Explain what fanout means for a B+tree index, how it is determined, and why an index over a billion rows is typically only three or four levels deep.

## Definition **Fanout** (branching factor) is the number of child pointers a single B+tree node holds. Because a node is exactly one storage page, fanout is a byte-budget question: ``` fanout ≈ usable bytes per page / (key bytes + child pointer bytes + per-entry overhead) ``` With an 8 KB page, an 8-byte integer key, a 6-8 byte page pointer and a few bytes of slot/header overhead, an entry costs on the order of 16-20 bytes, so roughly 400-500 entries fit. Pages are never packed to 100% — engines leave free space for future inserts and pay header and slot-directory overhead — so real fanout is somewhat below the arithmetic maximum. ## Height as a function of fanout A balanced tree of height h with fanout f reaches about `f^(h-1)` leaf pages, and each leaf itself holds many entries. Ignoring that extra leaf capacity for a conservative estimate: ``` height ≈ ceil( log_f(N) ) ``` With f = 500: | levels | keys addressable (approx) | |---|---| | 1 | 500 | | 2 | 250,000 | | 3 | 125,000,000 | | 4 | 62,500,000,000 | So three levels covers a hundred-million-row table and four levels covers tens of billions. This is the arithmetic behind the common statement that production B+trees are almost always 3-4 levels deep. ## Why the base of the logarithm is the whole story Every search structure on disk costs roughly one random page read per level. A binary search tree over one billion keys is ~30 levels — 30 potential random reads. A B+tree with fanout 500 is 4 levels. Same asymptotic class, wildly different constants: `log2(10^9) ≈ 30` versus `log500(10^9) ≈ 3.6`. The engine is trading CPU (binary search *inside* a 8 KB page, which is free relative to I/O) for a 10x reduction in page touches. That is the central design insight of disk-oriented indexing: make each page you pay for eliminate as much of the search space as possible. ## Consequences you can reason with in an interview **Lookup cost is effectively flat.** Because height moves logarithmically with a base in the hundreds, going from 10 million to 100 million rows usually does not add a level. The table has to grow by roughly the fanout factor to push the tree one level deeper. Meanwhile a full table scan's cost grows linearly. This is why index lookups stay cheap as data grows and scans do not. **Key width is a first-class cost.** Fanout is inversely proportional to entry size. Replace an 8-byte integer key with a 40-byte composite or textual key and fanout drops from ~500 to ~150; the tree may gain a level, and — more importantly — the entire index gets several times larger in pages, so much less of it fits in memory. **Page size shifts the tradeoff.** A larger page raises fanout and can shave a level, at the cost of reading and caching more bytes per access and more contention per page. Engines with 16 KB pages naturally reach higher fanout than ones with 4 KB pages. **Only the leaf level is proportional to row count.** The leaf level holds one entry per indexed row; every level above it is smaller by a factor of f. That means the internal levels together are roughly 1/f of the index size — under 1% for typical fanout. So the branch structure is tiny and stays resident in the buffer pool, while the leaf level is the part that may not fit in memory. ## Estimating on a whiteboard A clean way to answer aloud: "A page is 8 KB. My key plus pointer is about 16 bytes, so a node fans out to roughly 500 children. 500^3 is 125 million and 500^4 is 62 billion, so a billion-row table is a 4-level tree. A point lookup is 4 page accesses, of which the top 2-3 are cached, so realistically about one physical read plus the row fetch." That chain of reasoning — page size → entry size → fanout → powers → height → I/O — is exactly what the question is testing. ## Common trap Candidates sometimes say height is `log2(N)` because they are reasoning from binary trees, or claim height grows meaningfully as the table grows. Both miss the point: the base of the logarithm is in the hundreds, which is why B+tree depth is nearly a constant across every real-world table size.