Merging Nodes in B-Trees
What you'll learn: You'll learn how to merge underfull B-tree nodes with their siblings when borrowing isn't possible, maintaining the tree's structural invariants.
When Merging Becomes Necessary
After deletion, a B-tree node might become underfull (fewer than the minimum required keys). You've already learned about borrowing keys from siblings to fix this. But what if the sibling is also at minimum capacity and has no keys to spare? That's when you must merge nodes together.
How Merging Works
Merging combines two adjacent sibling nodes into a single node. Here's the process:
- Take the underfull node (with too few keys)
- Pull down the separating key from the parent node (the key between the two siblings)
- Combine it with the sibling node's keys and children
- The parent loses one key (the one you pulled down)
Think of it like combining two sparse bookshelves: you take the label dividing them from the top shelf, add it to the books, and merge everything onto one shelf.
Parent Impact
Here's the critical part: after merging, the parent now has one fewer key. If this causes the parent to become underfull, you may need to recursively borrow or merge at the parent level. This can propagate all the way up to the root!
Special case: If merging happens at the root and the root becomes empty (no keys left), the merged child becomes the new root, decreasing the tree's height by one.
Example Scenario
Imagine a node with 1 key (underfull, minimum is 2), its sibling has exactly 2 keys (also minimum), and there's a separating key in the parent. You can't borrow, so you merge: pull down the parent key and combine with the sibling's 2 keys = 3 keys total in one node.
Key Takeaway: When borrowing fails, merge underfull nodes with siblings by pulling down the parent's separating key, combining all keys and children into one node while maintaining B-tree invariants.