Bounding the Fragmentation of B-Trees Subject to Batched Insertions

Michael A. Bender, Aaron Bernstein, Nairen Cao +5

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 o…