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: 1528
Venue: PODS
Year: 2010
Pagerank: 5.1785299e-05
Overall Rank: 10,009 | 31.33%
DOI: 10.1145/1807085.1807125

Incoming Non-self Citations Over Time

Authors

1. Michael A. Bender (State University of New York at Stony Brook; Tokutek, Inc.)
2. Haodong Hu (Microsoft)
3. Bradley C. Kuszmaul (Massachusetts Institute of Technology; Tokutek, Inc.)

BibTeX Citation

@inproceedings{bender_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Performance Guarantees for B-trees with Different-Sized Atomic Keys}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807125},
        doi = {10.1145/1807085.1807125},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bender, Michael A. and Hu, Haodong and Kuszmaul, Bradley C.},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,112	Cache-Oblivious String B-trees	2006	PODS	0.00012125766

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,246	Compact B-Trees	1979	SIGMOD
2	1,059	On B-tree Indices for Skewed Distributions	1992	VLDB
3	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
4	8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD
5	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
6	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
7	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
8	12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
9	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
10	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS