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

Deletion from Leaf Nodes

Removing keys from leaf nodes and handling underflow through borrowing or merging with siblings.

Deletion from Leaf Nodes

What you'll learn: How B-Tree indexes handle removing keys from leaf nodes and what happens when a node becomes too small.


When you delete a key from a B-Tree, the simplest case occurs when that key lives in a leaf node (a node with no children). Unlike insertion, which may cause nodes to grow and split, deletion can make nodes shrink below their minimum capacity—creating what's called underflow.

The Basic Process

Every B-Tree has a minimum number of keys each node must contain (except the root). When you remove a key from a leaf:

  1. If the leaf still has enough keys after deletion: Simply remove the key—done!
  2. If the leaf falls below the minimum (underflow): You must restore balance by either borrowing from a sibling or merging with a sibling.

Handling Underflow

Think of B-Tree nodes like storage shelves that must stay at least half-full. When one becomes too empty:

Borrowing: If an adjacent sibling has extra keys (more than the minimum), you can borrow one through the parent node. The parent acts as a middleman, rotating keys to rebalance both siblings while maintaining sort order.

Merging: If neighboring siblings are also at their minimum, you combine the underflowing node with a sibling and pull down a key from the parent to glue them together. This creates one fuller node but may cause the parent to underflow—potentially triggering a chain reaction up the tree.

Why This Matters

Database indexes must maintain their balanced structure to guarantee consistent search performance. Deletion is trickier than insertion because underflow can propagate upward, potentially even shrinking the tree's height.

Key Takeaway: Deleting from B-Tree leaf nodes requires checking for underflow and restoring balance through borrowing from siblings (when possible) or merging nodes together, maintaining the tree's fundamental search efficiency.