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.1831862e-05
Overall Rank: 9,318 | 37.55%
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,585	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.1406489e-05
10,417	Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases	2027	VLDB	4.9605343e-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.00047937476
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046249672
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039323387
80	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036267455
147	Gorilla: A Fast, Scalable, In-Memory Time Series Database	2015	VLDB	0.00028941363
280	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022267903
427	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018429918
900	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013152699
912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013092547
1,370	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00010875068
1,849	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5008844e-05
1,981	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2505963e-05
2,017	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.169662e-05
2,474	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	8.3955114e-05
3,302	Efficient Index Compression in DB2 LUW	2009	VLDB	7.4220659e-05
5,398	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1338952e-05
6,737	CompressDB: Enabling Efficient Compressed Data Direct Processing for Various Databases	2022	SIGMOD	5.6777728e-05
6,920	MILC: Inverted List Compression in Memory	2017	VLDB	5.631163e-05
7,049	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5967284e-05
8,057	FCBench: Cross-Domain Benchmarking of Lossless Compression for Floating-Point Data	2024	VLDB	5.3829989e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
10,013	A Compact B-tree	2002	SIGMOD	5.0839435e-05

Semantically Similar Papers

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