One thing to keep in mind is that keeping the keys sorted on an insert requires O(k) element moves, so an insert is O(log2(n) + k) operations. So if you make k very large your inserts get slower.
B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
21–30 of 78 posts
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#22How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used.
A B-tree of any branching factor (not only 2) is equivalent to a binary tree.
We can take any B-tree node n:
n
|
---------+-----------
| | | | | |
a b c d e f
n
|
/ \
a /\
b/\
c/\
d/\
e/\
f nil
What the unbalanced tree cannot do is binary search through a to f to find which one to descend into; it doesn't have those nodes in a neat array for that.
That binary search makes B-tree more or less equivalent to a very balanced binary tree.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#23Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
I have a soft spot for red-black trees ever since reading about them in Dr. Dobbs - it's the first time I remember reading about a data structure (and it went mostly over my head at the time - but the fond memory remain):
I believe it was the 1992 article by Bruce Schneier:
https://jacobfilipp.com/DrDobbs/articles/DDJ/1992/9204/9204c...
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#24Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
Red-black trees use to make me anxious. I think the first time I grasped them was after watching Erik Demaine's lecture on the topic. For anyone interested it is this [1]; its still a very good reference on the topic! [1] https://videolectures.net/mit6046jf05_demaine_lec10/
RB trees still make me anxious which is why I use AA trees instead
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#25Earlier quoted context omitted.
If your concern is just arbitrary lookups then your baseline is a hashmap though.
Not really. Hashmaps don't have guaranteed performance characteristics and require the "correct" hash function to work properly. In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size. Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.
Trees require a lot more memory indirections than hashmaps, which makes them slower to traverse. They require a lot more interior pointers, which makes them bigger. It’s easy for a hashmap to beat a tree.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#26Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
> Later I looked at AVL trees... and they still give me a headache.
Why? From what I remember AVL trees were much easier to implement than B-trees. Especially if using recursion.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#27Earlier quoted context omitted.
Not really. Hashmaps don't have guaranteed performance characteristics and require the "correct" hash function to work properly. In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size. Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.
Trees require a lot more memory indirections than hashmaps, which makes them slower to traverse. They require a lot more interior pointers, which makes them bigger. It’s easy for a hashmap to beat a tree.
Not in the worst case.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#28Earlier quoted context omitted.
If your concern is just arbitrary lookups then your baseline is a hashmap though.
Not really. Hashmaps don't have guaranteed performance characteristics and require the "correct" hash function to work properly. In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size. Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.
> Not really.
Yes really, that’s why the vast majority of languages default to a hashmap (if they even have tree-based maps at all). Turns out the average application is a lot more interested in a low-constant-factor O(1) best case than in a high-constant-factor O(log n) worst case.
> Hashmaps don't have guaranteed performance characteristics
Of course they do.
> require the "correct" hash function to work properly.
And tree maps require correct comparators to work correctly.
> In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size.
Yes? Also “n-times” seems like pretty fuddy fud. And it seems weird to be more worried by the reallocation of a hashmap when a tree requires an allocation per node, so your average balanced tree requires a heap allocation per entry. And two pointers, for up to 16x overhead not including the allocator’s own metadata.
> Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.
And the amphibious cycle could be regarded as the more generic solution to the transport problem.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#29That does not mean that b-trees are unequivocally better than binary search trees. There are some applications, like concurrency or persistence, where comparison count is not as important. For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time. The binary structure also makes it possible to…
> For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time.
But this also assumes single-threaded computation. Increasingly, high-performance computers are SIMD-compute (aka: GPUs, and if not, at a minimum you're using AVX512 or ARM SVE).
If you have 1024-threads per thread group (common maximum in GPUs), that will commonly be used to create 1024-element B-Tree nodes, as sorting can be accomplished in a single pass network. (Bitonic network: https://en.wikipedia.org/wiki/Bitonic_sorter)
A singular lock that covers the whole 1024-node would better match these very wide GPUs that perform very wide SIMD-execution in practice. Physically, GPUs are 32-wide for NVidia and 32-wide or 64-wide for AMD. But various software tricks increase the width by either ganging-up neighboring compute-units in parallel and synchronizing them... or by running the same code across sequential passes like in AMD GCN architecture.
However, the programming interface of a 1024-wide (looking) piece of hardware/equipment naturally maps to 1024-wide B-Tree nodes, a 1024-wide Bitonic sort (or MergePath sort), and other such parallel sorting networks.
----------
B-Trees are "some number larger than 2", which I think for modern high-performance SIMD-based GPUs, the number absolutely should be "more than 2".
Where I'm wondering, is if the optimal algorithm is 32-wide (aka: one NVidia wave, the smallest unit of computation on an NVidia GPU), or if the optimal algorithm is 1024-wide (the maximum gang of waves that can work as a team). Or if maybe using the said maximum-gang across an even larger node (ex: 4096-wide) has any benefits.
--------
We are reaching the point where compute is so cheap that even a 1024-wide parallel sort is a trifling thing.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#30B-Tree are a good fit if your values are small, but as the value size grows, they lose their advantage.
Binary tree is a good default choice for sorted structure.
Underappreciated structure: sorted arrays (but come with big caveats).