B-trees, visualized
Where binary search falls short
In Binary search, visualized we found a value among a billion sorted values in at most 30 comparisons. That is fast when the array sits in memory. A database index lives on disk, and there the cost that matters is not comparisons but disk reads.
A disk, even an SSD, reads data in pages of a few kilobytes. Each of the 30 jumps that binary search makes lands far from the last one, so each jump reads a different page. Thirty page reads per lookup is far too slow for a database that answers thousands of queries a second.
A B-tree fixes this by doing more work per page. Instead of one value per step, each node holds many sorted keys, and the whole node is one page. You read a node once, binary search inside it in memory, and follow one pointer down.
Try it
The tree below holds 14 keys, with at most 3 keys per node. Press Search and watch it read one node per level. The node being read is outlined in purple, and each key it compares against lights up. To go one comparison at a time, press the Step button next to Search instead.
Then press Insert. The suggested value lands in a full leaf, so you can watch that leaf get too full and split. The Step button next to Insert does the same insert one move at a time: the walk down, the new key landing in the leaf, and each split on the way back up.
14 keys in 3 levels, up to 3 keys per node. Search, insert or step through.
If the animation is too fast or too slow, change the speed for every visualization on this page:
Change the animation speed
How a node is laid out
A node with k keys has k + 1 child pointers. The keys split the number line into ranges, and each pointer leads to the subtree for one range:
[ 32 | 64 ]
/ | \
< 32 32 to 64 > 64Every key in the left subtree is smaller than 32, every key in the middle one sits between 32 and 64, and every key on the right is larger than 64. That rule holds at every level, which is what makes search work.
Searching
Start at the root and repeat:
- Read the node. This is one disk read.
- Binary search its keys, exactly as in the previous article.
- If a key equals the target, you are done. The key turns green.
- Otherwise, the search ends between two keys. Follow the pointer between them and go down one level.
If you reach a leaf and the key is not there, the tree does not contain it.
static boolean contains(Node node, int target) {
while (node != null) {
// Same binary search as before, inside one node.
int lo = 0, hi = node.keyCount - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (node.keys[mid] == target) return true;
if (node.keys[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
// lo is now the index of the child whose range holds target.
node = node.isLeaf ? null : node.children[lo];
}
return false;
}Search for a key that lives in the root or a middle level, such as 38 or 64. A B-tree stores every key exactly once, and some keys live in internal nodes, so some searches stop before they reach a leaf. Keep that in mind: the B+ tree changes it.
Inserting and splitting
New keys always go into a leaf:
- Search for the key as above, down to the leaf where it belongs.
- Insert it into that leaf in sorted order.
- If the leaf now has more keys than fit, split it. The middle key moves up into the parent, the keys left of it stay in the old node, and the keys right of it go into a new node.
- The parent gained a key, so it might be too full now as well. If it is, split it the same way, and keep going up.
- If the root splits, the middle key becomes a new root.
Keep pressing Insert in the widget, or Step to pause on each split. Most inserts touch only one leaf. Every so often a split cascades all the way up and the tree gets one level taller.
A split also leaves both halves about half full. Each node is therefore between half full and full, apart from the root, so the tree never wastes much space and never drifts out of balance. Deleting keys works in reverse, borrowing from or merging with a neighbouring node when one gets too empty. This article skips deletes.
Fan-out is the whole point
Switch Max keys per node in the widget from 3 to 5. The same 14 keys now fit in fewer, wider nodes, and the tree is shorter. Real databases take this much further. MySQL’s InnoDB uses 16 KB pages by default and PostgreSQL uses 8 KB pages. A 16 KB page holding 8-byte keys and pointers fits several hundred children per node. Call it 500:
| levels | keys reachable with about 500 children per node |
|---|---|
| 1 | about 500 |
| 2 | about 250,000 |
| 3 | about 125 million |
| 4 | about 62 billion |
The number of comparisons barely changes. Binary search inside a 500-key node takes about 9 comparisons, and four levels take about 36, which is what plain binary search would need over 62 billion values. What changes is the disk reads: 4 instead of 36. The root and the level below it are read so often that they stay cached in memory, so a lookup usually costs one or two reads from disk.
What comes next
Databases rarely use this exact textbook structure. MySQL and PostgreSQL both build their indexes on a variant, the B+ tree, which keeps every value in the leaves and links the leaves together so that range queries such as WHERE id BETWEEN 20 AND 60 become a single walk along the bottom of the tree. That is the next article in this series.