Compact B-Trees

Summary: Compact B-trees are minimal-node B-trees among equally capacious trees of the same order, achieving optimal space utilization. Shows up to 2.5x space savings over visit-optimal B-trees, with node-visit cost at most 1 more than optimal; gives a linear-time, in-place compactification algorithm. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2156
Venue: SIGMOD
Year: 1979
Pagerank: 5.9425753e-05
Overall Rank: 6,246 | 57.15%
DOI: 10.1145/582095.582102

Incoming Non-self Citations Over Time

Authors

1. Arnold L. Rosenberg (IBM)
2. Lawrence Snyder (Yale University)

BibTeX Citation

@inproceedings{rosenberg_sigmod79,
        title = {{Compact B-Trees}},
        author = {Rosenberg, Arnold L. and Snyder, Lawrence},
        series = {{SIGMOD} '79},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582095.582102},
        url = {https://dl.acm.org/doi/10.1145/582095.582102},
        year = {1979}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,274	Experiments With B-Tree Reorganization	1980	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
2	8,943	Compact O-Complete Trees	1988	VLDB
3	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
4	10,149	Bounding the Fragmentation of B-Trees Subject to Batched Insertions	2026	PODS
5	14,493	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
6	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
7	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
8	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
9	9,518	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
10	14,479	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD