B-Trees

The previous chapter left a loose thread. A balanced binary search tree is O(log n) for lookup — asymptotically excellent — and yet no database in the world uses one for its indexes. They all use a B-tree instead. Understanding why is one of the most clarifying moments in systems programming, because the reason is not in the algorithm. Both trees are O(log n). The reason is the memory hierarchy, and it is the same lesson this whole book keeps returning to: the number of levels you touch matters far less than whether touching each one is a cache hit or a cache miss.

The problem: a binary tree is all misses

Walk a balanced binary search tree of a million keys and you descend about 20 levels. Each level is a single comparison — trivial work — followed by a pointer to one of two children. But those children were allocated whenever they were inserted, so each lives at some unpredictable address on the heap. Every step down the tree is therefore a cache miss: the CPU stalls ~100ns, roughly 300 cycles, fetching a line from main memory just to read one key and one pointer, then does it again, twenty times. The tree is O(log n) in comparisons and O(log n) in cache misses, and on modern hardware the second number is the one that hurts.

The fix is almost obvious once you see the problem. A cache miss brings in a whole 64-byte line whether you use one key or sixteen, so put many keys in each node — sized in whole cache lines in memory, or a page on disk — and do a small linear or binary scan within the node before descending. The node stops being a place to hold one key and becomes a batch of them. Now each expensive memory fetch does real work, and because each node has many children instead of two, the tree is dramatically shallower: a B-tree with 32 keys per node holds a million keys in about four levels instead of twenty. Twenty scattered pointer chases become four short contiguous scans. That is the entire idea of a B-tree.

Width has a cost, though: nodes must be kept between half-full and full so the tree stays balanced and shallow. The mechanism is the split — when a node overflows, its median key moves up to the parent and the node divides in two. Splits are the only thing that makes a B-tree taller, and they happen from the bottom up, which is why every leaf always ends at the same depth. Watch a full leaf split and grow the tree, then a second insert ride into the existing root:

The payoff, measured

Here are both structures holding the same two million sorted keys, answering the same million random lookups. Both are O(log n). The only difference is node width — binary versus 32 keys per node:

Roughly 8× faster, for the same keys and the same complexity class, purely because the B-tree turned twenty cache misses into a handful. When the data lives on disk instead of in RAM the effect is even more extreme — an SSD read is not 100 nanoseconds but a hundred thousand, and a spinning disk’s seek is ten million — which is why the idea was invented for disks in 1970 and never left.

Why databases are built on this

A database index has to answer two kinds of question fast: “find the row with id = X” (a point lookup) and “find all rows with id between X and Y” (a range scan). A hash index (the hash-table chapter) nails the first and cannot do the second at all — it threw away order. A B-tree does both: point lookups in O(log n) shallow steps, and range scans by walking the sorted leaves, which in a B+ tree (the variant every database actually uses) are linked together precisely so a range scan is a sequential walk. Ordered data, logarithmic lookup, sequential ranges, and a shape that matches how disks and caches move data — a B-tree is what you get when you design a search tree for the machine it actually runs on.

The one place B-trees strain is write-heavy workloads. Every insert has to find its leaf and update it in place, and at scale those leaf updates are random writes scattered across the disk — exactly the access pattern storage hardware is worst at. Holding the tree balanced under a high write rate becomes the bottleneck. That pressure is what motivates the next chapter’s structure, which turns random writes into sequential ones.

Engineering judgment

• You rarely implement a B-tree; you rely on one. The practical skill is knowing that your database’s index is a B-tree and reasoning accordingly — that lookups and range scans are cheap, that an index makes reads fast and writes a little slower, and why.
• Match node size to the hardware. In memory, a cache line (64 bytes). On disk, a page (a few KB). The whole point is one expensive fetch per level, so the node should be exactly as big as one fetch delivers.
• Reach for a B-tree (or its database) when you need ordered data with fast lookup and range queries. If you only ever do exact-key point lookups and never range or sorted access, a hash index is faster — use that instead.
• If your workload is write-dominated at scale, a B-tree’s in-place random writes become the bottleneck — and that’s the signal to look at an LSM tree.

Interview checklist

Takeaways

• A binary search tree is O(log n) but pays a cache miss per level — ~20 misses for a million keys — which is slow on real hardware despite the good asymptotics.
• A B-tree packs many keys into cache-line- or page-sized nodes, so the tree is shallow and each level is one fetch. Same O(log n), an order of magnitude fewer misses — you measured ~8× above.
• It gives ordered data, logarithmic point lookups, and sequential range scans (in the B+ variant), which is why every database index and filesystem is a B-tree.
• Its weakness is write-heavy workloads, where in-place random writes bottleneck — the problem the next structure solves.

Next, LSM trees — the structure that gives up in-place updates entirely to turn random writes into sequential ones, and powers the write-optimized databases behind modern data infrastructure.