Metraipolis › archive › dc_ef046b299b8d
PaB-tree: Parallel B+-tree with Batch Updates — arXiv:2611.09172
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09172
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:36:35.646Z
- SHA-256 of the archived text
73d52b210a194b63781ab4fd86c7bcd0cbaa5fdbef376f7243af36a2026d34fb- Stable URL of this page
https://metraipolis.com/documento/dc_ef046b299b8d
How to cite
PaB-tree: Parallel B+-tree with Batch Updates — arXiv:2611.09172 — arXiv (en), https://arxiv.org/abs/2611.09172 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ef046b299b8d (Metraipolis archive dc_ef046b299b8d, sha256 73d52b210a194b63781ab4fd86c7bcd0cbaa5fdbef376f7243af36a2026d34fb)
BibTeX
@misc{dcef046b299b8d,
title = {PaB-tree: Parallel B+-tree with Batch Updates — arXiv:2611.09172},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09172},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ef046b299b8d; sha256 73d52b210a194b63781ab4fd86c7bcd0cbaa5fdbef376f7243af36a2026d34fb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09172. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The B+-tree is a ubiquitous search index due to its provable I/O (cache) efficiency. Yet unlike batch-parallel binary search trees, which are both fast and widely available, no batch-parallel B+-tree offers strong empirical performance together with provable, near-optimal I/O efficiency. Prior B+-tree-based designs are either parallel but purely theoretical, with no high-performance implementation, or concurrent indexes such as the Bw-tree and Masstree, which run an order of magnitude slower on batch updates. We present PaB-tree, the first batch-parallel B+-tree with guarantees on work, span, and cache complexity alongside strong practical performance. Its core challenge -- repairing node overflows and underflows without eroding the tree's I/O advantage -- is resolved by one simple 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 take O(B log_B n) work and O(log_B n) I/O per element, matching the sequential B+-tree bounds, with polylogarithmic span. Against highly-optimized parallel and concurrent baselines, PaB-tree delivers the best overall performance trade-off: up to 1.4x faster on construction and up to 3.6x faster on batch insertion than the strongest baseline, while preserving B+-tree query efficiency. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB); Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2611.09172 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-09T22:31:17.065Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).