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: 486
Venue: CIDR
Year: 2023
Pagerank: 5.5070057e-05
Overall Rank: 8,016 | 45.01%
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
6,498	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	5.861854e-05
6,742	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.7862414e-05
8,357	Towards Buffer Management with Tiered Main Memory	2024	SIGMOD	5.4446759e-05
9,345	Practical DB-OS Co-Design with Privileged Kernel Bypass	2025	SIGMOD	5.284891e-05
9,599	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.2492748e-05
11,002	From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads	2025	VLDB	5.093636e-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
38	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00047648573
68	The End of an Architectural Era (It’s Time for a Complete Rewrite)	2007	VLDB	0.00038446206
73	Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases	2017	SIGMOD	0.00037333356
83	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00036185259
86	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00035316107
231	The LRU-K Page Replacement Algorithm For Database Disk Buffering	1993	SIGMOD	0.00023846898
604	Socrates: The New SQL Server in the Cloud	2019	SIGMOD	0.0001584774
720	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014632914
948	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.0001303916
964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012934147
1,089	High Performance Transactions in Deuteronomy	2015	CIDR	0.00012242396
1,344	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00011094717
1,524	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	0.00010501517
1,559	Cloud-Native Database Systems at Alibaba: Opportunities and Challenges	2019	VLDB	0.00010362456
3,535	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	7.3333933e-05
4,110	Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory	2021	SIGMOD	6.8948348e-05

Semantically Similar Papers

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