Why Do B+ Trees Use Linked Leaf Nodes for Range Queries?

B+ trees store all data records in linked leaf nodes to minimize disk I/O operations and maximize cache locality during sequential range queries. By separating routing keys in internal nodes from actual data in the leaves, a B+ tree achieves a higher branching factor and shallower tree height. Once a search locates the starting key in a leaf node, the linked list structure allows the system to scan subsequent records sequentially without traversing back up and down the tree.

Separation of Routing Keys and Data Records

In a standard B-tree, internal nodes store both keys and pointers to data records (or the records themselves). Because each node has a fixed size—typically aligned with a disk page or block of size \(B\)—storing data payloads inside internal nodes reduces the number of keys and child pointers a single node can hold.

A B+ tree removes data records from internal nodes entirely, keeping only routing keys and child pointers. If a key has size \(k\) and a child pointer has size \(p\), an internal node of size \(B\) can hold a fanout (branching factor) of approximately:

\[m \approx \left\lfloor \frac{B}{k + p} \right\rfloor\]

Because \(m\) is much larger in a B+ tree than in a B-tree, the height of the tree, \(h = O(\log_m N)\) for \(N\) records, is significantly smaller. A shallower tree means fewer page reads are required to reach the leaf level for any initial lookup.

How Linked Leaf Nodes Optimize Range Queries

A sequential range query asks for all records with keys in an interval \([K_{\text{start}}, K_{\text{end}}]\). In a B-tree without linked leaves, finding the next key after \(K_{\text{start}}\) often requires traversing back up to parent nodes and descending into sibling subtrees, causing random I/O and repeated node visits.

In a B+ tree, every data record resides at the leaf level, and each leaf node contains a pointer to the next leaf node in sorted key order. Executing a range query follows a simple two-step process:

1. Point Lookup: Traverse from the root to the leaf node containing \(K_{\text{start}}\) in \(O(\log_m N)\) page reads.
2. Sequential Scan: Read records from the starting leaf and follow the leaf-to-leaf pointers until a key greater than \(K_{\text{end}}\) is reached.

If the range contains \(R\) matching records and each leaf node holds \(L\) records, the sequential scan requires only \(\lceil R / L \rceil\) additional page reads.

Hardware and Storage Alignment in Classical Computing

Classical computing architectures—whether using spinning hard drives (HDDs), solid-state drives (SSDs), or CPU caches—strongly favor sequential memory access over random access.

• Disk and SSDs: Reading contiguous or sequentially linked pages allows storage controllers and operating systems to perform read-ahead prefetching, amortizing seek and latency costs across many records.
• CPU Cache Efficiency: Because internal nodes contain only keys and pointers, more of the upper tree levels fit into RAM or CPU caches, keeping root-to-leaf traversals fast while leaf scans stream data predictable into memory.

By combining high-fanout internal nodes with a doubly or singly linked list at the leaf level, B+ trees remain the standard indexing structure for relational databases and file systems that rely on fast range scans.