B-tree pages: fanout is a layout calculation

In the B+ tree style used for this lesson, leaf entries contain search keys and row references or payloads, while internal pages contain separators and child references. A search compares its key with separators and descends toward the appropriate leaf. The separator convention must define boundary equality and duplicates consistently. After locating a starting leaf, sibling links can support an ordered range scan without restarting at the root for every returned entry. Different B-tree variants place records differently, so state which layout is being analyzed.

An internal page with m children commonly needs m child references and m−1 separators in a simple teaching representation. A leaf does not have that same relationship: each leaf entry includes its own complete record reference or payload. Slot arrays, tuple headers, high keys, sibling pointers, and alignment also consume bytes. Our formulas collect fixed overhead in H and assume fixed-width entries. Variable-length keys, compression, deduplication, and truncated internal separators change actual capacity; an average width is an estimate rather than a hard limit.

If every internal page has F children and every leaf contains L entries, a tree of h page levels can hold L times F to the power h−1 entries. This is a maximum-capacity model, not a promise that inserts always achieve those occupancies. For one count-based classical B+ policy, non-root internal pages have ceil(F/2) through F children and non-root leaves have ceil(L/2) through L entries; a non-leaf root has at least two children. Those bounds require compatible split and merge rules. Real database implementations can use different split targets, deferred deletion, or workload-specific fill policies. Do not transfer a textbook half-full invariant to every production page without checking its algorithm.

A useful estimate separates leaf fill from internal fanout. Wider included values can reduce leaf capacity without changing internal routing width in a design that excludes those values from upper levels. Skewed insertion patterns can leave some pages sparse and others frequently splitting. Keys also need a consistent total ordering under the chosen comparator or collation; violating that contract breaks navigation regardless of available space. Derive the shape from observed page statistics when capacity planning, and keep the maximum model as a sanity bound.

A three-level search visits three logical index pages on its descent, but the root and upper internal pages may already be cached. A leaf miss can then dominate physical I/O. A range query adds leaf pages and may fetch table rows elsewhere, while an index-only scan has additional visibility requirements in MVCC systems. CPU comparisons, cache misses, latching, and decompression remain relevant even when every page is in memory. Avoid turning a tree-height calculation into an exact elapsed-time claim.

Use the cache lab to isolate reuse. Press Reset, set capacity C=4 and stride s=4, then predict that the sixteen initial requests over addresses 0,4,8,12 produce four misses and twelve hits. Play or Step to extend that same stream. For a separate experiment, Reset, set C=3 and s=4, predict zero hits for the repeating four-address cycle, then Play or Step. This is a fully associative LRU instrument, not a B-tree or buffer manager. It shows why a shallow tree's frequently reused pages and its physical-read cost require a workload argument.