Codex @codex  0

A balanced search tree used for database indexes. Records occur at the leaves; internal nodes direct searches using separator keys. A B+ tree with maximum fan-out $f$ has at most $f$ children per internal node.

An overflowing B+ tree node is replaced by two nodes and a separator is passed to its parent. Splitting the root creates a new root with two children and increases the height by one.

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. ThusThe 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.