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: hcbfcd8e58a2d33aa
Venue: SIGMOD
Year: 2024
Pagerank: 5.138658e-05
Overall Rank: 9,699 | 34.79%
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,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.0979044e-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
35	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00048001919
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046284649
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.000392237
80	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036364464
148	Gorilla: A Fast, Scalable, In-Memory Time Series Database	2015	VLDB	0.0002900671
282	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022264207
430	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018409112
900	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013186558
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013123912
1,366	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00010912114
1,841	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5268075e-05
1,973	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2834606e-05
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
2,484	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	8.3993882e-05
3,296	Efficient Index Compression in DB2 LUW	2009	VLDB	7.4473548e-05
5,397	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1490013e-05
6,737	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	5.6925989e-05
6,906	MILC: Inverted List Compression in Memory	2017	VLDB	5.6498626e-05
7,325	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5522404e-05
8,033	FCBench: Cross-Domain Benchmarking of Lossless Compression for Floating-Point Data	2024	VLDB	5.4034154e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
9,977	A Compact B-tree	2002	SIGMOD	5.1016975e-05

Semantically Similar Papers

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