Splits and Merges: Keeping the B-Tree Balanced
A B-Tree maintains its balance through two fundamental operations: splitting nodes that become too full during insertions, and merging (or redistributing) nodes that become too empty during deletions. These operations ensure that the tree's height changes only when absolutely necessary, and all leaves remain at the same depth.
B-Tree order and capacity
For a B-Tree of minimum degree t (also called the minimum branching factor):
- Each node holds at most 2t - 1 keys and 2t children.
- Each non-root node holds at least t - 1 keys and t children.
- The root may have as few as 1 key (or 0 if the tree is empty).
Split: handling overflow
When an insertion causes a node to exceed its maximum of 2t - 1 keys:
- The node now has 2t keys (one too many).
- Find the median key — the key at position t (the middle).
- Split the node into two nodes: the left node keeps keys 0..t-2 (that is, t-1 keys), and the right node gets keys t..2t-1 (also t-1 keys).
- Push the median key up into the parent node, along with a pointer to the new right node.
- If the parent also overflows, split it too — this can cascade up to the root.
- If the root splits, a new root is created with one key and two children. This is the only way the tree grows taller.
Merge: handling underflow
When a deletion causes a non-root node to have fewer than t - 1 keys:
- First, try to redistribute (borrow) a key from an adjacent sibling. If a sibling has more than t - 1 keys, rotate a key through the parent: pull the separator key down from the parent into the underflowing node, and push a key from the sibling up to replace the separator.
- If both adjacent siblings are at the minimum (exactly t - 1 keys), merge the underflowing node with one sibling: combine the two nodes and pull the separator key down from the parent. The merged node has (t-1) + (t-1) + 1 = 2t - 1 keys — exactly full.
- The parent now has one fewer key. If the parent underflows, the process cascades upward.
- If the root is left with 0 keys after a merge, its only child becomes the new root — the tree shrinks by one level.
Concurrent access: latch crabbing
In a multi-threaded database, multiple threads may traverse and modify the B-Tree simultaneously. Latch crabbing (also called latch coupling) is the standard protocol: a thread acquires a latch (lightweight lock) on a child node before releasing the latch on the parent, but only if the child is "safe" — that is, it will not split or merge even if the current operation modifies it. This limits the portion of the tree that must be locked.
Real-Life: Cascading Split During Bulk Insert
Imagine you are bulk-loading a million rows into a PostgreSQL table with a B-Tree index on the primary key. As keys are inserted:
- The first few keys fit in the root leaf node (say, up to 200 keys for a 8KB page).
- When the 201st key is inserted, the root splits: a new root is created with one key, and two leaf children. The tree is now 2 levels tall.
- As more keys are inserted, leaf nodes keep splitting. Each split pushes a key into the parent internal node.
- Eventually an internal node fills up and splits too, pushing its median key into the grandparent.
- When the root internal node fills and splits, a new root is created — the tree grows to 3 levels.
For a B-Tree with order 200 (100 minimum keys per node):
- Level 1 (root): 1 node, up to 199 keys
- Level 2: up to 200 nodes, each with up to 199 keys = ~40,000 keys
- Level 3: up to 40,000 nodes = ~8,000,000 keys
- Level 4: ~1.6 billion keys
So even 1 billion keys need only 4 levels. Splits are rare at higher levels because the fanout is so high.
PostgreSQL optimization: for sequential inserts (like auto-incrementing IDs), PostgreSQL uses a "fastpath" that caches the rightmost leaf, avoiding repeated root-to-leaf traversals. This makes bulk loading nearly O(1) amortized per insert.