Towards a B+-tree with Fluctuation-Free Performance

Abstract

Performance predictability is critical for modern DBMSs. Index maintenance can trigger rare but severe I/O spikes. In a B/B+-tree of Height H, due to node split propagation, the cost of a single insert can vary from (H + 1) I/Os when node split does not happen to (3H + 1) I/Os when split propagation reaches the root, nearly a 3 times degradation. We formalize performance fluctuation as the gap between the best- and worst-case insert behaviors. We show examples of why performance fluctuation is worth investigating. To mitigate the B/B+-tree split propagation, we introduce the FFBtree, a B+-tree with a novel insert and delete algorithms with bounded-fluctuation performance. We prove that the insert operation is guaranteed to encounter at most one node that needs to be split, and hence ensuring that no split propagation can take place. The new insert and delete algorithms guarantee bounded-fluctuation performance for the FFBtree. Experiments with simulated indexes show that the FFBtree caps I/O fluctuation compared to baseline indexes under various workloads.