For a point lookup through a four-level B+tree index, how many physical disk reads would you actually expect, and how do you reason about that with an interviewer?
answer
- Logical accesses ≠ physical reads
- Internal levels ≈ 1/fanout of index → always cached
- Real I/O sites: leaf page + row fetch
- Warm: 0-2 reads; cold: up to h+1
- Capacity question = leaf-level bytes vs buffer pool
basics
~20 sFour levels means four logical page accesses, but the root and upper internal levels are tiny and stay cached, so typically only the leaf access — and then the row fetch — can be physical. Expect roughly zero to two real reads on a warm cache.
solid answer
~60 sSeparate **logical page accesses** from **physical reads**. A four-level tree means four logical accesses to reach the leaf, plus one more to fetch the row if the index does not already contain the needed columns. But the levels are wildly different in size. With fanout ~500, level counts are 1 root, ~500, ~250k, and ~125M entries at the leaves. All the internal levels together are about `1/fanout` of the index — well under 1%. That fraction is hot on every single lookup, so it stays resident in the buffer pool essentially permanently. So on a warm system: the top three levels are memory hits, the leaf may or may not be cached depending on how the leaf level compares with available memory, and the row fetch is a separate random read. Realistic answer: **0-2 physical reads**, commonly 1-2 for a large table with a cold leaf level. On a cold cache it is up to 5. Sizing conversations should be about how much of the *leaf level* fits in memory, not about level count.
go deeper
Know that the tree height is the number of pages consulted and that the top levels are usually already in memory.
Separate logical accesses from physical reads and identify the leaf page plus the row fetch as the two places I/O really happens.
Give a range with explicit assumptions, justify why branch levels stay pinned using the 1/fanout argument, and connect it to buffer-pool sizing.
Turn it into a capacity model — working-set size versus memory, skew, and the wider-entry-versus-fewer-fetches tradeoff — rather than a per-query number.
## The two cost currencies When reasoning about index cost, keep two numbers apart: - **Logical page accesses** — how many pages the traversal must consult. For a height-h tree this is h, plus one for the row fetch if needed. It is deterministic and comes straight from the structure. - **Physical reads** — how many of those accesses miss the buffer pool and hit storage. This depends on memory size and access skew, and it is what latency actually tracks. Candidates who conflate the two either wildly overestimate index cost ("four levels means four disk seeks") or wildly underestimate it ("indexes are always fast"). ## Why the upper levels are effectively free Level sizes shrink by a factor of the fanout going up. With f ≈ 500 and a billion-row index: | level | pages (approx) | size at 8 KB/page | |---|---|---| | root | 1 | 8 KB | | level 2 | ~500 | 4 MB | | level 3 | ~250,000 | 2 GB… | — careful: level 3 here is the level just above the leaves, and the leaf level itself holds one entry per row. The key structural fact is that **all internal levels together are roughly `1/f` of the index**, under one percent. That tiny slice is touched by *every* lookup, so any reasonable cache-replacement policy keeps it resident. Treat the descent above the leaf as memory-speed. ## Where physical I/O actually occurs Two places: 1. **The leaf page.** The leaf level has one entry per row, so its size is proportional to the table's row count. Whether a leaf access is physical is a function of `leaf-level bytes` versus `available buffer pool` and how skewed the access is. A hot subset (recent orders, active users) may be fully cached even when the whole leaf level is not. 2. **The row fetch.** Unless the index contains every column the query needs, the engine must follow the row pointer to the table itself — an additional random access to a different page. Under clustered storage a secondary index lookup instead re-descends the primary index, which is a second traversal rather than a single page fetch. ## The realistic numbers - **Warm cache, hot key range:** 0 physical reads. Everything is in memory. - **Warm cache, cold key:** ~1 for the leaf, ~1 for the row → 1-2. - **Cold cache:** up to 5 (four levels plus the row). - **Cold, clustered secondary lookup:** more, because the row fetch is itself a tree descent. So "a point lookup costs about one or two reads" is the honest steady-state answer, and it is why index lookups are described as effectively constant-time in operational terms. ## Why this framing matters operationally It redirects capacity planning to the right variable. Level count barely moves with data growth, so it is not the thing to worry about. What moves is **leaf-level size relative to memory**. The practical questions become: - How large is the leaf level of the indexes on my hot query paths? - Does my working set (the actively-accessed subset) fit in the buffer pool, even if the whole index does not? - Are my keys wide enough to have inflated the leaf level unnecessarily? - Would including a couple of extra columns let the index answer the query outright and eliminate the row fetch — at the cost of a wider entry and a bigger leaf level? That last one is a genuine tradeoff: removing the row fetch saves a random access per row, but widening entries shrinks fanout and grows the index, so it can push the leaf level out of cache. Whether it wins depends on how many rows a typical query touches. ## Watching for the trap in the question Interviewers often ask this expecting the naive "four levels, four seeks" answer, then probe. The strong response leads with the distinction between logical and physical, explains the `1/f` argument for why upper levels are pinned, names the leaf level and the row fetch as the two real I/O sites, and gives a range rather than a single number — while stating the assumption (warm cache, table size versus memory) that the number depends on. ## One sentence to close with "Height tells me logical accesses; memory tells me physical reads — and because the branch levels are under one percent of the index and touched by every query, the only accesses that realistically go to storage are the leaf page and the row fetch."
- What would make even the leaf access reliably a cache hit?Access skew or a small enough leaf level. If queries concentrate on a hot key range — recent rows, active accounts — those leaf pages stay resident even when the full index does not fit, because cache replacement keeps what is actually touched. Alternatively, if the whole leaf level is smaller than the buffer pool, every leaf access is a memory hit by construction.
- How does making the index contain all the columns a query needs change this cost?It removes the row fetch, so the query is answered from the leaf page alone — typically saving one random access per qualifying row, which matters most for queries returning many rows. The cost is a wider index entry, which lowers fanout and grows the leaf level, so more of the index competes for cache. It is a good trade when a query touches many rows and a poor one when it adds substantial width for a single-row lookup.
A library's catalogue terminals sit by the door and are always available; the walk that costs you time is finding the shelf and then the book.
saying these in an interview costs you the question
- Saying a four-level tree means four disk seeks per lookup
- Claiming index lookups never touch disk because the index is cached
- Ignoring the row fetch after the index probe
- Sizing capacity around tree height instead of leaf-level bytes versus memory
- Giving a single confident number without stating cache-state assumptions