Deleting from B-Trees

Why delete is the hard part

Insert only ever makes nodes bigger, and the fix (split) is symmetric and local. Delete makes nodes smaller, and a node that gets too small — an underflow — can't just shrink quietly, because every B-tree node must keep at least ⌈M/2⌉ - 1 keys (except the root). Fixing an underflow means pulling keys in from elsewhere in the tree, and where they come from depends on what your siblings look like. This is genuinely the most fiddly part of implementing a B-tree — budget real time for edge cases here.

Step 1: locate the key, and handle two shapes

Deleting a key found in a leaf is simple: remove it from the sorted array, then check for underflow (see below).

Deleting a key found in an internal node is trickier — you can't just remove it, because internal keys separate subtrees; removing one blindly would break the ordering invariant. The standard fix: replace the key with its in-order predecessor (the largest key in the subtree to its left) or in-order successor (the smallest key in the subtree to its right), then recursively delete that key from the leaf it actually lives in.

function delete(node, key):
    if key in node.keys:
        if node.is_leaf:
            remove key from node.keys
        else:
            pred = find_max(child_before(key))   // or successor from child_after(key)
            replace key with pred in node.keys
            delete(child_before(key), pred)        // recurse — pred is now a duplicate to remove
    else:
        child = choose_child(node, key)
        delete(child, key)
    fix_underflow(child_just_modified)

Either predecessor or successor works; pick one and be consistent, since the "swap with a leaf value, then delete from the leaf" trick guarantees the actual removal always happens at a leaf, which is the case you already know how to shrink.

Step 2: fixing underflow — borrow first, merge second

After a removal, check whether the node fell below the minimum key count. If it did, try two remedies in order:

1. Borrow (rotate) from a sibling. If an immediate sibling has more than the minimum number of keys, you can borrow one:

• Move a key from the parent down into the underflowing node.
• Move the sibling's outermost key up into the parent to replace it.
• If the sibling is internal, its outermost child pointer moves too, to the underflowing node.

This is a rotation — no tree shape change, no further propagation needed. It's the cheap fix, prefer it when possible.

2. Merge with a sibling. If neither sibling has a spare key (both are exactly at the minimum), borrowing isn't possible — you'd only create a new underflow in the sibling. Instead, merge: combine the underflowing node, a separator key pulled down from the parent, and a sibling into one node.

merged = left_sibling.keys + [separator_from_parent] + node.keys
remove left_sibling and separator from parent
replace both with `merged` as parent's single child there

Merging removes a key from the parent — which can underflow the parent, so this step is recursive, just like split propagation on insert, but shrinking instead of growing.

Step 3: the root can shrink the tree

If the merge propagates all the way to the root and the root ends up with zero keys (it merged its only two children into one), that lone remaining child becomes the new root, and the tree loses a level. This is the delete-side mirror of "root split grows the tree" from the insert lesson.

Test matrix — don't skip any of these

• Delete a key straight out of a leaf, no underflow.
• Delete a key from an internal node (forces the predecessor/successor swap).
• Underflow fixed by borrowing from the left sibling.
• Underflow fixed by borrowing from the right sibling.
• Underflow fixed by merging, propagating up through multiple levels.
• Merge propagates all the way to the root, and the tree shrinks by one level.
• DELETE on a key that doesn't exist → NOT_FOUND, tree untouched.

Each of these is a genuinely different code path. A B-tree implementation that only handles "delete from a leaf, no rebalancing" will look correct on small tests and then corrupt the tree the moment a real workload deletes enough keys to trigger a merge.