If a B-tree index fits entirely in RAM, does its high fanout still pay off?
answer
- fanout was a consequence, not a goal
- what unit does the hardware move data in?
- that unit is much smaller in memory
- trace a binary search inside a 500-key node
- node size should track the transfer unit
basics
~20 sNot at the same node size. High fanout was never valuable in itself — it matched node size to the storage transfer unit. In memory that unit shrinks from a page to a cache line, so the right node holds tens of keys, not hundreds.
solid answer
~60 sThe justification for fanout in the hundreds is that a device hands you a whole page whether you want one key or five hundred, so you make the node a page. Move the index into memory and that argument does not disappear, it re-scales: the expensive event becomes a cache miss and the transfer unit becomes a cache line of tens of bytes, so the node that fills one unit holds a handful of keys, not hundreds. A 500-key node in memory is actively wasteful — a binary search inside it probes about nine scattered positions, most of them in different lines, so you pay roughly a miss per probe and lose the advantage. The structure is still a reasonable choice, because it keeps ordered iteration and range scans that a hash index cannot offer, but you re-tune the node size to the new cost model. And if the index must still be durably persisted and reloaded in page units, keep the page-shaped layout regardless of where it currently lives.
go deeper
Know that a B-tree node is sized to match the chunk of data the hardware moves at once, and that this chunk is much smaller for memory than for storage.
Explain the mechanism: node size tracks the transfer unit, so moving from pages to cache lines shrinks the ideal node from hundreds of keys to a handful.
Show you would trace a binary search inside a large node and count the distinct lines it touches, then re-tune node size rather than switching structures reflexively.
Own the decision under constraints: durability requirements, projected growth past the memory ceiling, and whether the workload needs ordered access at all usually decide this before any micro-benchmark does.
## The principle being tested This is a cost-model question wearing a data-structure costume. The interviewer wants to know whether you learned "B-trees have high fanout" as a fact or as a *consequence*. The consequence chain is: the hardware moves data in fixed-size units, a fetch of one unit costs the same whether you use one byte of it or all of it, therefore make the node exactly one unit so no fetch is wasted. Fanout is the output of that reasoning, not an input. Change the hardware, and the same reasoning produces a different number. ## What actually changes when the index becomes memory-resident | | on storage | in memory | |---|---|---| | expensive event | page fetch from the device | cache miss to main memory | | transfer unit | 4 KB - 16 KB page | one cache line, tens of bytes | | cost ratio to a comparison | 10^3 - 10^6 | 10^1 - 10^2 | | node size that fills one unit | hundreds of keys | a handful of keys | Two things move at once. The unit shrinks by two to three orders of magnitude, and the penalty for missing it shrinks too. Both push in the same direction: smaller nodes, and much less reason to contort the structure around the transfer unit at all. ## Why a page-sized node is actively bad in memory Consider a node holding 500 sorted keys and the standard binary search over it. Those probes land at positions 250, 125, 62, and so on — scattered addresses within the node. Each early probe lands in a different line, so you pay something close to one miss per probe, about nine misses to traverse a single node. A four-level tree then costs roughly 36 misses. A balanced binary search tree over the same data has height about 30 and costs about 30 misses. The page-shaped tree has stopped winning, because the property it was exploiting — that one expensive fetch delivers all 500 keys usefully — no longer holds when the fetch granularity is a line rather than a page. The fix is not to abandon the family but to re-tune it: nodes sized to a small multiple of a cache line, keys laid out so the search touches few distinct lines, and a linear scan rather than a binary search inside a node once it is small enough that scanning is cheaper than jumping around. This family of designs is exactly what the crossover produces, and it is why "in-memory ordered index" and "on-disk ordered index" look different even though both are B-tree descendants. ## What does *not* change Three things argue for keeping the on-disk shape even when everything currently fits in memory: 1. **Durability.** If the index must survive a restart, it has to be written and read back in page units. Maintaining one page-shaped layout that is both the persistent format and the in-memory format is far simpler than maintaining two representations and converting between them. 2. **"Fits in memory" is a claim about today.** Data sets grow. A structure tuned for cache lines that spills to storage degrades badly, because every node fetch then wastes most of a page. The page-shaped structure degrades gracefully. 3. **Ordered access.** Whatever you tune, do not give up the leaf-level ordering unless the workload has no range or cursor queries at all. A hash-based index answers point lookups in expected constant time and beats any tree for that one operation, but it cannot answer "everything between these two bounds" without a full scan. ## How to actually answer this in an interview A strong answer does three things. It names the mechanism rather than the folklore: node size tracks the transfer unit. It gives the direction and the rough magnitude of the change: the unit shrinks from kilobytes to tens of bytes, so node size shrinks by a similar factor. And it refuses to answer the question as pure theory — the real determinant is whether the index must be persisted, whether the data set will stay memory-resident at 10x, and whether the workload needs ordered access at all. If those three answers are "yes, no, yes," you keep the page-shaped tree even though it is currently memory-resident, and you say so with the reason attached. The failure mode to avoid is treating asymptotic notation as the arbiter. Both variants are O(log n) lookups. The entire question lives in the constant factor and in which operation the constant is counting, which is precisely why the medium decides it and the notation cannot.
- Once everything is in memory, would a hash-based index simply be better?For point lookups, yes — expected constant time beats any logarithm, and there is no descent at all. But it gives up exactly what the ordered structure was built for: interval queries, sorted iteration and cursor-style paging all become full scans. Choose the hash index only if you can show the workload has no ordered access, and remember its worst case degrades under adversarial or heavily colliding keys.
- What measurement would actually settle the node-size question for your workload?Benchmark the real key size, key distribution and data-set size at several node sizes, measuring lookup and scan latency together with cache-miss counts, not just operation counts. Asymptotics are identical across the candidates, so the answer lives entirely in constants that only measurement on the target hardware reveals.
saying these in an interview costs you the question
- says fanout is always better, so keep it in memory
- claims memory is random access so layout does not matter
- compares the options by big-O when both are O(log n)
- forgets the index may still need durable page-shaped persistence
- assumes today's fit in memory holds after 10x growth