EUVIMEDEUVIMED entdecken
Crossref

Bounding the Fragmentation of B-Trees Subject to Batched Insertions

Michael A. Bender, Aaron Bernstein, Nairen Cao, Alex Conway, Martín Farach-Colton, Hanna Komlós, Yarin Shechter, Nicole Wein

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →