B+ 树因其可证明的 I/O（缓存）效率而成为最常用的搜索索引。现有的批量并行二叉搜索树既快又易获取，但缺乏同等性能的批量并行 B+ 树。此前的 B+ 树设计要么仅是理论模型、缺少高性能实现，要么是并发索引（如 Bw-tree、Masstree），在批量更新时慢一个数量级。PaB-tree 是首个在工作量、跨度和缓存复杂度上都有保证且实际表现优异的批量并行 B+ 树。其核心难点是如何在不破坏 I/O 优势的前提下修复节点的溢出和欠载。我们通过一个简单的不变式解决：修复操作永不触及兄弟节点，总是向父节点传播。Promote 原语把批量构建和插入归约为重复的节点提升，把批量删除归约为重新插入。批量更新的工作量为 $O(B \log_{B} n)$，每个元素的 I/O 为 $O(\log_{B} n)$，与顺序 B+ 树的界限相同，且跨度为多项式对数级。与高度优化的并行和并发基线相比，PaB-tree 在整体性能上表现最佳：构建速度提升至 1.4 倍，批量插入提升至 3.6 倍，同时保持 B+ 树的查询效率。
点评