B+ Tree Database Index

What Makes It a B+ Tree, Not Just a B-Tree

A regular B-tree allows a key-value pair to be stored in any node, internal or leaf, the moment the key is inserted and the node has room. A B+ tree changes that rule in two ways. First, internal nodes only ever hold copies of keys used for routing; they never hold the actual record payload. Second, every real record, along with its full key, lives in a leaf node, and only in a leaf node. When a key is inserted, the tree always walks down to a leaf to place it, and if that key also needs to appear in an internal node as a separator, only a copy of the key travels upward, not the data itself.This separation has a practical payoff: internal nodes become much smaller per key, since they carry no payload, so many more routing keys fit into a single disk page or memory block. A shorter, wider tree means fewer levels to descend before reaching a leaf, and fewer levels means fewer expensive random-access reads from disk. In a classic B-tree, the payload size mixed into internal nodes bloats them and forces the tree taller for the same amount of data.The second defining trait, and the one this lab focuses on, is that leaf nodes are linked to their neighbors in sorted key order, typically as a doubly-linked list so scans can move forward or backward. That link is invisible in a plain B-tree; there, leaves are isolated dead ends, and moving from one leaf's data to the next sorted leaf's data means climbing back up to a shared ancestor and back down. In a B+ tree, that climb is unnecessary. The tree is descended exactly once, to locate the first matching leaf, and everything after that is a straight walk along the chain. Try building the tree in this lab and notice how, no matter how deep it grows, the leaves always stay stitched together left to right in ascending order.

Why the Leaf-Linked List Changes Everything for Range Scans

Consider a query asking for every transaction with a timestamp between two dates. In a structure without linked leaves, satisfying that query means finding the first qualifying key, then repeatedly asking the tree, what comes next? Each of those questions can require walking back up toward the root and back down a different path, since the next key in order is not necessarily a neighbor in the same node. For a range spanning thousands of rows, that adds up to a large number of tree traversals, each one a potential random disk read.A B+ tree eliminates almost all of that work. The database performs a single descent to locate the leaf holding the first key greater than or equal to the range's start. From there, it simply follows the leaf's next pointer, reading records in sorted order, until it reaches a key past the end of the range. Each step is a cheap sequential move to an adjacent leaf rather than a fresh tree traversal. On spinning disks this mattered enormously because sequential reads are far faster than random ones; on modern solid-state storage the gap is smaller but still real, and the reduction in CPU work (fewer comparisons, fewer pointer chases through internal nodes) remains significant either way.This same mechanism accelerates full index scans and sorted output more broadly. Query planners frequently want data in key order to satisfy an ORDER BY clause, to feed a merge join, or to compute an aggregate over a window of rows. Instead of sorting the data separately after retrieval, the engine can simply walk the leaf chain of an existing index and get sorted output essentially for free. This is precisely why the leaf-linking feature is not a minor implementation detail; it is often the single biggest reason a B+ tree outperforms a plain B-tree in real database workloads.

Why MySQL InnoDB and PostgreSQL Choose B+ Trees

MySQL's default storage engine, InnoDB, builds its primary key index as a B+ tree where the leaves themselves store the complete row data, an arrangement often called a clustered index. Every secondary index in InnoDB is also a B+ tree, but its leaves store the indexed column values plus a reference back to the primary key rather than the full row. In both cases, the linked leaf structure is what makes range predicates like WHERE order_date BETWEEN X AND Y efficient: the engine finds the starting leaf once and streams forward.PostgreSQL takes a related but distinct approach. Its default index type, confusingly named the B-tree access method, is in practice implemented as a B+ tree internally, with data-bearing leaf pages linked in sorted order via sibling pointers, again to support efficient range scans, ordered scans, and even backward scans for descending sort orders. Neither engine uses the older, plain B-tree structure for its everyday indexes, precisely because production workloads are dominated by point lookups mixed with range scans, and the linked-leaf design serves both well.There are secondary benefits too. Because internal nodes hold no payload, they compress well and tend to stay resident in memory (the buffer pool or shared buffers cache), so the only disk access frequently needed is for the leaf level itself. Full table scans, index-only scans that avoid touching the underlying table entirely, and bulk export operations all lean on the same leaf-chain walk. Even routine maintenance, like rebuilding an index or computing statistics, benefits from being able to stream through sorted data without repeatedly re-searching the tree. This combination of compact routing nodes and a sorted leaf chain is why the B+ tree, not the classic B-tree, became the default choice for relational database indexes.

Insertion, Splits, and Keeping the Chain Intact

Inserting into a B+ tree starts the same way as a B-tree: descend from the root, comparing the new key against separator keys at each internal node, until reaching the appropriate leaf. The key and its record are added to that leaf in sorted position. If the leaf now holds more entries than its capacity allows, it splits into two leaves, each holding roughly half the entries.Here the B+ tree diverges from the classic algorithm in an important way. When an internal node splits in a plain B-tree, the middle key is moved up to the parent and removed from the children, since keys are unique to one location in the tree. In a B+ tree, when a leaf splits, the smallest key of the new right-hand leaf is copied (not moved) up to the parent as a separator; the key still physically remains in the leaf alongside its data, because leaves must hold every key with its record. Only when an internal node splits does a key genuinely move up without staying behind, since internal nodes carry no data of their own to preserve.Just as important, the split must update the linked list pointers so the chain stays unbroken: the new right leaf's previous pointer is set to the original leaf, the original leaf's next pointer is redirected to the new leaf, and the new leaf's next pointer takes over whatever the original leaf used to point to. Skipping this step would silently break range scans that cross the split point, even though the tree's routing structure above the leaves would still look perfectly correct. If the split propagates upward and even the root splits, a brand-new root is created holding a single separator key, and the tree grows one level taller, but the leaf level, and its chain, remains a single unbroken sorted sequence throughout. Use the insert control in this lab and watch the pointer between two leaves get rewired the moment a split occurs.

Deletion, Rebalancing, and Real-World Trade-offs

Deleting a key follows the same initial path: descend to the leaf containing it and remove the entry. If the leaf still has at least the minimum required number of entries afterward, nothing else needs to happen structurally, though a separator key higher in the tree may now be slightly stale; most implementations tolerate this since it still routes searches correctly, as long as it stays consistent with the boundary between children.If a deletion leaves a leaf under-full, the tree tries to borrow a spare entry from an adjacent sibling leaf, adjusting the parent's separator key to match. When borrowing is not possible because the neighbor is also at its minimum, two leaves are merged into one, and the corresponding separator key is removed from the parent. Crucially, merging two leaves also means merging their positions in the linked list: the surviving leaf's next pointer must be updated to skip over the leaf being discarded, and the following leaf's previous pointer must point back to the surviving leaf. As with splits, this bookkeeping is easy to get wrong in a from-scratch implementation, and a broken pointer can cause a range scan to silently skip data or loop, even though point lookups through the tree would still succeed.The trade-off databases accept for all this is some duplicated key storage, since separator keys in internal nodes are copies of keys that also live in leaves, and every leaf carries two extra pointers for its neighbors. In exchange, they get near-constant-time access to the next or previous record in sorted order, resilient support for both equality and range predicates through the same structure, and internal nodes compact enough to keep most of the tree cached in memory. That is a trade every production database engine has judged well worth making, which is why, despite the family name, it is the B+ tree, not the original B-tree, doing the real work inside the index you query every day.

Frequently asked questions

Try it live

Everything above runs in your browser — open B+ Tree Database Index and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.