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.2003819e-05
Overall Rank: 9,295 | 37.53%
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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,559	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.1577035e-05
10,350	Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases	2027	VLDB	4.9769913e-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.00047996489
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039236924
80	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036354352
148	Gorilla: A Fast, Scalable, In-Memory Time Series Database	2015	VLDB	0.00029001141
277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022320139
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
898	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.0001318387
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013122392
1,366	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00010908555
1,839	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5284548e-05
1,974	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2806652e-05
2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.1924806e-05
2,483	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	8.3973995e-05
3,293	Efficient Index Compression in DB2 LUW	2009	VLDB	7.4456263e-05
5,388	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1520776e-05
6,736	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	5.6914316e-05
6,908	MILC: Inverted List Compression in Memory	2017	VLDB	5.6471881e-05
7,029	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6152961e-05
8,040	FCBench: Cross-Domain Benchmarking of Lossless Compression for Floating-Point Data	2024	VLDB	5.4008575e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3286931e-05
9,982	A Compact B-tree	2002	SIGMOD	5.1008099e-05

Semantically Similar Papers

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