Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-25
DOI: 10.1145/3801894 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Michael A. Bender und 7 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben. Gefördert von: National Science Foundation, Alfred P. Sloan Foundation, Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity.
Abstract (Originalsprache)
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves of a B-tree against a workload of uniformly random insertions achieves space utilization of around 69%. However, many database applications perform batched insertions, where a small run of consecutive keys is inserted at a single position. We develop a generalization of Yao's analysis to provide rigorous treatment of such batched workloads. Our approach revisits and reformulates the analytical structure underlying Yao's result in a way that enables generalization and is used to argue that even splitting works well for many workloads in our extended class. For the remaining workloads, we develop simple alternative strategies that provably maintain good space utilization.
Förderung
- National Science Foundation
- Alfred P. Sloan Foundation
- Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity
Zitieren
APA
Bender, M. A., Bernstein, A., Cao, N., Conway, A., Farach-Colton, M., Komlós, H., Shechter, Y., & Wein, N. (2026). Bounding the Fragmentation of B-Trees Subject to Batched Insertions. Proceedings of the ACM on Management of Data, 4(2), 1-25. https://doi.org/10.1145/3801894
Vancouver
Bender MA, Bernstein A, Cao N, Conway A, Farach-Colton M, Komlós H, et al. Bounding the Fragmentation of B-Trees Subject to Batched Insertions. Proceedings of the ACM on Management of Data. 2026;4(2):1-25. doi:10.1145/3801894
BibTeX
@article{Bender2026,
author = {Bender, Michael A. and Bernstein, Aaron and Cao, Nairen and Conway, Alex and Farach-Colton, Martín and Komlós, Hanna and Shechter, Yarin and Wein, Nicole},
title = {Bounding the Fragmentation of B-Trees Subject to Batched Insertions},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--25},
doi = {10.1145/3801894}
}
EUVIMED