B+ tree node split (source code)

= B+ tree node split
{c}

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.<B-Tree Indexes in the PostgreSQL documentation>[version 18, section 65.1.4.1, upward split cascade and root split]{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, $[2,5,9,14]$ can split into $[2,5]$ and $[9,14]$, 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.