Which of the following best explains why B+ trees typically have smaller…

Concept

For a fixed-size disk page/node, the height of a B-tree or B+ tree is governed by its fan-out (the maximum number of children per node): height is approximately log base fan-out of N, for N keys. A B-tree keeps a data pointer/record alongside every key in every node (leaf and internal), while a B+ tree keeps data pointers only in leaf nodes - internal nodes store just keys and child pointers. Removing the data payload from internal-node entries lets more entries fit into the same fixed-size page, directly raising the fan-out of internal nodes.

Application

1. Assume one disk page can hold a fixed amount of space, say 100 units.

2. In a B-tree, each internal-node entry needs room for a key plus a child pointer plus a data/record pointer, so fewer entries fit per page - say 10 entries, giving fan-out approximately 11.

3. In a B+ tree, each internal-node entry needs room only for a key plus a child pointer (no data pointer), so roughly twice as many entries fit per page - say 20 entries, giving fan-out approximately 21.

4. For N = 1,000,000 keys, a B-tree with fan-out 11 needs about log base 11 of 1,000,000, approximately 5.8, i.e. 6 levels, while a B+ tree with fan-out 21 needs about log base 21 of 1,000,000, approximately 4.6, i.e. 5 levels.

5. The B+ tree therefore reaches every key in one fewer disk-page access on average - a direct consequence of its internal nodes carrying only keys.

Cross-check

The general height formula for any multiway search tree is height approximately log base fan-out of N; since fan-out is the only variable that changed in this comparison (both structures index the same N keys), a strictly larger fan-out must produce a strictly smaller or equal height. This confirms that internal nodes storing only keys - and thereby allowing a higher fan-out - is the mechanism behind a B+ tree's smaller height, and is consistent with why B+ trees, not B-trees, are the standard choice for filesystem and database indexes, where minimizing disk-page reads per lookup matters most.