B-tree and B+ tree

In short: B-trees are balanced search trees with many keys per node. They underpin most database indexes because they need few disk accesses.

In more detail: Each node corresponds to a storage page (for example 8 KB) and holds hundreds of keys. The tree is therefore very flat: with 3–4 levels you find one item among millions. In a B+ tree all data sits in the leaves, which are linked to each other, speeding up range queries.

In Depth

• Search: From the root downwards, binary search in each node. Running time O(log n) with a large base.
• Insert: Into the leaf; if it is full it splits and the middle key moves up.
• Delete: With too few entries nodes are merged or redistributed.
• B+ tree: Inner nodes only as signposts, leaves linked.
• Effects: Random keys (UUIDv4) cause many splits, sequential keys are cheaper.
• Alternatives: LSM trees (write-optimised), hash indexes.

See also: LSM tree and sorted string tables, SQL index