Revisiting B-tree Compression: An Experimental Study

Summary: First head-to-head experimental study of 7 classic B-tree compression schemes, spanning synthetic and real workloads. Quantifies when compression actually helps (space, cache/I/O, query speed) and distills design guidance for modern index systems. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6994
Venue: SIGMOD
Year: 2024
Pagerank: 5.256602e-05
Overall Rank: 9,518 | 34.70%
DOI: 10.1145/3654972

Incoming Non-self Citations Over Time

Authors

1. Chuqing Gao (Purdue University)
2. Shreya Ballijepalli (Purdue University)
3. Jianguo Wang (Purdue University)

BibTeX Citation

@inproceedings{gao_sigmod24,
        title = {{Revisiting B-tree Compression: An Experimental Study}},
        author = {Gao, Chuqing and Ballijepalli, Shreya and Wang, Jianguo},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654972},
        url = {https://dl.acm.org/doi/10.1145/3654972},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.214913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00047648573
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0003955489
83	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036185259
148	Gorilla: A Fast, Scalable, In-Memory Time Series Database	2015	VLDB	0.00029250767
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
447	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018322593
921	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013209503
925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013182044
1,342	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00011098147
1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.6941032e-05
2,023	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2950046e-05
2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.9183396e-05
2,563	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	8.412445e-05
3,244	Efficient Index Compression in DB2 LUW	2009	VLDB	7.6033499e-05
5,285	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.2821588e-05
6,791	MILC: Inverted List Compression in Memory	2017	VLDB	5.7723936e-05
7,173	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	5.6830655e-05
7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6775326e-05
7,890	FCBench: Cross-Domain Benchmarking of Lossless Compression for Floating-Point Data	2024	VLDB	5.521314e-05
8,349	Tree-Encoded Bitmaps	2020	SIGMOD	5.4460774e-05
9,794	A Compact B-tree	2002	SIGMOD	5.2187932e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,810	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
2	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
3	3,949	A New Compression Method with Fast Searching on Large Databases	1987	VLDB
4	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
5	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
6	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
7	6,246	Compact B-Trees	1979	SIGMOD
8	14,479	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD
9	2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
10	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD