TreeLine: An Update-In-Place Key-Value Store for Modern Storage

Summary: TreeLine revisits update-in-place KV storage for NVMe SSDs, exploiting their parallel random-write performance to avoid LSM read penalties. Record caching, page grouping, and insert forecasting mitigate point, scan, and reorganization costs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8931a5f353d50104
Venue: VLDB
Year: 2023
Pagerank: 7.5008192e-05
Overall Rank: 3,233 | 78.28%
DOI: 10.14778/3561261.3561270
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Geoffrey X. Yu (Massachusetts Institute of Technology)
2. Markos Markakis (Massachusetts Institute of Technology)
3. Andreas Kipf (Massachusetts Institute of Technology)
4. Per-Åke Larson (University of Waterloo)
5. Umar Farooq Minhas (Apple)
6. Tim Kraska (Massachusetts Institute of Technology)

BibTeX Citation

@article{yu_vldb23,
        title = {{TreeLine: An Update-In-Place Key-Value Store for Modern Storage}},
        author = {Yu, Geoffrey X. and Markakis, Markos and Kipf, Andreas and Larson, Per-Åke and Minhas, Umar Farooq and Kraska, Tim},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {1},
        pages = {99--112},
        doi = {10.14778/3561261.3561270},
        url = {https://doi.org/10.14778/3561261.3561270},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 26 of 26 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,878	Oasis: An Optimal Disjoint Segmented Learned Range Filter	2024	VLDB	6.369385e-05
5,221	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	6.2207378e-05
6,123	Learning to Optimize LSM-trees: Towards A Reinforcement Learning based Key-Value Store for Dynamic Workloads	2023	SIGMOD	5.8771312e-05
6,486	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB	5.766886e-05
6,867	Accelerating String-key Learned Index Structures via Memoization-based Incremental Training	2024	VLDB	5.6581046e-05
7,869	Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD	2024	VLDB	5.4342182e-05
8,075	Two is Better Than One: The Case for 2-Tree for Skewed Data Sets	2023	CIDR	5.3921263e-05
8,228	ArceKV: Towards Workload-driven LSM-compactions for Key-Value Store Under Dynamic Workloads	2026	VLDB	5.3734043e-05
8,326	How to Grow an LSM-tree? Towards Bridging the Gap Between Theory and Practice	2025	SIGMOD	5.3522236e-05
9,064	Aster: Enhancing LSM-structures for Scalable Graph Database	2025	SIGMOD	5.2270607e-05
9,124	Check Out the Big Brain on BRAD: Simplifying Cloud Data Processing with Learned Automated Data Meshes	2023	VLDB	5.2247088e-05
9,140	Rethinking The Compaction Policies in LSM-trees	2025	SIGMOD	5.2208299e-05
9,191	Structural Designs Meet Optimality: Exploring Optimized LSM-tree Structures in A Colossal Configuration Space	2024	SIGMOD	5.20942e-05
9,601	Can Learned Indexes be Built Efficiently? A Deep Dive into Sampling Trade-offs	2024	SIGMOD	5.153951e-05
9,782	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	5.129066e-05
10,234	From FASTER to F2: Evolving Concurrent Key-Value Store Designs for Large Skewed Workloads	2025	VLDB	5.0547568e-05
10,567	Counting Is All You Need for Instant Tuple Discovery: Enabling Real-Time HTAP in Standalone DBMSs	2026	SIGMOD	4.9769913e-05
10,663	Improving Range Scan Performance in LSM-trees with Group Caching	2026	SIGMOD	4.9769913e-05
10,680	Predictive Translation: High-Performance Buffer Management Without the Trade-Offs	2026	SIGMOD	4.9769913e-05
10,735	How to Write to SSDs	2026	VLDB	4.9769913e-05
10,737	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.9769913e-05
10,854	Rethinking Learned Index and LSM-tree Integration	2026	VLDB	4.9769913e-05
10,906	Tidehunter: Large-Value Storage With Minimal Data Relocation	2026	VLDB	4.9769913e-05
11,306	STsCache: An Efficient Semantic Caching Scheme for Time-series Data Workloads Based on Hybrid Storage	2025	VLDB	4.9769913e-05
11,561	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	4.9769913e-05
11,563	Sorting on Byte-Addressable Storage: The Resurgence of Tree Structure	2024	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
40	The Case for Learned Index Structures	2018	SIGMOD	0.00046363107
400	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019124757
422	ALEX: An Updatable Adaptive Learned Index	2020	SIGMOD	0.00018488849
458	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017880664
546	Faster: A Concurrent Key-Value Store with In-Place Updates	2018	SIGMOD	0.00016584272
768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014107655
817	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013685662
835	Benchmarking Learned Indexes	2021	VLDB	0.00013575971
1,422	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	0.00010720711
1,891	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	9.4233024e-05
1,982	Chucky: A Succinct Cuckoo Filter for LSM-Tree	2021	SIGMOD	9.2570284e-05
3,480	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2661848e-05
6,990	FASTER: An Embedded Concurrent Key-Value Store for State Management	2018	VLDB	5.6256457e-05
7,739	High-Performance Geospatial Analytics in HyPerSpace	2016	SIGMOD	5.4616281e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,091	MirrorKV: An Efficient Key-Value Store on Hybrid Cloud Storage with Balanced Performance of Compaction and Querying	2023	SIGMOD
2	10,663	Improving Range Scan Performance in LSM-trees with Group Caching	2026	SIGMOD
3	6,639	LSM-Trees and B-Trees: The Best of Both Worlds	2019	SIGMOD
4	6,242	Toward a Better Understanding and Evaluation of Tree Structures on Flash SSDs	2021	VLDB
5	10,735	How to Write to SSDs	2026	VLDB
6	6,934	Breaking Down Memory Walls in LSM-based Storage Systems	2020	SIGMOD
7	12,214	Splaying Log-Structured Merge-Trees	2018	SIGMOD
8	5,221	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB
9	817	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB
10	10,678	PartitionKV: Redesigning LSM-tree KV Stores on NVMs with Adaptive Partitioning for Reducing Write Stalls and Amplification	2026	SIGMOD