Two is Better Than One: The Case for 2-Tree for Skewed Data Sets

Summary: 2-Tree splits an index into hot (in-memory) and cold (on-disk) trees, using lightweight bidirectional migration and low-cost access tracking to enable per-tree tuning. Yields 15x (B+tree)/20x (LSM) memory-utilization gains and up to 1.7x throughput on Zipfian IO-bound workloads while preserving range-scan performance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4d6a3b826e82cf5a
Venue: CIDR
Year: 2023
Pagerank: 5.3938156e-05
Overall Rank: 8,129 | 45.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Xinjing Zhou (Massachusetts Institute of Technology)
2. Xiangyao Yu (University of Wisconsin)
3. Goetz Graefe (Google)
4. Michael Stonebraker (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{zhou_cidr23,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '23},
        title = {{Two is Better Than One: The Case for 2-Tree for Skewed Data Sets}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Zhou, Xinjing and Yu, Xiangyao and Graefe, Goetz and Stonebraker, Michael},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,360	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	6.1614422e-05
6,484	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.7696173e-05
8,473	Towards Buffer Management with Tiered Main Memory	2024	SIGMOD	5.3345353e-05
8,571	Practical DB-OS Co-Design with Privileged Kernel Bypass	2025	SIGMOD	5.3127636e-05
9,777	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.1314952e-05
10,228	From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads	2025	VLDB	5.0571508e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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
63	Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases	2017	SIGMOD	0.00038531147
70	The End of an Architectural Era (It’s Time for a Complete Rewrite)	2007	VLDB	0.00037859131
78	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036684414
80	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036364464
212	The LRU-K Page Replacement Algorithm For Database Disk Buffering	1993	SIGMOD	0.00024767296
543	Socrates: The New SQL Server in the Cloud	2019	SIGMOD	0.0001663263
728	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014414001
964	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012810196
971	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012766019
1,083	High Performance Transactions in Deuteronomy	2015	CIDR	0.00012113053
1,289	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00011162479
1,513	Cloud-Native Database Systems at Alibaba: Opportunities and Challenges	2019	VLDB	0.00010429438
1,524	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	0.00010356318
3,232	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	7.50343e-05
4,167	Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory	2021	SIGMOD	6.7656035e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,325	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
2	14,803	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
3	13,564	Experiments With B-Tree Reorganization	1980	SIGMOD
4	6,822	PIM-tree: A Skew-resistant Index for Processing-in-Memory	2023	VLDB
5	1,841	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
6	12,208	Splaying Log-Structured Merge-Trees	2018	SIGMOD
7	5,234	Multi-Disk B-trees	1991	SIGMOD
8	6,635	LSM-Trees and B-Trees: The Best of Both Worlds	2019	SIGMOD
9	9,998	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
10	1,085	On B-tree Indices for Skewed Distributions	1992	VLDB