The B-tree has been the default index structure for fifty years, which is unusual enough to deserve an explanation. The explanation is that its shape is derived from the cost of a page read rather than from the cost of a comparison, and that derivation still holds.

The cost the structure is designed around

Every lookup in an on-disk structure costs page reads, and a page read is three to five orders of magnitude more expensive than a comparison in memory. So the quantity to minimise is not comparisons but pages touched.

Stating the objective that way immediately rules out most textbook structures. A binary search tree minimises comparisons, which is the wrong objective, and a structure that minimises comparisons while touching a page per comparison is a disaster on disk. Everything distinctive about the B-tree follows from optimising the right quantity.

What a high branching factor buys

If each node holds hundreds of keys and hundreds of child pointers rather than one key and two pointers, the tree's height collapses. Height is the number of page reads per lookup, so collapsing height is the whole game.

The arithmetic is worth seeing concretely because it is more dramatic than people expect. With a branching factor of around five hundred, three levels address one hundred and twenty-five million entries and four levels address sixty-two billion. Nearly every index in production is three or four levels deep, which means nearly every index lookup is three or four page reads.

The height formula

For

entries and a branching factor of , the height is , and because appears in the base, increasing it reduces height far faster than reducing does.

This is why the practical lever is the branching factor rather than the data volume. Halving the number of rows in a table reduces lookup cost by a fraction of one page read on average; doubling the branching factor, by making keys smaller, can remove a whole level. The second effect is a factor and the first is a rounding error.

Where the branching factor comes from

It is the page size divided by the size of one entry, where an entry in an internal node is a key plus a child pointer. An eight kilobyte page with sixteen byte entries holds around five hundred, so the key size directly sets the branching factor.

This is the practical consequence that most affects schema decisions. A thirty-two byte key halves the branching factor compared to a sixteen byte one, and a two hundred byte key reduces it to forty, which can add two levels to a large index. Choosing a narrow key is choosing a shallower tree, and the relationship is simple division.

Why all leaves are at the same depth

The B-tree maintains the invariant that every leaf is the same distance from the root, so every lookup costs the same number of page reads. There is no unlucky key and no degenerate case from an unfortunate insertion order.

This predictability is worth as much operationally as the low height is. An unbalanced structure has a worst case that appears only under particular data, which means a system can pass every test and then behave badly in production on real key distributions. The B-tree's balance is maintained by construction, so the worst case and the average case are the same.

How balance is maintained without rebalancing

Rather than rotating subtrees as a binary tree does, a B-tree splits a full node into two and pushes one separator key up to the parent, so the tree grows at the root rather than at the leaves.

This is the structural insight that makes the whole thing practical. Splitting touches a bounded number of pages, usually two or three, and growing at the root means the tree gets taller only when the root itself splits, which for a large index happens a handful of times in its life. There is no reorganisation and no global operation.

Why nodes are kept partly full

A node is allowed to be between roughly half and completely full. The lower bound guarantees the height bound holds; the slack means an insertion usually has somewhere to go without splitting anything.

The resulting space utilisation is around seventy percent in steady state under random insertion, which looks wasteful and is the price of amortised cheap insertion. A structure packed completely full would split on nearly every insertion, so the thirty percent of apparently wasted space is what makes insertion cost a fraction of a page write rather than several.

Why not a hash index instead

A hash index finds one key in one page read, which beats three. It cannot answer a range query, cannot return rows in order, and cannot support a prefix of a composite key, because hashing destroys the ordering that all three require.

The B-tree's one extra page read buys every ordered operation, and ordered operations are most of what a database does: ranges, sorts, group boundaries, merge joins and prefix matching. Paying one page read for all of that is why the B-tree is the default and the hash index is the special case.

Why not a skip list or a trie

Both are good in-memory structures whose per-node sizes are poorly matched to a page. A skip list's nodes are small and its traversal follows pointers across pages; a trie's branching is by character rather than by page capacity.

The general principle underneath is that an on-disk structure must have a node size equal to the page size, because that is the unit of transfer, and structures not designed around that constraint waste most of each page they touch. Page-sized nodes with maximal fanout is less a choice than a requirement.

The structure under modern hardware

Flash removed the seek penalty that originally motivated minimising reads, and the B-tree's advantage persisted anyway, because each read still costs a round trip of tens of microseconds and a shallow tree still makes fewer of them.

The deeper reason is that the same reasoning now applies one level up. Processor cache lines are to memory what pages are to disk, so a structure with cache-line-sized nodes and maximal fanout is the right answer for an in-memory index too. The B-tree's logic is about any memory hierarchy, which is why it survived the hardware change that was supposed to end it.

What the structure does not do well

Random insertion into a large tree is a random write pattern, since each insertion lands in an arbitrary leaf. On a device where random writes are much more expensive than sequential ones, this is the B-tree's weakness and the reason log-structured alternatives exist.

Being clear about this one weakness is what makes the comparison with log-structured storage a real engineering choice rather than a preference. The B-tree is excellent at reads and ordered access and merely acceptable at random writes; the log-structured family inverts exactly that, and later lessons treat the trade properly.

What to take from the shape

Three things. The structure optimises pages touched rather than comparisons, which is why high fanout and low height are its defining properties and why nearly every production index is three or four page reads deep. The branching factor is the page size divided by the entry size, so key width directly sets tree height and a narrow key is a shallower tree. And balance is maintained by splitting and growing at the root, which touches a bounded number of pages and never requires a global reorganisation.