In a B+-tree, why do records live only in the linked leaf level?

## Two variants of the same idea A classic B-tree stores a record wherever its key lives — including in interior nodes. A **B+-tree** makes one change with two large consequences: **all records live in the leaves**, interior nodes hold only separator keys and child pointers, and the leaves are linked into a sorted chain. ## Consequence one: interior pages become dense routers Fanout is page size divided by the size of one entry. In a classic B-tree an interior entry is `key + pointer + record`. If a record is 200 bytes and a key is 8, a 4 KB page holds around 19 entries. Strip the record out and the entry is `key + pointer`, about 16 bytes, so the same page holds around 250. The tree's height is log base fanout, so this is not a small constant factor — it is a change to the base of the logarithm, and at large `n` it typically removes a level or more from the descent. Since height is the fetch count, removing a level removes a device read from *every* lookup. A second, subtler benefit: interior pages are now small enough, in aggregate, that the top levels of a big index comfortably stay cached, so the bulk of real lookups touch storage only at the leaf. ## Consequence two: ordered iteration becomes sequential Take a concrete workload from an on-flash key-value store on an embedded device: export every reading whose timestamp falls between two bounds, where the qualifying records span thousands of pages. In a **classic B-tree** this is an in-order traversal. You visit an interior node, descend to a child subtree, come back up to read the next interior key, descend again. The access pattern interleaves levels and revisits interior pages; you either keep a stack of ancestors or re-descend from the root repeatedly. The pages you touch are scattered in whatever order the tree was built. In a **B+-tree** it is one descent to the leaf containing the lower bound, then "follow next-leaf pointer" until a key exceeds the upper bound. The interior levels are touched exactly once, at the start. Each qualifying leaf page is read exactly once, in key order, and because leaves are often allocated near-sequentially, the device sees something close to a sequential read — the access pattern storage is fastest at. The cost of the scan becomes (height) + (number of qualifying leaf pages), which for a large range is dominated entirely by the second term. This single property is why ordered on-disk indexes across mainstream relational engines and embedded key-value stores converged on the B+ variant rather than the classic one: the workloads that matter are not only "find this key" but "give me everything in this interval, in order." ## What the B+ variant gives up - **No early exit.** In a classic B-tree, a lookup that matches a key stored in the root finishes in one fetch. In a B+-tree, an interior key is only a routing separator — it may be a *copy* of a key that also appears in a leaf — so every point lookup descends the full height. This sounds worse than it is: with fanout in the hundreds, roughly (f-1)/f of all nodes are leaves, so early exit was a lucky accident on a tiny fraction of lookups. - **Duplicated key values.** A separator repeats a key that also exists below. That is a negligible space cost against the fanout gained. - **Chain maintenance.** Splitting a leaf must also patch the neighbour pointers, a small amount of extra bookkeeping. ## A useful way to hold it Think of a B+-tree as two structures stacked: a **sorted linked list of all records**, sitting underneath a **multi-level sparse index whose only job is to find the right entry point into that list quickly**. Everything above the leaves exists only to answer "where do I start?" in a handful of fetches; everything the query actually returns comes from the list. That decomposition explains both properties at once — routing is cheap because routers carry nothing but keys, and scanning is cheap because the data layer is already a list in key order. ## Recognising when it is the right shape The B+ layout pays whenever the workload is ordered: interval queries, sorted exports, cursor-style paging through results, or anything that needs "the next key after this one." It pays much less when the workload is purely point lookups on an exact key, where a structure that gives up ordering entirely — a hash-based index — answers in expected constant time regardless of `n`. The reason ordered indexes stay the default is that giving up ordering also gives up every range query, and most real workloads have at least one.