A strong answer
Storage is read in pages of several kilobytes, and a page read costs thousands to millions of times more than a comparison. A binary tree over a billion keys has about thirty levels, each potentially a separate page read. The cost that matters is page reads, not comparisons.
A B-tree makes each node a page holding hundreds of sorted keys and child pointers. Search binary-searches inside the node, then follows one child, so the height is about log base B of n: with 500 keys per page, three levels hold 125 million keys and four hold over 60 billion. The top levels are small and stay cached, so a lookup usually reads one or two pages from storage.
Inserts go into a leaf; a full leaf splits, pushing its middle key into the parent, and splits can cascade. When the root splits, a new root is created above it, so the tree grows at the top and all leaves stay at the same depth, with no rotations. Deletes borrow from or merge with siblings.
Databases use B+ trees: records live only in leaves, internal nodes hold routing keys for higher fan-out, and leaves are linked, so a range query descends once and then reads consecutive leaves. That is also why an index on (a, b) serves queries on a, or a and b, but not b alone. The same idea helps in memory, because a wide node costs one or a few cache misses.
What the interviewer is listening for
- Page reads as the cost model, and fan-out reducing height.
- Splits and growth at the root.
- B+ tree leaves and range scans.
Common mistakes
- Arguing in terms of comparisons only.
- Describing B-trees as binary trees stored on disk.
- Forgetting the cached upper levels in the cost estimate.