Resolving underflow in B-tree

Underflow happens in a B-tree of order m when a deletion leaves a non-root node with fewer than the minimum number of keys, ⌈m/2⌉ − 1 (for order 5, fewer than 2 keys). The node is then repaired using an adjacent sibling that has the same parent.

1. Balance (borrow / redistribute / rotate)

Used when an adjacent sibling has more than the minimum number of keys.

1. Move the separator key in the parent down into the underflowing node.
2. Move the nearest key of the rich sibling up to replace the separator in the parent.
3. If the nodes are internal, also move the child pointer that goes with the borrowed key.

Example (order 5, min 2 keys). Delete 10 from:

    [30]                      [40]
   /    \       delete 10    /    \
[10 20] [40 50 60]  ==>   [20 30] [50 60]

After the deletion the left leaf is [20], with only 1 key (underflow). The right sibling has 3 keys, so 30 comes down and 40 goes up.

2. Combine (merge / concatenate)

Used when the sibling has exactly the minimum number of keys, so nothing can be borrowed.

1. Merge the underflowing node, the separator key from the parent, and the sibling into one node.
2. Remove the separator and the extra pointer from the parent.
3. The parent may now underflow, so repeat balance or combine upward. If the root loses its last key, the merged node becomes the new root and the tree height decreases by one.

Example. Delete 10 from:

    [30]
   /    \        delete 10
[10 20] [40 50]     ==>      [20 30 40 50]

After the deletion [20] underflows, and its sibling [40 50] has only the minimum 2 keys. Combine [20] + 30 + [40 50] = [20 30 40 50]; the root becomes empty and is removed, so the merged node is the new root.