A B+Tree Node Underflows: Merge or Borrow?
4 days ago
- #Index Maintenance
- #Database Performance
- #B+Tree
- B+Tree node underflow occurs when a delete operation reduces node occupancy below a minimum threshold, requiring rebalancing to maintain tree invariants.
- Modern B+Trees use optimistic latching protocols, but underflows force slower, pessimistic locking paths.
- Two strategies for fixing underflow: merge-first (prioritizes space efficiency) and borrow-first (prioritizes write speed).
- Merge-first approach can cause cascading rebalances but improves node density, cache locality, and reduces I/O for range scans.
- Borrow-first approach avoids cascading rebalances but results in lower node density and more I/O for range scans.
- MySQL InnoDB handles underflows via background merges, configurable with MERGE_THRESHOLD, but risks merge-split thrashing.
- PostgreSQL typically does nothing for underflows, only reclaiming space when a node becomes completely empty, prioritizing concurrency over space efficiency.
- Both systems trade-off index bloat for performance, shifting management of bloat to operators.