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.5614825e-05
Overall Rank: 8,185 | 43.12%
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,838	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	4.906223e-05
7,152	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	4.8126591e-05
8,422	Towards Buffer Management with Tiered Main Memory	2024	SIGMOD	4.5114807e-05
9,189	Practical DB-OS Co-Design with Privileged Kernel Bypass	2025	SIGMOD	4.3750062e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,779	From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads	2025	VLDB	4.1905499e-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
87	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00052844656
88	The End of an Architectural Era (It's Time for a Complete Rewrite)	2007	VLDB	0.0005262025
136	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042409816
156	Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases	2017	SIGMOD	0.00040580118
183	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036859633
306	The LRU-K Page Replacement Algorithm For Database Disk Buffering	1993	SIGMOD	0.00028255083
914	Socrates: The New SQL Server in the Cloud	2019	SIGMOD	0.00015370799
980	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014868633
1,300	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012711153
1,306	BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory	2018	VLDB	0.00012674725
1,447	High Performance Transactions in Deuteronomy	2015	CIDR	0.0001192999
1,721	Cloud-Native Database Systems at Alibaba: Opportunities and Challenges	2019	VLDB	0.00010741822
1,816	An Inquiry into Machine Learning-based Automatic Configuration Tuning Services on Real-World Database Management Systems	2021	VLDB	0.00010438512
2,075	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	9.6115775e-05
4,404	TreeLine: An Update-In-Place Key-Value Store for Modern Storage	2023	VLDB	6.2052645e-05
4,816	Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory	2021	SIGMOD	5.897817e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,990	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	4.6086117e-05
14,306	Towards an Optimal Data-Structure: CB-trees	1984	VLDB	-
13,086	Experiments With B-Tree Reorganization	1980	SIGMOD	4.1905499e-05
7,097	PIM-tree: A Skew-resistant Index for Processing-in-Memory	2023	VLDB	4.8280402e-05
1,807	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.0001047644
11,709	Splaying Log-Structured Merge-Trees	2018	SIGMOD	4.1905499e-05
5,217	Multi-Disk B-trees	1991	SIGMOD	5.621547e-05
7,341	LSM-Trees and B-Trees: The Best of Both Worlds	2019	SIGMOD	4.7522998e-05
10,380	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1905499e-05
639	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018782897