Fanout, Height, and Why B-Trees Stay Shallow

A binary search tree over a billion keys has a height near thirty, because each comparison can only halve the remaining range. A B-tree over the same billion keys has a height of three or four. The difference is not a better search algorithm; both perform binary search. The difference is that a B-tree node is a page, and a page holds hundreds of keys rather than one, so a single read of a node discards a factor of hundreds of the remaining search space instead of a factor of two.

That ratio, not any clever ordering property, is the entire reason B-trees dominate disk-resident indexing. Every other design decision in a B-tree follows from trying to keep the ratio large.

Deriving the branching factor from the page

Consider a page of 8192 bytes holding an internal node of a B+-tree. Each entry in such a node consists of a separator key and a pointer to a child page. Take a key of 10 bytes and a child pointer of 6 bytes, and add a 2-byte slot offset for the entry directory that most page formats use to keep entries variable-length. Each entry costs about 18 bytes, and the page holds roughly

$$B \approx \frac{8192}{18} \approx 455$$

children. The exact number depends on the format: some engines store a fixed-size header, some reserve space for a rightmost pointer, some store the separator as a prefix-compressed fragment. The order of magnitude is what matters, and it is a few hundred.

The height follows from the branching factor. A tree of height $h$ (root at level 1) with fanout $B$ both in internal nodes and in leaves addresses at most $B^{h}$ keys, since the leaves hold $B$ entries each and there are $B^{h-1}$ of them. So the height needed for $N$ keys is $\lceil \log_B N \rceil$. For $N = 10^9$ and $B = 455$:

import math

def height(keys: int, fanout: int) -> int:
    # Internal nodes and leaves both hold `fanout` entries, so a tree of
    # height h addresses at most fanout**h keys.
    return math.ceil(math.log(keys) / math.log(fanout))

print(height(10**9, 455))   # 4
print(height(10**9, 2))     # 30

Four page reads, of which the top ones are almost always cached. A binary tree over pages needs thirty, and every one of those is a separate page. The comparison count is also different: a binary search within a 455-entry page costs about nine comparisons, so a four-level descent costs roughly thirty-six comparisons against thirty for the binary tree. The B-tree does slightly more work in the CPU and an order of magnitude less work in the memory hierarchy, and on any storage medium where a page fetch costs thousands of times a comparison, that trade is not close.

Which levels are actually cached

The upper levels of a B-tree are small enough that they live in memory permanently, which changes the effective height of the tree. With fanout 455, level 1 is one page, level 2 is 455 pages, level 3 is about 207,000 pages, and level 4 is the leaves. At 8 KiB per page the first two levels total under four megabytes and the third totals about 1.6 GiB.

For most indexes the root and the second level are resident, so a lookup that reaches a leaf touches one page it may not have. The height of the tree is therefore not the number of I/Os; the number of I/Os is roughly the number of levels below the cached frontier, which is usually one. This is why adding a level to an index is much less catastrophic than the raw height suggests, and why an index that grows from three to four levels does not double in cost.

The corollary is that the buffer pool’s job is to hold the top of every hot index, and the top of an index is cheap: a hundred indexes with three cached upper levels each consume a few hundred megabytes, not gigabytes. Engines that pin the root page explicitly are exploiting exactly this arithmetic.

Why leaf pages are chained rather than only treed

A point lookup descends the tree and stops. A range scan descends once and then walks forward across many leaves, and a pure tree walk would have to ascend to a common ancestor and descend again for every leaf boundary, costing two extra page reads per boundary crossed. Every production B+-tree therefore stores a forward link to the next leaf page in the leaf pages themselves, forming a linked list at the bottom of the tree.

The link is what makes the separator keys in internal nodes only a routing device rather than a complete description of order. Internal nodes do not need to contain every key, because the leaf chain defines the actual sequence. A scan of a million rows reads a million rows’ worth of leaves sequentially and consults the internal nodes exactly once. This is also why leaf pages are the only pages whose layout affects scan throughput, and why compression schemes are applied there first, as described in prefix compression in index pages.

The fanout is smaller than the arithmetic suggests

The 455-entry figure assumes full pages holding short keys. Several routine conditions reduce it.

Wide keys reduce fanout linearly. A composite index on two 40-byte string columns gives entries near 90 bytes with the pointer and slot overhead, and fanout drops to about 90. The height for a billion keys rises to five. Long keys also force page formats to store key prefixes only, or to store the key once in an overflow area, and both of those reintroduce a second read.

Half-full pages reduce it again. A B-tree built by random insertion settles at roughly 69 percent occupancy on average, a figure that follows from the distribution of split points, so the effective fanout of an internal node is nearer 300 than 455. After a large deletion wave, pages can sit near the minimum occupancy of one half, and the effective fanout halves again. An index that was four levels deep can become five without any change in the number of rows, which is a real operational hazard for tables that grow and shrink.

Fixed-size page headers reduce it slightly. A page format that reserves 96 bytes of header and maintains a free-space map pays that cost once per node, which matters at the margins but not for the order of magnitude.

The mitigation for wide keys is compression. Prefix compression stores the shared prefix of neighbouring keys once, and suffix truncation stores only enough of a separator to distinguish the left subtree’s maximum from the right subtree’s minimum. Both raise the effective fanout, and both are covered where they belong, in the article on compressed pages. The mitigation for low occupancy is a fill factor setting at build time, which trades space for a shallower tree, and which interacts with the split and merge behaviour described in node splits, merges, and the fill factor.

Where the page-sized node stops being right

The page is the right node size when a node read costs a device access. When the whole index fits in memory, the relevant cost becomes a cache miss rather than a page fault, and a cache line is 64 bytes on the common architectures. A node of 8 KiB then spans 128 cache lines, and a binary search across it touches a different line at each of its first several probes, so the last few comparisons each pay a full miss. In-memory indexes respond by shrinking the node to one or a few cache lines, or by replacing the comparison-based layout with a radix layout in which the key bytes themselves select the child, giving a bounded number of dependent loads. The height falls to the key length in bytes rather than the logarithm of the row count.

The same arithmetic explains the LSM alternative. When writes must be sequential, the tree cannot be updated in place at all, and the index becomes a set of sorted runs merged over time, with the number of runs standing in for the height of the tree. The read cost of that structure is governed by how many runs a lookup must consult, which is the direct analogue of height, and the mechanisms that keep it bounded are the subject of leveled compaction and the shape of the LSM tree.

The invariant worth carrying away is that index depth is a ratio of page size to entry size, and everything that makes an index slow is something that reduced that ratio: wide keys, sparse pages, per-entry overhead, or a node size mismatched to the medium.