Borrowing Keys from Siblings
You'll learn: How to fix an underfull B-Tree node by transferring a key from an adjacent sibling through the parent, maintaining balance without merging.
When deleting from a B-Tree, you might create an underfull node — one with fewer keys than the minimum required. Before resorting to merging nodes (which can propagate changes upward), we first check if a sibling can spare a key.
The Core Idea
Think of siblings as neighbors sharing resources. If your node is too empty but your sibling has extras, you can "borrow" through your shared parent:
- Identify a sibling with more than the minimum number of keys (it has extras to share)
- Rotate keys through the parent: move a parent key down to the underfull node
- Replace the parent key with a key from the generous sibling
This is like a circular shift: sibling → parent → underfull node, keeping the BST ordering intact throughout.
Example
Suppose you have nodes where minimum is 2 keys:
- Underfull node:
[10](only 1 key) - Parent key between them:
[20] - Right sibling:
[25, 30, 35](has 3 keys, can spare one)
After borrowing:
- Underfull node becomes:
[10, 20](now valid!) - Parent gets:
[25] - Sibling becomes:
[30, 35](still valid)
The key 20 moved down, and 25 moved up. Child pointers also shift accordingly to maintain the search property.
When Borrowing Works
Borrowing only succeeds when a sibling has more than the minimum required keys. If both siblings are already at minimum capacity, you must merge instead.
Key Takeaway: Borrowing from siblings fixes underfull nodes through parent key rotation, maintaining B-Tree invariants without the cost of merging when adjacent nodes have spare capacity.