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