← Knowledgebase

B-tree deletion: borrowing and merging

The mirror image of a split

Inserting can give a node one key too many, and the fix is a split that pushes a key up. Deleting can leave a node with one key too few, underfull, and the fix pulls a key down. Both keep the B-tree rules: every node except the root holds at least the minimum number of keys, and all leaves stay at the same depth.

Step 1: remove the key from a leaf

If the key is in a leaf, remove it. If it's in an internal node, removing it would leave two children with no key to separate them. So, as in binary search tree deletion, replace it with its in-order successor (right child, then left all the way down), and remove the successor from its leaf instead. Either way, a key leaves a leaf.

Step 2: fix an underfull node

  1. Borrow if a sibling next to it has more than the minimum. The separator key in the parent comes down into the underfull node, and the sibling's nearest key goes up to replace it. Like a rotation, this keeps the order. Done.
  2. Merge if neither sibling can lend. The separator comes down and joins the node and a sibling into one node. The parent lost a key, so it may now be underfull: fix it the same way, one level up.
  3. If the root loses its last key, its only child becomes the new root, and the tree is one level shorter, at every leaf at once.

Several choices are valid in general. These pages use the successor (not the predecessor); borrow from the left sibling first, then the right; and, when merging, use the left sibling if there is one. So every question has one right answer.

Reading the pictures

The node being worked on has a yellow outline; an underfull (or overfull) node turns orange. Keys move by value, so you can watch a separator come down and a sibling's key go up.

B-tree deletion
TimeO(log n): one walk down, then at most one fix per level on the way up.
Borrow or merge?A borrow always ends the repair. Only merges can spread upward, just as only splits do on insertion.