B-Tree Fanout Arithmetic and the Cost of a Point Lookup

A B-tree answers a point lookup in a number of node visits equal to its height. Everything interesting about the structure follows from one design decision: the node is the unit of I/O, and the node size is chosen to match the device’s transfer granularity. Once that decision is made, the arithmetic of how many keys fit in a node determines how tall the tree is, and the height determines how many round trips a lookup costs.

Fanout is a division problem

A B-tree node of order m holds at most m − 1 keys and m child pointers. The keys partition the key space: key i sits between the subtrees reached by pointer i and pointer i+1. For a node of B bytes, k bytes per key, and p bytes per pointer, the maximum order satisfies

m ≤ ⌊(B + k) / (k + p)⌋

because m pointers and m − 1 keys occupy m·p + (m−1)·k bytes, and the + k in the numerator is exactly the correction for the one key that the pointer count does not account for. For a 4 KiB page, 8-byte pointers, and 16-byte keys, that is (4096 + 16) / 24 ≈ 171 pointers, so a fanout of 171. With 4 KiB pages and 8-byte integer keys plus 8-byte row identifiers, fanout rises past 250.

The height follows from the fanout. A tree with fanout f holds at most f^h keys at depth h (counting the root as depth 1), so a billion keys needs ⌈log_f 10⁹⌉ levels. For a fanout of 171 that is ⌈log₁₇₁ 10⁹⌉ = 5 levels of nodes in all — four internal pages and one leaf — because 171⁴ ≈ 8.6 × 10⁸ falls just short of a billion while 171⁵ ≈ 1.5 × 10¹¹ covers it. A lookup costs at most five page reads, and because the upper levels are always resident in the buffer pool, the number of reads that actually reach the device is one or two.

This is the entire reason B-trees displaced balanced binary trees for on-disk indexes. A binary tree over a billion keys has height 30, and 30 dependent page reads are 30 device round trips, each one a seek plus rotational latency on a rotating disk and a far larger penalty on anything that touches the network. Five levels with three cached is one or two reads. The comparison count is far higher in the B-tree — each node visit does a binary search over up to 170 keys, about 8 comparisons — but comparisons are nanoseconds and page reads are not.

The node layout in bytes

The node’s internal structure matters less than its size, but two layout choices recur.

Separator keys stored in full. Each node holds copies of the keys that separate its children. In a B-tree (as opposed to a B+-tree) these are the actual data keys, so a key may appear once in the whole tree; in a B+-tree the separators are copies and the data lives only in leaves. The B+-tree layout is what almost every database uses, because it makes every lookup end at a leaf — uniform cost — and it makes range scans a leaf-chain walk rather than a tree traversal.

Prefix compression on separators. When consecutive keys share a long prefix, storing the full key in every separator wastes most of the node. A common technique stores only the distinguishing suffix plus a length, which can raise fanout substantially for string keys. The cost is that comparison requires reconstructing the key, and reconstruction requires walking back to the start of the node or to a restart point.

A typical B+-tree leaf holds key-value pairs and a sibling pointer, and is filled to a target occupancy — commonly around three quarters of capacity, not full — so that subsequent insertions do not immediately split. The internal node has one more pointer than key, and the leftmost pointer carries no key.

Descending a node

Within a node, the search for the child pointer is a binary search over the sorted separator array, giving ⌈log₂ m⌉ comparisons. For m = 171, that is 8 comparisons. An alternative for small nodes is a linear scan, which has a lower constant but a comparison count that grows with the node; at 170 keys, linear scan averages 85 comparisons and loses. The separator array is also redundancy in the limit: its only job is to describe the boundaries between subtrees, and a model fitted to the key-to-rank mapping can describe the same boundaries with a few parameters rather than hundreds of stored keys.

/* Returns the child index to follow for key, in a node with nkeys separators
   stored in keys[0..nkeys) and nkeys+1 child pointers. */
int child_for(const int64_t *keys, int nkeys, int64_t key)
{
    int lo = 0, hi = nkeys;         /* find first separator >= key */
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (keys[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;                      /* 0..nkeys, one past the end included */
}

The subtlety is the boundary: the returned value ranges from 0 to nkeys inclusive, which is exactly the count of child pointers. A search that returns nkeys − 1 at most will send keys greater than the last separator into the wrong subtree, and the error only appears for keys in the rightmost child.

Node-level searches in a real implementation are rarely written this way, because the separator array is often stored in a format that supports SIMD comparison — 8 or 16 keys compared at once — turning the 8 comparisons into one or two vector instructions plus a horizontal reduction. That is a constant-factor change with a large effect on in-memory trees, which is why in-memory B-trees use much wider nodes than disk B-trees: with no page-read cost, the node size is chosen to fill a cache line or a few of them, and the fanout is set by the vector width rather than the page size.

Height, occupancy, and the split cascade

Height is a function of fanout and of how full the nodes actually are. A B-tree that splits a full node into two half-full nodes maintains the invariant that every node except the root is at least half full. The worst-case height bound is derived from the minimum occupancy: with minimum fanout ⌈m/2⌉, the height is at most log_{⌈m/2⌉} n + 1. For m = 171, the minimum fanout is 86, and the worst-case depth for a billion keys is 6 node visits (⌈log₈₆ 10⁹⌉ = 5 internal levels plus the leaf) against the 5 that a full tree achieves. The gap between best and worst case is one level, which is the point of the occupancy invariant.

Insertion descends to a leaf, inserts, and splits upward if the leaf overflows. A split of a node with m − 1 keys produces two nodes with about m/2 each and pushes one separator into the parent. If the parent is full, it splits too, and the cascade can reach the root, at which point the tree grows by one level. The amortised cost of the split work is constant per insertion: each split creates a node that must absorb about m/2 further insertions before it splits again, so the total split work over n insertions is O(n) node writes. The expensive part is not the split itself but the page writes it triggers, which is why write-optimised variants batch them.

Deletion is the mirror image and is where implementations diverge most. Merging two under-full siblings on every delete causes thrashing when the workload alternates insert and delete around a boundary. Real implementations usually tolerate under-full nodes and merge lazily, or merge only when occupancy falls below a lower threshold. The invariant is therefore often “at least half full” in the steady state and “may be under-full transiently” in the implementation.

Where the arithmetic stops paying

Three regimes break the model.

Keys larger than a fraction of the page. Fanout is inversely proportional to key size. With 512-byte keys on a 4 KiB page, fanout drops to 8 and height for a billion keys rises to 10, because 8⁹ ≈ 1.3 × 10⁸ is short and 8¹⁰ ≈ 1.1 × 10⁹ is enough. At that point the B-tree has lost most of its advantage over a binary tree, and the usual response is to store a hash or a short prefix in the index and the full key in the leaf, or to move to an index whose fanout is decoupled from the payload.

Very small trees. A tree of a few thousand keys fits in memory entirely, and the page-read argument vanishes. Height differences of one level are then noise, and simpler structures — a sorted array with binary search over a half-open interval, or the level-order layout that keeps the top levels in one cache line — do better because they avoid the node header and the pointer indirection.

Write-heavy workloads with random keys. Every insert touches a leaf page and dirties it. When the working set of dirty pages exceeds the cache, each insert becomes a random write. Log-structured merge trees address exactly this by buffering inserts in memory and writing sorted runs sequentially, trading lookup cost — a lookup must consult several runs — for write cost. The trade is explicit: B-trees optimise read amplification, LSM trees optimise write amplification, and the crossover depends on the ratio of reads to writes and on the device’s behaviour for random versus sequential writes. The same trade appears in the comparison of extendible hashing’s directory growth, where the cost being optimised is directory doubling rather than page splits.

A fourth, subtler limit is concurrency. A lookup that descends the tree must read node contents while other threads split and merge them. The standard solution is latch coupling: read-latch a child before releasing the parent’s latch, so the structure cannot change underneath the descent. The alternative is optimistic descent with version validation, which retries when a node changes mid-read. Both add per-level overhead that is invisible in the height arithmetic and dominant in a hot in-memory tree.

Reading the cost model correctly

The height formula is a lower bound on node visits, not on latency. Latency is height × (per-node cost), and per-node cost has three parts: the page read if not cached, the in-node search, and the latch. On a cached tree, the in-node search dominates, and the choice of 170 keys per node is then too many for a binary search and too few for a vector scan to be efficient. On an uncached tree, the page read dominates by two or three orders of magnitude and everything else is noise.

That asymmetry explains why the same abstract structure is tuned so differently in its two habitats. A disk B-tree wants nodes of exactly one page, occupancy high enough to keep height low, and as few levels as possible. An in-memory B-tree wants nodes sized to a cache line multiple, fanout set by SIMD width, and height that trades against in-node search cost. The arithmetic is the same division; the constants that matter are not.