B+ Tree range queries across pages

WHAT THIS TESTS The interviewer checks whether you know why B+ Trees, not plain B-Trees, dominate databases and how that structure makes range scans efficient against block storage.

A GOOD ANSWER COVERS A B+ Tree maps each node to a disk page. Internal nodes store only separator keys and child pointers, no row data, so a single page holds many keys, giving a high fan-out and a very shallow tree, often three or four levels even for billions of rows; that bounds the number of page fetches for any lookup. All actual data or row pointers live exclusively in the leaf level, and the leaf pages are linked together in sorted order, typically as a doubly linked list. To run WHERE id BETWEEN 100 AND 200, the engine starts at the root page, compares keys, follows the child pointer toward 100, descends level by level faulting each needed page into the buffer pool, and reaches the leaf page containing 100. From there it reads matching entries on that leaf, then follows the leaf link pointer to the next leaf page, continuing to read sequentially across linked leaves until it encounters a key above 200, then stops. It never returns to the root for subsequent rows.

COMMON WRONG ANSWERS Saying it re-descends from the root for each row, which would be far slower. Confusing B+ Tree with B-Tree by putting data in internal nodes. Forgetting the leaf-level linked list that enables sequential range scans. Ignoring that nodes are pages cached in the buffer pool.

LIKELY FOLLOW-UPS Why is fan-out important for tree height; how does the leaf linkage help ORDER BY; what is the difference from a B-Tree; how many page reads for a point lookup.

ONE CONCRETE EXAMPLE For a billion-row table a B+ Tree might be four levels deep. The BETWEEN query reads four pages descending to the leaf holding id 100, then streams along linked leaf pages reading consecutive ids, faulting each new leaf page from disk only once, until it passes 200, returning the range with a handful of page reads rather than scanning the table.