B-Trees
A B-tree is a balanced search tree with many keys per node, tuned to minimise disk reads for databases and file systems.
Wide nodes, shallow trees
A B-tree generalises the binary search tree by letting each node hold many keys and many children. A node with k keys has k+1 children, and the keys within a node are kept sorted, partitioning the child subtrees into ranges. Because each node fans out to hundreds of children, the tree is very shallow: even billions of keys sit only a handful of levels deep.
Built for the disk
The design target is storage where reading one block is far more expensive than comparing keys already in memory. A node is sized to one disk block or page, so descending one level costs one block read. Minimising tree height therefore minimises disk I/O, which is why B-trees underpin relational databases and file systems.
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
- Range scan: O(log n + k) for k results
Splitting and merging
A B-tree of order m keeps each node between roughly m/2 and m keys, so nodes are always at least half full. Inserting into a full node splits it and pushes the median key up to the parent, which may cascade to the root and increase height. Deletion that underfills a node merges it with a sibling or borrows a key, keeping the tree balanced.
The B+ tree variant
Most database indexes actually use a B+ tree, a variant that stores all values in the leaves and links the leaves in a chain. Internal nodes hold only keys for routing, so they fan out even wider, and the leaf chain makes range scans a simple linear walk. This combination is why B+ trees dominate on-disk indexing.