Why does a B-tree with fanout 500 beat a balanced binary tree for on-disk lookup?
answer
- ask what one lookup step actually costs
- the device hands you a whole page
- height is the base of which logarithm?
- 500 to the fourth power versus 2 to the thirtieth
- count fetches; in-page work is nearly free
basics
~20 sBecause the cost unit is page fetches, not comparisons. Each B-tree node fills one storage page, so four fetches reach tens of billions of records at fanout 500, while a balanced binary tree needs about thirty separate pointer chases.
solid answer
~40 sOn storage, the expensive operation is fetching a page; work done on a page already in memory is nearly free. A B-tree node is sized to one page, so a node holding ~500 keys resolves log2(500) is about 9 bits of the search per fetch instead of 1. Height is log_fanout(n): 500^4 is over 60 billion, so a point lookup on a billion-record on-flash key-value store is about four page reads, and the top levels are usually already cached, so often only one or two actually hit the device. A balanced binary tree over the same data has height about 30, and each of those 30 nodes is on a different page, so it is roughly 30 device reads. Total key comparisons are similar in both; the fetch count is what changed.
go deeper
Be ready to state the two heights out loud: about 30 levels for a balanced binary tree over a billion records, about 4 for a B-tree with fanout in the hundreds. Say that each level costs a fetch from storage.
Explain where the fanout number comes from — page size divided by key plus pointer size — and show that comparison counts stay near log2(n) either way, so the saving is in I/O, not in comparisons.
Show you reason about the real steady state: the top levels stay cached, so the measured read count is well below the height. Be able to say what makes the height bound guaranteed rather than lucky.
Own the framing that a data structure is only fast relative to a cost model, and that the model belongs to the hardware. Be ready to say what would have to change about the storage tier before you would revisit the choice.
## The question behind the question An interviewer asking this is checking whether you can switch cost models. Almost every complexity claim you learned in an algorithms course counts *comparisons* or *pointer dereferences*, all priced at one unit. A B-tree only makes sense under a different price list: the unit that costs is a **transfer of one block between storage and memory**, and everything you do to a block you already hold costs approximately nothing by comparison. A device read is on the order of tens of microseconds on flash and milliseconds on a spinning disk; a comparison between two keys already in memory is nanoseconds. The gap is three to six orders of magnitude, so the algorithm that wins is the one that minimises fetches, even if it does slightly more arithmetic. ## What fanout actually buys Storage hardware does not hand you one key; it hands you a whole page, typically 4 KB or 16 KB. If your node is a binary tree node with two child pointers and one key, you pull 4 KB off the device and use about 24 bytes of it. The rest of the page is wasted bandwidth. A B-tree node is deliberately sized to fill that page. With 8-byte keys and 8-byte child pointers, a 4 KB page holds on the order of 250 separators; a 16 KB page holds on the order of a thousand. Call it a fanout of *f*. The tree's height is then ceil(log_f(n)) rather than log2(n), and because *f* is in the hundreds, the logarithm collapses: | structure | fanout | height at n = 1,000,000,000 | device reads per lookup | |---|---|---|---| | balanced binary tree | 2 | ~30 | ~30 | | B-tree | 500 | 4 (500^4 > 6 x 10^10) | ~4, fewer once cached | That is the whole trick: **height is the read count, and fanout is the base of the logarithm.** ## Comparisons are not the story, and saying they are is the classic wrong answer A very common wrong answer is "B-trees are faster because they do fewer comparisons." Work it out. Inside each 500-key node you still have to locate the right child, and a binary search over 500 sorted separators costs about log2(500) is about 9 comparisons. Four levels times nine is roughly 36 comparisons — slightly *more* than the balanced binary tree's ~30. The comparison count is essentially unchanged, because information-theoretically you still need about log2(n) bits to isolate one record out of n, however you package them. What changed is *where* those bits are bought. The binary tree buys one bit per device read. The B-tree buys nine bits per device read, because a page fetch delivers 500 separators at once and the comparisons that consume them are free. Fanout does not reduce the total information needed; it raises the information yield per unit of I/O. ## Why the height bound is guaranteed, not hoped for A B-tree is not merely "a tree with wide nodes." It enforces two invariants that make the height bound real: every node except the root holds at least a minimum number of keys (so no node degenerates into a near-binary node), and every leaf sits at exactly the same depth. Without the minimum-occupancy rule, a tree of 500-key nodes each holding a single key would be a binary tree wearing a costume, and the read count would be back to ~30. ## Where the top of the tree lives In practice a four-level index does not usually cost four device reads. Consider that with fanout 500, the root is one page, level two is 500 pages (a couple of megabytes), and level three is 250,000 pages. A modest cache holds the top two levels permanently, so the steady-state cost of a lookup is one or two real reads. This is also why an interviewer may follow up with "why do your measurements not match your arithmetic" — the arithmetic gives the worst case, the cache gives the common case. ## Where it stops paying Fanout cannot be raised indefinitely. Beyond a page, a larger node means transferring bytes you will not look at, and the in-node search grows too. The right node size is the one that matches the device's efficient transfer unit — which is exactly why the answer changes when the medium changes, for example when the whole index becomes memory-resident and the meaningful transfer unit shrinks from a page to a cache line.
- Where does a fanout number like 500 actually come from?From arithmetic on the page: fanout is roughly page size divided by the size of one separator key plus one child pointer. A 4 KB page with 8-byte keys and 8-byte pointers gives a few hundred; a 16 KB page with the same entries gives around a thousand. Wider keys shrink it, which is one concrete reason long composite keys make an index taller.
- You predicted four reads per lookup but measured closer to one. Why?The upper levels are tiny and hot. With fanout 500 the root is a single page and the second level is only a few hundred pages, so both stay resident in any cache after a handful of queries. Only the deepest level or two ever reaches the device in steady state. Four is the cold worst case, not the typical cost.
- Does the same reasoning apply to flash, where there is no seek time?Yes, though for a different reason. Flash has no mechanical seek, but it is still addressed in pages and every access crosses a bus with fixed per-request overhead, so a request that returns 4 KB of useful separators beats thirty requests that each return one key. The gap is narrower than on a spinning disk but still large enough that high fanout wins.
Walking to the filing cabinet is the expensive part, not reading a folder. So you put five hundred folders in each drawer and open four drawers, instead of thirty drawers holding one folder each.
saying these in an interview costs you the question
- B-trees are fast because they do fewer comparisons
- treats every node visit as one unit regardless of storage medium
- calls a B-tree lookup O(1) because the tree is shallow
- assumes fanout can be raised without limit for free
- says a B-tree is just a balanced binary tree with extra children