Course contentsShow
← Computer Science
Lesson 563 of 2,87213. Balanced TreesFree lesson

B-Tree Deletion: Leaf Node Cases

Remove keys from leaf nodes, handling simple cases and recognizing when nodes become underfull.

B-Tree Deletion: Leaf Node Cases

You'll learn how to remove keys from B-tree leaf nodes and recognize when a node violates the minimum key requirement.

The Simple Case

When deleting a key from a B-tree, the easiest scenario is removing it from a leaf node (one with no children). If the leaf still contains enough keys after deletion, you simply remove the key and you're done!

Remember that B-trees have a minimum degree t, which means each non-root node must contain at least t-1 keys. For example, if t=3, each node needs at least 2 keys.

Two Leaf Deletion Scenarios

Scenario 1: Node remains valid If the leaf node has more than t-1 keys, just delete the target key. The node still satisfies the B-tree invariant.

Think of it like a bookshelf that must hold at least 2 books. If it has 4 books and you remove one, it still has 3 books—perfectly fine.

Scenario 2: Node becomes underfull If the leaf node has exactly t-1 keys (the minimum), removing one leaves it with t-2 keys—violating the invariant. This is called becoming underfull.

Like that bookshelf dropping to just 1 book when it needs at least 2. Houston, we have a problem.

Detecting Underfull Nodes

Before deleting, check: keys_count > t-1?

  • Yes: Safe to delete directly
  • No: Deletion requires additional rebalancing operations (you'll learn these next)

The key insight is recognizing when simple deletion works versus when you need to "borrow" keys from siblings or merge nodes.

Key Takeaway: Deleting from a B-tree leaf is straightforward when the node has extra keys beyond the minimum; otherwise, the node becomes underfull and requires rebalancing to maintain B-tree invariants.