B+ tree Created 2026-10-31 Updated 2026-11-05
A B+ tree is a balanced search tree designed to keep each vertex in a storage database page. Internal vertices contain separator keys and child references; leaf vertices contain the indexed records or references to them. All leaves occur at the same depth, and linked leaves support ordered scans. PostgreSQL's index implementation illustrates this separation between leaf record references and internal downward references.[ref]
A large fan-out reduces storage accesses: with a fixed positive lower bound on nonroot internal fan-out, the height is . A database query first descends to the leaf containing a boundary key, then follows leaf links for a range. Separator keys guide navigation; their copies do not replace the leaf records.
For example, a root separator can direct keys below twelve to leaf and keys at least twelve to leaf . Searching for seventeen descends right. A range query from eight through seventeen starts in the left leaf and continues right. B+ tree node splits preserve the equal-depth structure as records are inserted.
B+ tree node split Created 2026-10-31 Updated 2026-11-05
A B+ tree node split repairs an overflowing B+ tree node by distributing its entries between two nodes and adding a separating downlink to its parent. A parent overflow can propagate the split upward; splitting the root creates a new root one level higher.[ref]
In a simple leaf convention, the parent separator is a copy of the smallest key in the new right leaf. If a leaf with capacity three receives a fourth key, can split into and , with separator nine. Nine remains in the right leaf as an indexed record. The leaf-neighbour links must also be updated.
An internal split instead promotes a separator between child groups; it need not retain that separator as an ordinary key in either new internal node. Distinguishing promotion from the leaf copy rule prevents missing records or inconsistent child ranges. Exact occupancy and separator conventions are implementation choices. Every split replaces one level by two nodes at that same level, so existing root-to-leaf depths remain equal; only a root split increases all depths together.
Use fan-out four to mean at most four child pointers per internal node. A height increase requires a B+ tree node split at the root. Immediately after that B+ tree node split, the new root has exactly two children.
One further insertion follows one search path. Any chain of B+ tree node splits along that path can pass at most one additional separator and child pointer to the root. Its number of children therefore rises from two to at most three, below the maximum four. Thus
The argument includes an initially leaf-only B+ tree: its first root split likewise creates a root with two children. Even if the next insertion causes a child split immediately, the new root still has room. The conclusion assumes the standard insertion operation with one overflowing node split into two; it does not depend on whether height counts edges or levels.