B-Trees

Why B-trees?

Databases and file systems keep their data on disk or SSD, where fetching one block costs far more than anything done with it in memory. A binary search tree with a million keys is about 20 levels deep, which means 20 slow reads per lookup. A B-tree packs many keys into each node, so the tree is short and wide: with a few hundred keys per node, a million keys fit in three or four levels.

The rules

Each node holds its keys in sorted order, with a child between each pair of keys (k keys, k + 1 children).
Every key in a child lies between the two keys on either side of it.
A node holds at most a fixed maximum of keys and, except the root, at least about half that.
All leaves are at the same depth. The tree is always perfectly balanced.

These pages use small nodes so everything is visible: 2-3 trees (1 or 2 keys per node, hence 2 or 3 children) and trees with up to 4 keys per node.

Search

Like a binary search tree, but at each node compare against all its keys: either the key is there, or exactly one gap between keys tells you which child to go to.

Insert: split on the way up

Walk down to the leaf where the key belongs and put it there, in order.
If the leaf now holds one key too many, split it: the middle key moves up into the parent, and the keys on either side become two separate nodes.
The parent gained a key, so it may overflow too: split it the same way, and so on upward.
If the root splits, its middle key becomes a new root.

That last step is the only way the tree gets taller, and it adds a level above every leaf at once. That's why all leaves always stay at the same depth. (A 2-3-4 tree, with up to 3 keys per node, is exactly what a red-black tree encodes with its colors.)

	B-tree with up to m keys per node
Height	About log base m/2 of n: tiny for realistic m.
Search, insert	O(log n) comparisons, and only O(height) node reads, which is what matters on disk.
Delete	Also O(log n): an underfull node borrows a key from a sibling or merges with it. See B-tree deletion.