Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917335885938688 |
|---|---|
| author | Bender, Michael A. Bernstein, Aaron Cao, Nairen Conway, Alex Farach-Colton, Martín Komlós, Hanna Shechter, Yarin Wein, Nicole |
| author_facet | Bender, Michael A. Bernstein, Aaron Cao, Nairen Conway, Alex Farach-Colton, Martín Komlós, Hanna Shechter, Yarin Wein, Nicole |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_12211 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bounding the Fragmentation of B-Trees Subject to Batched Insertions Bender, Michael A. Bernstein, Aaron Cao, Nairen Conway, Alex Farach-Colton, Martín Komlós, Hanna Shechter, Yarin Wein, Nicole Data Structures and Algorithms Databases 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. |
| title | Bounding the Fragmentation of B-Trees Subject to Batched Insertions |
| topic | Data Structures and Algorithms Databases |
| url | https://arxiv.org/abs/2603.12211 |