Course contentsShow
← Computer Science
Lesson 1684 of 2,87238. Database Transactions and IndexingFree lesson

Deletion from Internal Nodes

Replacing deleted keys with predecessors or successors and recursively deleting from subtrees.

Deletion from Internal Nodes

What you'll learn: How B-Trees handle deletion when the key to remove sits in an internal (non-leaf) node.

The Core Challenge

When you delete a key from a leaf node in a B-Tree, it's straightforward—you just remove it. But what happens when the key you need to delete lives in an internal node? You can't simply remove it, because internal nodes act as "signposts" guiding searches through the tree. Removing one would break the tree's structure.

The Replacement Strategy

The solution is elegant: replace the deleted key with either its predecessor or successor, then recursively delete that replacement key from the appropriate subtree.

  • Predecessor: The largest key in the left subtree (rightmost value if you went left)
  • Successor: The smallest key in the right subtree (leftmost value if you went right)

Why This Works

Think of it like a leadership succession plan. When a manager (internal node key) leaves, you promote someone from their team—either the most senior person from the department below them (predecessor) or the most junior qualified person from the department above (successor). The promoted person takes the manager's spot, and you handle their now-vacant position recursively.

The Process

  1. Find the key to delete in the internal node
  2. Choose either the predecessor (from left child) or successor (from right child)
  3. Copy that replacement value into the internal node
  4. Recursively delete the replacement key from its original subtree (which will be a leaf or another internal node)

This recursive deletion may trigger additional operations like borrowing from siblings or merging nodes if the child becomes underfull.

Key Takeaway: Deleting from internal B-Tree nodes requires replacing the deleted key with its predecessor or successor, then recursively deleting that replacement from its original subtree to maintain the tree's structural properties.