B+ tree (source code)

= B+ tree
{c}
{wiki}

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.<B-Tree Indexes in the PostgreSQL documentation>[version 18, section 65.1.4.1, B-Tree Structure]{ref}

A large fan-out reduces storage accesses: with a fixed positive lower bound $b$ on nonroot internal fan-out, the height is $O(1+\log_b n)$. 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 $12$ can direct keys below twelve to leaf $[3,8]$ and keys at least twelve to leaf $[12,17]$. 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.