3 ms·
Doesn't really seem much better than just a balanced size-tagged binary tree. You get O(log n) access, insertion, and deletion. Yes access is slower but inserti
by kccqzy 7y ago
Doesn't really seem much better than just a balanced size-tagged binary tree. You get O(log n) access, insertion, and deletion. Yes access is slower but insertion and deletion is much faster. Remember that for even one billion the logarithm is merely 30. That's hardly anything. Whereas the square root is more than 30 thousand.
- saagarjha 7y agoI wonder if you can save a bit in the constant by only having to chase one pointer instead of log(n) of them.
- igushev 7y agoThat sounds like trees are silver bullets but they're not and that's why we have variety of basic data structures.
- kccqzy 7y agoI'm not saying they are a silver bullet but personally from experience I think they are a good choice in the majority of scenarios that programmers encounter. Of course our experiences could differ.
- anarazel 7y agoThis type of data structure ought to have much better cache and branch prediction behaviour than most tree implementations.
- snovv_crash 7y agoReally depends on your dataset size, right? You give 1 billion as an example, that is 8GB of RAM in a single data structure just in overhead if you have a pointer for each tree leaf. This data structure makes more sense in the 10k-1M size, where chasing pointers is expensive and the scaling doesn't dominate.
- proverbialbunny 7y agoRight, or an rrb-tree which is effectively O(1) for everything. It's a tree of arrays where the arrays are usually 32 or 64 elements. Though, there's a bit more to it than that.