What distinguishes a B+tree from a classic B-tree, and why do relational storage engines almost always choose the B+tree variant for table indexes?

## The two structures side by side Both are balanced, multi-way, page-oriented search trees. The difference is what the nodes hold. **Classic B-tree.** Each node holds a sorted run of *(key, payload)* pairs interleaved with child pointers. The payload might be the row itself or a row pointer. A search compares against keys as it descends and can stop the moment it finds the key — possibly at the root. **B+tree.** Internal nodes hold only *separator keys* and *child pointers*; no payload at all. Every key that exists in the index also appears in a leaf, together with its row pointer. A search therefore always descends the full height, even if the search key matches a separator on the way down. Leaves are chained left-to-right (often doubly), forming a sorted list of the entire key space. A separator in a B+tree does not even need to be a real key value — it only has to divide the key space — so engines can store abbreviated or synthetic separators (for example, the shortest byte prefix that distinguishes two subtrees). ## Why B+tree wins on disk **Higher fanout, shallower tree.** Node size is fixed at one page. If each internal entry must also carry payload, fewer entries fit, so the branching factor drops and the tree grows taller. Since the dominant cost of a lookup is the number of pages touched, anything that raises fanout is the single most valuable optimization available. Stripping payload out of the internal levels is exactly that. **Predictable cost.** Every lookup costs the same number of page accesses because every lookup ends at a leaf. This uniformity makes the optimizer's cost model simple and makes latency stable, which operationally matters more than an occasional lucky early hit at an upper level. **One sorted level for everything.** All keys are in the leaf level, in order, with sibling links. That makes ordered access a linear walk over leaves. In a classic B-tree the sorted sequence is spread across all levels, so ordered traversal is a full in-order walk that continually re-visits internal nodes — far more random and far more page touches. **Tiny, cacheable branch structure.** With payload removed, the internal levels together are roughly `1/fanout` of the index size — well under one percent. Those pages stay pinned in the buffer pool in practice, so the top of the descent costs no I/O at all and only the leaf access tends to be physical. **Uniform maintenance.** Because payload only ever moves between leaves, splits and merges have simpler invariants: the internal levels only ever gain or lose separators. In a B-tree, splitting a node that carries payload means relocating payload upward, which complicates concurrency control and recovery. ## What the B+tree gives up The honest tradeoff is the lost early exit. In a B-tree, a small fraction of lookups terminate above the leaf level. But that fraction is roughly the share of keys stored above the leaves, which for high fanout is under one percent — and those top pages are cached anyway, so the saved access is usually a memory hit, not a disk read. Trading a sub-1% early-exit chance for a several-fold increase in fanout is not a close call. Some engines also blur the line: a B+tree variant may store the row itself in the leaf (an index-organized or clustered table) rather than a pointer, which is a decision about leaf payload, not about the B-tree/B+tree distinction. ## How to phrase it in an interview "Classic B-tree: keys and payload in every node, search can stop early. B+tree: payload only in leaves, internal nodes are pure separators, leaves are linked in sorted order. Engines choose B+tree because removing payload from the branch levels maximizes fanout and therefore minimizes tree height and page reads, keeps the entire branch structure small enough to stay cached, and puts every key in one sorted linked level so ordered access is a leaf walk." ## Naming caveat In everyday speech, "B-tree index" almost always means a B+tree — engine documentation and even index-type names use "btree" loosely. If an interviewer asks the difference, they are testing whether you know the distinction exists, not trying to catch you out on vocabulary. Say the distinction, then note that the common term refers to the B+tree variant.