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: 487
Venue: CIDR
Year: 2023
Pagerank: 4.5658208e-05
Overall Rank: 8,183 | 43.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,840	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	4.9109345e-05
7,154	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	4.815267e-05
8,428	Towards Buffer Management with Tiered Main Memory	2024	SIGMOD	4.5158105e-05
9,185	Practical DB-OS Co-Design with Privileged Kernel Bypass	2025	SIGMOD	4.3792034e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,773	From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads	2025	VLDB	4.1945683e-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
86	The End of an Architectural Era (It's Time for a Complete Rewrite)	2007	VLDB	0.00052563276
87	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00052389723
137	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042342967
156	Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases	2017	SIGMOD	0.00040504295
183	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036721403
306	The LRU-K Page Replacement Algorithm For Database Disk Buffering	1993	SIGMOD	0.00028228982
918	Socrates: The New SQL Server in the Cloud	2019	SIGMOD	0.00015350181
982	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014872253
1,312	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012652548
1,405	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012174592
1,457	High Performance Transactions in Deuteronomy	2015	CIDR	0.00011897016
1,729	Cloud-Native Database Systems at Alibaba: Opportunities and Challenges	2019	VLDB	0.0001073728
1,827	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00010390548
2,076	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	9.6059442e-05
4,235	Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory	2021	SIGMOD	6.3342932e-05
4,427	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	6.1965873e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,995	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	4.6109825e-05
14,292	Towards an Optimal Data-Structure: CB-trees	1984	VLDB	-
13,073	Experiments With B-Tree Reorganization	1980	SIGMOD	4.1945683e-05
7,099	PIM-tree: A Skew-resistant Index for Processing-in-Memory	2023	VLDB	4.8326366e-05
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
11,704	Splaying Log-Structured Merge-Trees	2018	SIGMOD	4.1945683e-05
5,098	Multi-Disk B-trees	1991	SIGMOD	5.7007294e-05
7,343	LSM-Trees and B-Trees: The Best of Both Worlds	2019	SIGMOD	4.7568442e-05
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677