B-tree Primer
B-trees are the workhorse of every serious database storage engine, from Postgres to SQLite to MongoDB. Unlike binary trees, B-trees are wide and shallow which minimizes disk I/O. This primer walks through the structure, the search algorithm, and the split-on-insert mechanic that keeps everything balanced.
1.Structure and invariants
A B-tree of order m holds up to m-1 keys per node and up to m child pointers. All leaves sit at the same depth, which is the magic that bounds search at O(log_m N) regardless of insert order. Each internal key acts as a separator: subtree to its left holds smaller keys, subtree to its right holds larger.
2.Search descent
Searching is a binary search inside each node followed by a single pointer follow to the correct child. On a tree with branching factor 256 and a billion keys, the depth is only four. With pages cached in RAM, that is at most one disk seek per lookup.
function search(node, key) {
let i = 0;
while (i < node.keys.length && key > node.keys[i]) {
i++;
}
if (i < node.keys.length && key === node.keys[i]) {
return node.values[i];
}
if (node.isLeaf) return null;
return search(node.children[i], key);
}3.Insert and split
Inserts always land in a leaf. If the leaf has room, drop the key in place. If it is full, split it in half, promote the median to the parent, and recurse. When the root splits, the tree grows by one level. That is the only time the tree gets taller, which is why depth stays balanced for free.