Which operation benefits most dramatically from the linked leaf nodes in a B+…

In a B+ tree, every actual data record (or record pointer) is stored only at the leaf level; internal nodes hold only separator or routing keys, which may repeat leaf keys but exist purely to guide the search downward. The leaf nodes are additionally chained together in a sequential linked list, separate from this internal index structure. This leaf-level linked list is what lets a program move from one leaf to the very next leaf directly, without re-descending from the root through the internal nodes.

1. A successor lookup needs the entry that comes immediately after a given key in sorted order.

2. Once the leaf holding the given key is known, the next entry can be read directly: it is either the following entry within the same leaf, or, if the given key is the last entry in its leaf, the first entry of the adjacent leaf reached through the leaf's linked-list pointer.

3. This turns a "move to the next key" step into a single pointer hop (O(1) amortized), rather than needing to re-locate that position by searching again from the root of the tree.

4. By contrast, exact key search always performs a fresh root-to-leaf descent guided by separator keys, and never uses the leaf-to-leaf pointers to complete the search. Parent node splitting, an internal node dividing on insertion overflow, is handled purely through the internal-node hierarchy and does not rely on the leaf-level links at all. Structural rebalancing after a deletion, redistributing entries between sibling leaves or merging two leaves, may need to update the surviving neighboring leaf's linked-list pointer as routine bookkeeping when a leaf is removed via a merge, but its own cost comes from the redistribution or merge logic itself, not from walking the leaf chain; it gains no traversal speed-up from the linked list the way a successor lookup does.

This matches the standard justification for choosing B+ trees over plain B-trees for range or sequential access: a plain B-tree has no leaf-level linked list, so without maintaining extra parent or path information, moving from one key to the next typically means re-locating that position through the internal-node structure rather than following a direct pointer. Successor and range-style traversal are the operations whose own per-step cost is most directly reduced by following that leaf-linked list; the other three operations either do not use it at all or only perform incidental pointer bookkeeping on it, rather than gaining a genuine per-step speed benefit from it.

Therefore, the operation that benefits most dramatically from the linked leaf nodes in a B+ tree is successor lookup.