Persistent indexes often store far more data than fits in fast memory. A tree designed for storage should therefore minimize expensive page accesses as well as comparisons.

A B-tree is a balanced multiway search tree whose nodes contain many ordered keys and many child pointers.

High branching factor

Instead of storing only one key per node, a B-tree node can hold enough keys to occupy a useful fraction of a storage page.

This gives a large branching factor and keeps the tree shallow even when it contains millions of entries.

Search

Within one node, the key ranges determine which child can contain the target. Search descends through one child at each level until the key is found or a leaf is reached.

Maintaining balance

Insertions can split full nodes, while deletions can redistribute or merge underfull nodes. These operations preserve the balance invariants, so all leaves remain at the same depth.

B+ trees

Database systems commonly use B+ tree variants in which leaf nodes contain the indexed entries and are linked in key order. This makes range scans efficient after the first matching leaf is found.

B-trees trade more work within each node for far fewer levels, matching the block-oriented nature of persistent storage.