A B+Tree Node Underflows: Merge or Borrow?

Summary

A B+Tree Node Underflows: Merge or Borrow? 16-Aug-2025 A B+Tree's stable algorithmic performance relies on a single invariant: the path from its root to any leaf is always the same length. However, a delete operation can cause a node to underflow (falling below its minimum occupancy), triggering a rebalancing procedure to maintain this critical invariant. Modern B+Trees use fast, optimistic latching protocols which operate under the assumption that rebalancing happens rarely. The mere possibility of an underflow can force the rebalancing into the slow, pessimistic path, acquiring exclusive locks that stall other operations. How the implementation decides to fix the underflow is therefore a critical design choice: merge with a sibling node to reclaim free space, or borrow keys from a sibling node to minimize the impact on write latency. Simply put, it's a classic trade-off between space and time. In this post, we will also explore how major OLTP systems expertly implement sophisticated strategies which go beyond this classic trade-off. Table of Contents Fixing Node Underflow In OLTP systems Key Takeaways Fixing Node Underflow A node underflow happens when the used space (or occupancy) within a node falls below a minimum threshold. This is a possibility after removing an entry from the node. A viable solution is to do nothing. By doing nothing, a tree balancing procedure is never activated. The major downside though is index bloat. A failure to garbage collect the unused memory results in the nodes becoming progressively sparse as entries continue to be added and removed. In contrast, a node overflow will always trigger a tree rebalancing because it creates a new node whose reference needs to be inserted in the parent node. Here, doing nothing is not even an available option. The two basic strategies for fixing node underflow both involve merging and borrowing. They differ by which operation is executed first: a merge or a borrow. The merge-first approach prioritizes ...