B-Tree Deletion: Borrowing & Merging

Deletion is the mirror of insertion. Removing a key can push a node below its minimum of t − 1 keys — a state called underflow. Every deletion case exists to either avoid or repair underflow while keeping all B-tree invariants true (balanced, sorted, correct child counts).

There are three basic situations, listed here from cheapest to most expensive:

Deleting a key from an internal node adds one wrinkle: we can't just remove a separator (its children depend on it), so we first replace it with its inorder predecessor or successor (which lives in a leaf) and then delete that key from the leaf — reducing every case to a leaf deletion.

Borrowing (rotation) — used when a neighbour is rich enough to lend:

The parent separator 50 drops down into the starved node, and the sibling's largest key 40 rises to take 50's place. One key shifts through the parent — the parent's key count is unchanged, so nothing propagates upward. Borrowing is always a local, O(1)-node fix.

Merging — used when no neighbour can spare a key (both siblings sit at t − 1):

The separator from the parent is pulled down and combined with the two minimal nodes into a single node of 2t − 1 keys. Because the parent loses a key, a merge can cause the parent to underflow too — so merging may cascade upward, and if the root ends up empty, the tree shrinks in height by one. Merging is the exact inverse of a split.

We continue with the B-tree built in the previous topic — minimum degree t = 3 (min 2 keys, max 5 keys per non-root node), holding 10 … 150:

We now delete 30, 60, 90 one at a time. All three live in the root, so each is an internal-node deletion that first looks to its two surrounding children.

30 separates children [10|20] and [40|50]. Both have exactly t − 1 = 2 keys, so neither can lend a predecessor or successor. This forces a merge: pull 30 down and fuse the two children into one node, then remove 30 from the fused leaf.

The root loses key 30 and one child pointer:

➡️ Case used: deletion using merging with a sibling.

60 now separates [10|20|40|50] and [70|80]. The left child has 4 keys, comfortably above the minimum — so we replace 60 with its inorder predecessor (the largest key to its left, 50), then delete 50 from that leaf. The leaf drops from 4 keys to 3, still ≥ 2, so no underflow occurs.

➡️ Case used: deletion from a leaf node without underflow (after swapping the internal key with its predecessor).

90 separates [70|80] and [100|110] — both minimal (2 keys), so again neither can lend. We merge: pull 90 down, fuse the two leaves, then remove 90.

The root drops to just two keys — still valid, since the root's minimum is 1:

➡️ Case used: deletion using merging with a sibling.

Summary of the three deletions: 30 → merge, 60 → leaf delete without underflow (via predecessor swap), 90 → merge.

The sequence above happened to trigger only merge and no-underflow cases. Here is a compact example that isolates borrowing, again with t = 3 (min 2 keys):

Borrowing kept the fix local — no key count changed in the parent, so nothing propagated upward. Had the left sibling held only 2 keys, we would have been forced to merge instead.

➡️ Case used: deletion using borrowing from a sibling.

Deletion walks a single root-to-leaf path. At each level it does O(1) sibling checks and O(t) key shifting. A borrow stops immediately; a merge may cascade up the path but at most once per level.

• Comparisons / CPU work: O(t · log_t n).
• Disk accesses: O(log_t n).

As with insertion, expensive restructuring (merges cascading, height shrinking) is rare — most deletions are a simple leaf removal — which is why the amortized cost of B-tree updates stays low.