B+-Tree Indexes

A B+-tree is a balanced, multiway search tree structure used to implement a database index. It generalizes the binary search tree in two essential ways. First, each node can have many children — an order $n$ node holds between $\lceil n/2 \rceil$ and $n$ pointers (with the root exempted from the lower bound), so a single node routes search among up to $n-1$ keys rather than just 2. Second, the tree is height-balanced by construction: every leaf sits at exactly the same depth, so there is no notion of "left-heavy" or "right-heavy" subtrees to fix — balance is maintained automatically by the split and merge rules described below. The defining structural choice of the B+-tree, as opposed to a plain B-tree, is that all actual record pointers (or records) live only in the leaves. Internal (non-leaf) nodes store copies of key values purely to steer search; they carry no data pointers of their own. Consequently the leaf level is a complete, sorted, dense index over the search key — every distinct key value that exists in the file has an entry in some leaf — and the internal levels above it form a hierarchy of sparse directories that guide you to the right leaf in $O(\log_F N)$ steps. Leaves are additionally linked together in key order via sibling pointers, forming a doubly- or singly-linked list across the bottom of the tree. This is what makes range queries ("all keys between $a$ and $b$") efficient: locate the leaf containing $a$, then walk sibling pointers forward, never re-visiting internal nodes. Two structural invariants define correctness precisely. (1) Search-key ordering invariant: within every node, keys are stored in strictly increasing order, and for every internal node with keys $K_1 < K_2 < \dots < K_{m}$ and child pointers $P_0, P_1, \dots, P_m$, every key in the subtree rooted at $P_i$ satisfies $K_i \le \text{key} < K_{i+1}$ (with the obvious boundary conventions at $P_0$ and $P_m$). (2) Occupancy invariant: every node except the root has between $\lceil n/2 \rceil$ and $n$ children (equivalently, between $\lceil n/2 \rceil - 1$ and $n - 1$ keys), guaranteeing the tree never becomes pathologically sparse and its height stays logarithmic in the number of records. These two invariants together are what every insertion and deletion algorithm must preserve.

Node layout

A leaf node of order $n$ holds up to $n - 1$ (key, pointer) pairs, where the pointer is either the record itself, a pointer to the record on disk, or (for a non-clustering index) a pointer to a bucket of record pointers when duplicates exist. The last slot in a leaf is reserved for the pointer to the next leaf in key order. An internal node of order $n$ holds up to $n - 1$ keys and up to $n$ child pointers, alternating pointer, key, pointer, key, …, pointer. The order $n$ is chosen so that one node occupies exactly one disk block — if a block holds 4 KB and each (key, pointer) pair takes about 16 bytes, then $n \approx 250$, giving very high fanout.

Search

Searching for a key $K$ starts at the root and descends exactly one level per comparison step, using the routing invariant to pick the correct child, until a leaf is reached. ``` function SEARCH(node, K): if node is a leaf: scan node's keys for K if found: return the associated record pointer(s) else: return NOT_FOUND else: // internal node with keys K_1 < ... < K_{m}, children P_0 .. P_m find smallest i such that K < K_i // K_{m+1} = +infinity child <- P_i read child from disk return SEARCH(child, K) ``` For a range query `[low, high]`, first locate the leaf containing `low` via `SEARCH`, then follow the leaf's next-pointer chain, emitting matching entries, until a key exceeds `high` or the chain ends.

Insertion

Insertion first performs a search to locate the target leaf, inserts the new (key, pointer) entry in sorted position, and then repairs any resulting overflow by splitting — possibly cascading the split upward. ``` function INSERT(tree, K, recordPointer): leaf <- FIND_LEAF(tree.root, K) // descend as in SEARCH insert (K, recordPointer) into leaf in sorted order if leaf.numKeys <= n - 1: return // fits, done // leaf overflow: split into two leaves newLeaf <- new leaf node move the ceil(n/2) largest entries of leaf into newLeaf newLeaf.next <- leaf.next leaf.next <- newLeaf splitKey <- smallest key in newLeaf // COPIED up, stays in newLeaf too INSERT_IN_PARENT(tree, leaf, splitKey, newLeaf)

function INSERT_IN_PARENT(tree, left, key, right): if left is the root: newRoot <- new internal node with children [left, key, right] tree.root <- newRoot return parent <- PARENT_OF(left) // known from the descent, or via parent pointers insert (key, right) into parent immediately after left's pointer if parent.numPointers <= n: return // parent fits, done // internal node overflow: split, but push the middle key UP (do not copy it) newInternal <- new internal node mid <- the middle key of parent's (n) keys move all keys/pointers to the right of mid into newInternal remove mid from parent (it moves up, not duplicated) INSERT_IN_PARENT(tree, parent, mid, newInternal) ``` Two subtleties matter here. In a leaf split, the split key is copied up to the parent, because the key must still physically remain in the leaf level to keep the dense leaf index complete. In an internal-node split, the middle key is moved up, not copied, because internal nodes are pure routing structures with no obligation to retain every key at every level. If the split propagates all the way past the root, the tree gains exactly one new level — this is the only way a B+-tree grows in height, and it happens only when literally every node on the path from a leaf to the root was already full.

Deletion

Deletion is the mirror image: locate the leaf, remove the entry, and if the node falls below the minimum occupancy, either redistribute (borrow) from a sibling or merge with a sibling, propagating the fix upward if necessary. ``` function DELETE(tree, K): leaf <- FIND_LEAF(tree.root, K) remove (K, pointer) from leaf if leaf is the root or leaf.numKeys >= ceil(n/2) - 1: return // still legal, done sibling <- an adjacent sibling of leaf (via parent) parent <- PARENT_OF(leaf) if sibling has more than the minimum number of keys: // redistribute: borrow one entry from sibling move one entry from sibling into leaf (from the near end) update the separating key in parent to reflect the new boundary return else: // merge leaf and sibling into one node merge all entries of leaf and sibling into one leaf update sibling-chain (next) pointers to skip the removed leaf remove the pointer to the deleted leaf and its separating key from parent DELETE_ENTRY_FIXUP(tree, parent)

function DELETE_ENTRY_FIXUP(tree, node): if node is the root: if node has only one child left: tree.root <- that one child // tree shrinks by one level return if node.numPointers >= ceil(n/2): return // still legal, done sibling <- an adjacent sibling of node parent <- PARENT_OF(node) if sibling has more than the minimum number of pointers: // redistribute: rotate one key/pointer through parent move one child pointer from sibling into node, pulling the appropriate separating key down from parent and pushing a new separating key up into parent return else: // merge node and sibling, pulling the separating key down from parent merge node, the parent's separating key, and sibling into one node remove the pointer to node (or sibling) and the separating key from parent DELETE_ENTRY_FIXUP(tree, parent) ``` Notice the asymmetry with insertion: leaf merges do not pull a key down from the parent (leaves store their own keys and the merge simply concatenates two sorted key lists), but internal-node merges do pull the separating key down, because that key was only present in the parent, not duplicated in the children. This mirrors the copy-up-vs-move-up asymmetry seen in insertion.

Height. Let $F$ be the minimum fanout guaranteed at every non-root level, i.e. $F = \lceil n/2 \rceil$. Since every non-root node has at least $F$ children, a tree of height $h$ (root at level 0, leaves at level $h$) has at least $F^{h-1}$ leaves below the root's children, hence at least $2F^{h-1}$ leaves counting the root's own fanout of at least 2. If there are $N$ records distributed dense-index style across the leaves, this forces

With $n \approx 200$ (order in the low hundreds, typical for 4–8 KB blocks and small keys), $F \approx 100$, and $\log_{100}(10^9) \approx 4.5$, meaning even a billion-row index needs only about 4–5 levels. This is the entire reason B+-trees dominate disk-backed indexing: each level is one disk I/O, so search cost is $O(\log_F N)$ I/Os, not $O(\log_2 N)$.

Search cost. `SEARCH` reads exactly one node per level, doing $O(\log n)$ in-memory comparisons per node (binary search within the block, since keys are sorted) but only one disk I/O per level. Total: $O(\log_F N)$ I/Os and $O(\log_F N \cdot \log n)$ CPU comparisons — I/O dominates in practice, so we simply say search is $O(\log_F N)$.

Insertion cost. Locating the leaf costs $O(\log_F N)$ I/Os, identical to search. In the worst case, insertion triggers a chain of splits from the leaf up to the root, but each split is a local, constant-time operation (redistributing at most $n$ entries between two nodes and updating one parent pointer), and there are at most $h = O(\log_F N)$ such splits, one per level. So insertion is $O(\log_F N)$ I/Os in the worst case, and importantly $O(1)$ amortized splits in practice, since a split only happens when a node was already completely full — most insertions cause zero splits.

Deletion cost. Symmetric: locating and removing the entry costs $O(\log_F N)$ I/Os, and at most one merge-or-redistribute operation per level propagates upward, again $O(\log_F N)$ in the worst case.

Correctness argument. The two invariants stated earlier — sorted-key routing and bounded occupancy $[\lceil n/2\rceil, n]$ per node — are exactly what every split and merge preserves, and this is provable by induction on the operations.

• Split preserves routing: a split partitions a node's keys into a "low" half and a "high" half at a well-defined boundary key; the parent gets exactly that boundary key inserted at the correct position, so every subsequent search still routes correctly, by construction of `INSERT_IN_PARENT`.
• Split preserves occupancy: splitting a node with $n$ keys (just over the max of $n-1$) into two nodes each holding roughly $n/2$ keys leaves both new nodes at or above $\lceil n/2\rceil - 1$, satisfying the lower bound, and clearly at or below $n-1$, satisfying the upper bound.
• Merge/redistribution preserves occupancy symmetrically: a node can only underflow after a single deletion, so it holds at least $\lceil n/2\rceil - 2$ keys before the fix; redistribution or merging with a sibling (itself holding at least $\lceil n/2 \rceil - 1$ keys) restores both nodes (or the single merged node) to a legal range, which can be checked by the arithmetic bound $n - 1 \ge (\lceil n/2\rceil - 1) + (\lceil n/2\rceil - 1)$ for merges not to overflow.
• Height only changes at the root, and only by one: a new root is created only when the previous root itself splits (insertion), and the root shrinks only when it is reduced to a single child (deletion). Both events are detected explicitly in the algorithms above, so height changes are the unique, controlled exception to "all other nodes stay within bounds," and they never cascade — one insertion or deletion changes height by at most one level.

Because these invariants hold after every single operation, they hold after any sequence of operations by induction, which is exactly why the tree never needs a global rebalancing pass: all rebalancing is local to the path from the modified leaf to the root, bounding the work per operation by the tree's height.

Honest tradeoffs. Space utilization is only guaranteed to be at least $50\%$ per node in the worst case (right after a split, nodes can be roughly half full); in practice, sequential insertion patterns and bulk-loading achieve much higher utilization, often 67–100%. Also, `INSERT_IN_PARENT` and `DELETE_ENTRY_FIXUP` require knowing each node's parent; real systems either store parent pointers, or (much more commonly) retain the root-to-leaf path from the initial descent in memory to avoid a second traversal. Finally, the B+-tree assumes an ordering on the search key — it does not help with multidimensional range queries or exact-match-only workloads on unordered keys, where a hash index or structures covered under Multidimensional Indexes may be preferable.

Consider a B+-tree of order $n = 4$ (so each node holds up to 3 keys / 4 pointers, and non-root nodes need at least $\lceil 4/2 \rceil = 2$ children, i.e. at least 1 key). Start from an empty tree and insert keys in this order: `10, 20, 5, 6, 12, 30, 7, 17`.

Final tree: root `[10, 20]` with three children: `[5,6,7]`, `[10,12,17]`, `[20,30]`, all chained left to right. Height is 2 — one internal level, one leaf level — for 8 keys, consistent with $\log_2 8 = 3$ being a loose upper bound (the actual height is much smaller thanks to fanout $\ge 2$ at every step, and would stay at height 2 for hundreds of keys given order 4's minimum fanout).

Now delete 6. Locate leaf `[5,6,7]`, remove 6 → `[5,7]`. Minimum keys required per non-root leaf is $\lceil 4/2 \rceil - 1 = 1$; `[5,7]` has 2 keys, still legal. No merge needed. Tree unchanged in shape.

Now delete 7. Locate leaf `[5,7]`, remove 7 → `[5]`. Still exactly at the minimum (1 key), legal — no fixup triggered. This shows underflow handling only activates strictly below the minimum, not merely at it.

Now delete 5 as well (leaf now would have 0 keys, illegal). Sibling `[10,12,17]` has 3 keys (above minimum), so we redistribute: move the smallest entry, `10`, from the sibling into the underflowing leaf, and update the separating key in the root from `10` to `12` (the new smallest key of the sibling). Leaves become `[10] → [12,17] → [20,30]`, root becomes `[12, 20]`. The tree stays at height 2 with all invariants intact — exactly the local, no-cascade repair the algorithm guarantees.

The B-tree family, of which the B+-tree is the disk-optimized dense-leaf variant, emerged from the practical need in the early 1970s to manage indexes that vastly exceeded available main memory, at a time when disk access was the dominant cost in any database operation. Rudolf Bayer and Edward McCreight, working at Boeing Scientific Research Labs, formalized the balanced multiway tree with guaranteed logarithmic height — engineered specifically around minimizing disk seeks rather than in-memory comparisons, a design philosophy that still defines every storage-engine index built since.

Every mainstream relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements its primary and secondary indexes using B+-tree variants, because the structure directly optimizes for the dominant real-world cost: disk (or SSD) I/O. Clustered indexes in InnoDB store entire rows in the B+-tree leaves themselves, making the leaf level double as the physical row storage. Filesystems such as NTFS, HFS+, and Btrfs use B+-tree or B-tree variants to index directories and file extents at scale. Key-value stores and search engines that need sorted range scans (as opposed to pure hash lookups) — including many embedded stores and the internal structures behind LSM-tree-based systems' sorted runs — draw on the same core split/merge logic. Understanding the B+-tree is foundational before comparing it against alternative access methods discussed under Introduction to Indexing, deciding which columns merit an index as covered in Index Selection, or moving to structures that handle multiple search keys simultaneously, the subject of Multidimensional Indexes.

Ask the tutor: How does the B+-tree's split/merge logic change when the tree is used as a clustered index storing full rows in its leaves, rather than just pointers?