Back to papers

Performance Guarantees for B-trees with Different-Sized Atomic Keys

Summary: Defines an "atomic-key" B-tree model for opaque, variable-length keys and gives B-tree-like expected-cost bounds parameterized by average key size K: static search O(ceil(K/B) log_{1+ceil(B/K)} N) and dynamic amortized insert O(ceil(K/B) log_{1+ceil(B/K)} N + |kappa|/B) transfers. Minimal structural change (pivot choice), builds in O(NK) work (O(NK/B) transfers if sorted), proves worst-case bounds impossible, and provides a DP to construct optimal expected-cost search trees. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID

1529

Venue

PODS

Year

2010

Pagerank

4.269353e-05

Overall Rank

9,859 | 31.42%

DOI

-