Tree

B-tree Deletion

Remove keys while preserving sorted order, balanced height, and the minimum-key rules that keep the tree valid.

B-tree deletion is one of the hardest tree operations for learners because the challenge is not just removing a key. The real challenge is deciding how to repair the tree when deletion causes underflow.

The key teaching flow is: delete → diagnose underflow → choose the correct repair → propagate upward if needed. Once learners can recognize the repair pattern, the algorithm becomes much easier to follow.

Watch Visualization View Pseudocode

Quick Facts

Deletion Is Decision-Driven

Removing the key is only the beginning. The main work is choosing the correct repair strategy afterward.

Underflow Is the Trigger

If a node drops below the minimum allowed number of keys, the tree must be repaired.

Sibling Capacity Matters

Borrow is possible only when a sibling has an extra key to give.

Repair Can Propagate Upward

A merge can reduce keys in the parent, which may cause another repair higher in the tree.

Key Idea

B-tree deletion is best understood as a rule-selection problem. Once a deletion happens, learners must ask: What condition does the tree satisfy now, and which repair rule applies next?

The most important mental model is: diagnose first, repair second. Without that diagnosis step, the cases feel like memorization instead of reasoning.

Visualization

This visualization highlights the full deletion cycle: internal-key replacement, underflow detection, sibling comparison, borrowing, merging, and possible root shrink. Watch actively: pause and predict which rule applies next.

A good viewing habit is to stop before each repair and ask: Should this node borrow, merge, or trigger a higher-level change?

How It Works

Locate the Key

Search for the key to delete, just as in normal B-tree search.

Delete or Replace

If the key is in an internal node, replace it with a predecessor or successor before continuing deletion.

Check for Underflow

If the node now has too few keys, the tree needs repair.

Borrow, Merge, or Shrink

Choose the correct repair based on sibling capacity and parent structure.

The Four Main Repair Rules

Replace

If the deleted key is inside an internal node, replace it with a nearby key such as the predecessor or successor, then continue deletion in the child subtree.

Borrow

If a sibling has an extra key, move a separator key through the parent so the underfull node gains one key and balance is restored.

Merge

If siblings cannot lend a key, combine the underfull node with a sibling and pull a separator down from the parent.

Shrink

If repair causes the root to lose its last separator, the tree height decreases by one.

Borrow vs Merge

This is the most important deletion decision:

If a sibling has an extra key:
    Borrow

Otherwise:
    Merge

That is why sibling capacity is such a useful teaching focus. Borrow preserves two separate nodes. Merge combines them and may reduce the parent’s key count.

Why It Matters

Structural Reasoning

B-tree deletion trains learners to reason about invariants, not just follow code.

Database Relevance

B-trees are widely used in indexing, so understanding repair logic has real practical value.

Decision Practice

This topic develops conditional reasoning: learners must choose the correct rule based on structure.

Better Than Memorization

When students understand why a repair works, they can predict tree changes instead of memorizing cases blindly.

Pseudocode

A high-level view of B-tree deletion looks like this:

B-TREE-DELETE(T, k):
    DELETE-FROM-NODE(T.root, k)

    if root has no keys and root has a child:
        make that child the new root


DELETE-FROM-NODE(x, k):
    if k is in x and x is a leaf:
        remove k from x

    else if k is in x and x is an internal node:
        if left child can supply predecessor safely:
            replace k with predecessor
            delete predecessor from left subtree
        else if right child can supply successor safely:
            replace k with successor
            delete successor from right subtree
        else:
            merge the two surrounding children with k
            continue deletion in the merged node

    else:
        choose the correct child where k should be
        if that child is minimal and may underflow:
            repair first by borrowing or merging
        continue deletion in the repaired child

The most important pattern is: before descending, make sure the child you are moving into can safely support deletion.

Common Confusions

“Deletion just removes the key”

Not in B-trees. The deletion step is often followed by structural repair to preserve validity.

“Borrow and merge are interchangeable”

They are not. Borrow is possible only when a sibling has an extra key. Merge is used when borrowing is impossible.

“The parent key disappears during merge”

It does not disappear. The separator key moves down and becomes part of the merged node.

“Root shrink means the tree is broken”

No. Root shrink is a normal structural outcome when the old root loses its final key.

Outcome

After this lesson, learners should be able to recognize underflow, choose between borrow and merge correctly, explain predecessor or successor replacement, and describe how deletion can propagate structural changes all the way to the root.

Back to Home