B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

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.

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.

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.

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

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

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-Balan... [2] https://rtheunissen.github.io/bst

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.

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!

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