8 ms·

B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

191 points by greghn 2y ago

shagie 2y ago
Long 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 planning over the weekend (this was in the "we're redoing the class, teach it as it needs to be taught" type mandate) and he had us skip that section of the text. The fist lecture he was going off of overhead transparencies that he was writing as he lectured. The second lecture he gave us photocopies of hand written notes and diagrams. Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees. For what it's worth, I still know how to do 2-3 trees from scratch. Later I looked at AVL trees... and they still give me a headache.
- abhgh 2y ago
  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/ https://videolectures.net/mit6046jf05_demaine_lec10/
  - cassepipe 2y ago
    RB trees still make me anxious which is why I use AA trees instead https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree
    - deleted 2y ago
      [deleted]
- teruakohatu 2y ago
  I feel there must be better ways of learning the principles of algorithms than balancing trees. I suffered through RB trees.
  - 082349872349872 2y ago
    There are two fundamental things to teach in an algorithms course: 1) that there are many programs that implement the same algorithm, and many algorithms that implement the same function. 2) that there are a few basic tradeoffs we can make when implementing a function/customising an algorithm: space vs time, read vs write, deterministic vs indeterministic, etc. I'd guess trees have traditionally been used, because there's a whole zoo of them, which clearly presents (1) and allows (2) to be learned (in "cookbook" style) even if they're never explicitly presented (in "textbook" style).
  - ajuc 2y ago
    Suffering is the point. It's like exercises in math or push-ups - if you find a way to do them effortlessly you won't develop the skills you are training for. I agree they suck tho.
- slaymaker1907 2y ago
  B-trees are definitely more useful, but I don’t think they’re really a good idea to start out with as your first balanced tree.
- 29athrowaway 2y ago
  Left leaning red black trees are simpler to implement than the regular red black tree.
  - skribanto 2y ago
    Left leaning red black trees enforce extra constraints, which remove symmetries. This actually adds an edge case when instead you can just treat left/right rotations and comparisons as symmetric operations. Left Leaning Red Black Trees Considerer Harmful: https://www.read.seas.harvard.edu/~kohler/notes/llrb.html https://www.read.seas.harvard.edu/~kohler/notes/llrb.html
- saghm 2y ago
  > Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever reason, I've run into cases far more often where I need to maintain insertion order than sort order, but I'm not confident about whether this is due more to the type of stuff I work on or if it's just a more common requirement in general.
  - globular-toast 2y ago
    They're not about maintaining sort order, though? They're about arbitrary lookup. Or do you mean "if I had to pick one nice side effect"?
    - masklinn 2y ago
      If your concern is just arbitrary lookups then your baseline is a hashmap though.
      - globular-toast 2y ago
        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.
        fanf2 2y ago
        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.
- tgv 2y ago
  AVL isn't complicated. Insert the node as you would in a binary tree. Do that recursively. Then, when you return from inserting, you check at each level if the height of the tree under the left and right children differ at most 1. If not, you perform a little shuffle of the nodes, update the levels, and return to the previous level. That's all. The proof that that works is a bit complicated, though.
- e12e 2y ago
  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/9204c.htm https://jacobfilipp.com/DrDobbs/articles/DDJ/1992/9204/9204c...
- DanielHB 2y ago
  > 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.
  - whizzter 2y ago
    Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for. Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it was able to produce quite an exhaustive set of conditions.
    - nayuki 2y ago
      B-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling. In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl. I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set , etc.
      - DanielHB 2y ago
        Yeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...
- nayuki 2y ago
  I would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set https://www.nayuki.io/page/aa-tree-set B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set
  - ncruces 2y ago
    Another (immutable/persistent) AA tree implementation, in Go: https://github.com/ncruces/aa https://github.com/ncruces/aa
- harrison_clarke 2y ago
  red black trees can be thought of as 2-4 trees, and they're way less headache-inducing when you do if you inline the red nodes into the black nodes, you get a 2-4 tree node. except that the 3-nodes have chirality. but then, you can just use a 2-4 tree AVL trees seem not worth learning. they have slightly different performance characteristics than red-black trees. but, if i care about performance beyond big O, i'm probably using a hash table or a cache-aware tree of some kind instead of a CS101 data structure
cperciva 2y ago
In a sense, red-black and 2-3 trees are just a special case of B-trees with small nodes. Smaller B-tree nodes have (by a constant factor) more expensive searching than larger nodes; but smaller nodes are more efficient for mutating operations. And indeed, if you have an insert/delete heavy workload you can't beat something like a red-black tree.
- anonymoushn 2y ago
  This sounds surprising, unless you mean specifically a workload where a bunch of inserts and deletes are made using a stored cursor, so that they don't need to follow a bunch of pointers from the root.
- aidenn0 2y ago
  AA trees are isomorphic to 2,3 trees and RB trees are isomorphic to 2,4 trees. IIRC we learned 2,4 trees first in my data-structures class, and then demonstrated that RB trees were a different representation of the same idea.
masklinn 2y ago
> Practical B-trees often use fairly large values of k (e.g., 100) and therefore offer tight bounds -- in addition to being more cache-friendly than binary search trees. That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.
- leni536 2y ago
  Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set<int32_t>, nodes currently have 62 children ... https://abseil.io/about/design/btree https://abseil.io/about/design/btree
  - vlovich123 2y ago
    From the looks of it Rust [1] uses a constant branching factor based on number of items whereas ABSEIL generally uses a target of 256 bytes [3] for branching and fits however many elements fit within that [2]. Rust’s approach seems to be more primitive as ABSEIL is optimizing for cache line usage (not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?) [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/library/alloc/... [2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/internal/btree.h#L428-L443 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724... [3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/btree_map.h#L93 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...
    - masklinn 2y ago
      > not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing? The AMD64 cache line is only 64 bytes, that would make for very low branching factors given interior nodes need a pointer per child, plus key, plus record pointer if b-tree (as opposed to b+tree).
rtheunissen 2y ago
That 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 support randomized balancing and self-adjusting strategies like splay trees. I am disappointed to still see frequent mention of red-black trees – I see no reason for red-black trees to ever be the best choice in practice, or in theory, or in school. LBST's (logarithmic binary search trees) [1] are generally simpler, more intuitive, and more efficient [2] than red-black trees. They also support positional access inherently, so the balancing information is useful (subtree size). [1] https://www.semanticscholar.org/paper/A-New-Method-for-Balancing-Binary-Search-Trees-Roura/f50d33d56a11b6c3423cf003d13f717d137d1154 https://www.semanticscholar.org/paper/A-New-Method-for-Balan... [2] https://rtheunissen.github.io/bst https://rtheunissen.github.io/bst
- dragontamer 2y ago
  > 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 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.
orlp 2y ago
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.
kazinator 2y ago
How 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 and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every node of the B-tree, like from a to f, it as if we are traversing the unbalanced tree (except for constant-time instruction and cache level efficiencies). 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.
- jvanderbot 2y ago
  I don't think so? I think the b-tree is using the start/end sequence knowledge at each to do fewer node evaluations. That is, a b-tree is "shorter" so of course it'll take fewer node evaluations to reach the leaf. "b-tree is equivalent to balanced binary tree", and "unbalanced tree", don't make a ton of sense when ostensibly the article compares b-trees to balanced BST.
- bunderbunder 2y ago
  Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
  - sam0x17 2y ago
    yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
  - shpongled 2y ago
    Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...
shin_lao 2y ago
B-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).
- LorenPechtel 2y ago
  Not counting access costs binary is always the best for *reading*, but that comes at the cost of expensive *writing*. B-trees are a compromise between reading and writing. The various other tree types are actually just special cases of b-trees. B-tree also enjoys a *massive* advantage when your access block size can hold many keys. With big data this will always win.
nayuki 2y ago
Blogspot supports HTTPS. Please always use it when linking to the site.
exabrial 2y ago
I think either is a good choice for knowing nothing about the data set. After n grows large enough, I think you’d want to benchmark your -exact- dataset on your -exact- prod hardware. Some datasets may cause certain trees to perform badly. Some hardware is much faster at memory lookups and cache misses are not as painful. For instance, developing locally on Intel and deploying to Arm could yield pretty wild performance differences!

191 points by greghn 2y ago

Long 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 planning over the weekend (this was in the "we're redoing the class, teach it as it needs to be taught" type mandate) and he had us skip that section of the text. The fist lecture he was going off of overhead transparencies that he was writing as he lectured. The second lecture he gave us photocopies of hand written notes and diagrams. Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees. For what it's worth, I still know how to do 2-3 trees from scratch. Later I looked at AVL trees... and they still give me a headache.

abhgh 2y ago
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/ https://videolectures.net/mit6046jf05_demaine_lec10/
- cassepipe 2y ago
  RB trees still make me anxious which is why I use AA trees instead https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree
  - deleted 2y ago
    [deleted]
teruakohatu 2y ago
I feel there must be better ways of learning the principles of algorithms than balancing trees. I suffered through RB trees.
- 082349872349872 2y ago
  There are two fundamental things to teach in an algorithms course: 1) that there are many programs that implement the same algorithm, and many algorithms that implement the same function. 2) that there are a few basic tradeoffs we can make when implementing a function/customising an algorithm: space vs time, read vs write, deterministic vs indeterministic, etc. I'd guess trees have traditionally been used, because there's a whole zoo of them, which clearly presents (1) and allows (2) to be learned (in "cookbook" style) even if they're never explicitly presented (in "textbook" style).
- ajuc 2y ago
  Suffering is the point. It's like exercises in math or push-ups - if you find a way to do them effortlessly you won't develop the skills you are training for. I agree they suck tho.
slaymaker1907 2y ago
B-trees are definitely more useful, but I don’t think they’re really a good idea to start out with as your first balanced tree.
29athrowaway 2y ago
Left leaning red black trees are simpler to implement than the regular red black tree.
- skribanto 2y ago
  Left leaning red black trees enforce extra constraints, which remove symmetries. This actually adds an edge case when instead you can just treat left/right rotations and comparisons as symmetric operations. Left Leaning Red Black Trees Considerer Harmful: https://www.read.seas.harvard.edu/~kohler/notes/llrb.html https://www.read.seas.harvard.edu/~kohler/notes/llrb.html
saghm 2y ago
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever reason, I've run into cases far more often where I need to maintain insertion order than sort order, but I'm not confident about whether this is due more to the type of stuff I work on or if it's just a more common requirement in general.
- globular-toast 2y ago
  They're not about maintaining sort order, though? They're about arbitrary lookup. Or do you mean "if I had to pick one nice side effect"?
  - masklinn 2y ago
    If your concern is just arbitrary lookups then your baseline is a hashmap though.
    - globular-toast 2y ago
      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.
      - fanf2 2y ago
        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.
tgv 2y ago
AVL isn't complicated. Insert the node as you would in a binary tree. Do that recursively. Then, when you return from inserting, you check at each level if the height of the tree under the left and right children differ at most 1. If not, you perform a little shuffle of the nodes, update the levels, and return to the previous level. That's all. The proof that that works is a bit complicated, though.
e12e 2y ago
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/9204c.htm https://jacobfilipp.com/DrDobbs/articles/DDJ/1992/9204/9204c...
DanielHB 2y ago
> 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.
- whizzter 2y ago
  Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for. Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it was able to produce quite an exhaustive set of conditions.
  - nayuki 2y ago
    B-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling. In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl. I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set , etc.
    - DanielHB 2y ago
      Yeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...
nayuki 2y ago
I would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set https://www.nayuki.io/page/aa-tree-set B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set
- ncruces 2y ago
  Another (immutable/persistent) AA tree implementation, in Go: https://github.com/ncruces/aa https://github.com/ncruces/aa
harrison_clarke 2y ago
red black trees can be thought of as 2-4 trees, and they're way less headache-inducing when you do if you inline the red nodes into the black nodes, you get a 2-4 tree node. except that the 3-nodes have chirality. but then, you can just use a 2-4 tree AVL trees seem not worth learning. they have slightly different performance characteristics than red-black trees. but, if i care about performance beyond big O, i'm probably using a hash table or a cache-aware tree of some kind instead of a CS101 data structure

cperciva 2y ago

In a sense, red-black and 2-3 trees are just a special case of B-trees with small nodes. Smaller B-tree nodes have (by a constant factor) more expensive searching than larger nodes; but smaller nodes are more efficient for mutating operations. And indeed, if you have an insert/delete heavy workload you can't beat something like a red-black tree.

anonymoushn 2y ago
This sounds surprising, unless you mean specifically a workload where a bunch of inserts and deletes are made using a stored cursor, so that they don't need to follow a bunch of pointers from the root.
aidenn0 2y ago
AA trees are isomorphic to 2,3 trees and RB trees are isomorphic to 2,4 trees. IIRC we learned 2,4 trees first in my data-structures class, and then demonstrated that RB trees were a different representation of the same idea.

masklinn 2y ago

> Practical B-trees often use fairly large values of k (e.g., 100) and therefore offer tight bounds -- in addition to being more cache-friendly than binary search trees. That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.

leni536 2y ago
Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set<int32_t>, nodes currently have 62 children ... https://abseil.io/about/design/btree https://abseil.io/about/design/btree
- vlovich123 2y ago
  From the looks of it Rust [1] uses a constant branching factor based on number of items whereas ABSEIL generally uses a target of 256 bytes [3] for branching and fits however many elements fit within that [2]. Rust’s approach seems to be more primitive as ABSEIL is optimizing for cache line usage (not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?) [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/library/alloc/... [2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/internal/btree.h#L428-L443 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724... [3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/btree_map.h#L93 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...
  - masklinn 2y ago
    > not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing? The AMD64 cache line is only 64 bytes, that would make for very low branching factors given interior nodes need a pointer per child, plus key, plus record pointer if b-tree (as opposed to b+tree).

rtheunissen 2y ago

That 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 support randomized balancing and self-adjusting strategies like splay trees. I am disappointed to still see frequent mention of red-black trees – I see no reason for red-black trees to ever be the best choice in practice, or in theory, or in school. LBST's (logarithmic binary search trees) [1] are generally simpler, more intuitive, and more efficient [2] than red-black trees. They also support positional access inherently, so the balancing information is useful (subtree size). [1] https://www.semanticscholar.org/paper/A-New-Method-for-Balancing-Binary-Search-Trees-Roura/f50d33d56a11b6c3423cf003d13f717d137d1154 https://www.semanticscholar.org/paper/A-New-Method-for-Balan... [2] https://rtheunissen.github.io/bst https://rtheunissen.github.io/bst

dragontamer 2y ago
> 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 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.

orlp 2y ago

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.

kazinator 2y ago

How 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 and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every node of the B-tree, like from a to f, it as if we are traversing the unbalanced tree (except for constant-time instruction and cache level efficiencies). 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.

jvanderbot 2y ago
I don't think so? I think the b-tree is using the start/end sequence knowledge at each to do fewer node evaluations. That is, a b-tree is "shorter" so of course it'll take fewer node evaluations to reach the leaf. "b-tree is equivalent to balanced binary tree", and "unbalanced tree", don't make a ton of sense when ostensibly the article compares b-trees to balanced BST.
bunderbunder 2y ago
Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
- sam0x17 2y ago
  yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
- shpongled 2y ago
  Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1]. [1] https://en.algorithmica.org/hpc/data-structures/binary-search/ https://en.algorithmica.org/hpc/data-structures/binary-searc...

shin_lao 2y ago

B-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).

LorenPechtel 2y ago
Not counting access costs binary is always the best for *reading*, but that comes at the cost of expensive *writing*. B-trees are a compromise between reading and writing. The various other tree types are actually just special cases of b-trees. B-tree also enjoys a *massive* advantage when your access block size can hold many keys. With big data this will always win.

nayuki 2y ago

Blogspot supports HTTPS. Please always use it when linking to the site.

exabrial 2y ago

I think either is a good choice for knowing nothing about the data set. After n grows large enough, I think you’d want to benchmark your -exact- dataset on your -exact- prod hardware. Some datasets may cause certain trees to perform badly. Some hardware is much faster at memory lookups and cache misses are not as painful. For instance, developing locally on Intel and deploying to Arm could yield pretty wild performance differences!