The B+-tree is the de‑facto search index because of its provable I/O (cache) efficiency. Batch‑parallel binary search trees are both fast and widely available, yet a batch‑parallel B+-tree with comparable empirical performance and near‑optimal I/O guarantees has been missing. Existing B+-tree‑based designs are either purely theoretical without high‑performance implementations, or concurrent indexes such as Bw‑tree and Masstree that run an order of magnitude slower on batch updates. PaB-tree is the first batch‑parallel B+-tree that offers guarantees on work, span and cache complexity while delivering strong practical performance. The main challenge—repairing node overflows and underflows without losing the tree’s I/O advantage—is solved by a single invariant: a repair never touches a sibling and is always pushed to the parent. A Promote primitive reduces batch construction and insertion to repeated node promotion, and batch deletion to reinsertion. Batch updates require $O(B \log_{B} n)$ work and $O(\log_{B} n)$ I/O per element, matching sequential B+-tree bounds, with polylogarithmic span. Against highly‑optimized parallel and concurrent baselines, PaB-tree achieves the best overall trade‑off: up to 1.4× faster construction and up to 3.6× faster batch insertion while preserving B+-tree query efficiency.
Review