Write-Optimized B-Trees

Summary: Augments conventional B-trees with optional log-structured, large-write behavior while retaining in-place updates, direct node addressing, fine-grained locking, and ACID transactions. Inexpensive online page migration also supports defragmentation, free-space consolidation, compression, and range locking. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h95f03d9b804c60cf
Venue: VLDB
Year: 2004
Pagerank: 9.7107503e-05
Overall Rank: 1,757 | 88.20%
DOI: 10.1016/B978-012088469-8.50060-7

Incoming Non-self Citations Over Time

Authors

1. Goetz Graefe (Microsoft)

BibTeX Citation

@article{graefe_vldb04,
        title = {{Write-Optimized B-Trees}},
        author = {Graefe, Goetz},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {672--683},
        doi = {10.1016/B978-012088469-8.50060-7},
        url = {https://doi.org/10.1016/B978-012088469-8.50060-7},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
500	Design of Flash-Based DBMS: An In-Page Logging Approach	2007	SIGMOD	0.00017285624
513	Tree Indexing on Solid State Drives	2010	VLDB	0.00017040424
2,842	Optimizing Optimistic Concurrency Control for Tree-Structured, Log-Structured Databases	2015	SIGMOD	7.9468719e-05
3,678	Fast General Distributed Transactions with Opacity	2019	SIGMOD	7.1030964e-05
4,938	Optimistic Concurrency Control by Melding Trees	2011	VLDB	6.3439064e-05
7,029	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6152961e-05
7,156	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.5953223e-05
8,994	Resource-Adaptive Query Execution with Paged Memory Management	2025	CIDR	5.2408882e-05
9,629	Definition, Detection, and Recovery of Single-Page Failures, a Fourth Class of Database Failures	2012	VLDB	5.1472458e-05
10,735	How to Write to SSDs	2026	VLDB	4.9769913e-05
11,359	Enhancing Transaction Processing through Indirection Skipping	2025	VLDB	4.9769913e-05
12,274	Write-Optimized Skip Lists	2017	PODS	4.9769913e-05
12,566	NoFTL: Database Systems on FTL-less Flash Storage	2013	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
59	Differential Files: Their Application To The Maintenance Of Large Data Bases	1976	SIGMOD	0.00039592759
137	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00029708689
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024269058
1,192	Data Compression in Oracle	2003	VLDB	0.00011585228
1,528	Key Range Locking Strategies for Improved Concurrency	1993	VLDB	0.00010346983
1,540	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010311314
1,586	Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance	2002	SIGMOD	0.00010143882
2,791	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.0061967e-05
4,000	Write-Only Disk Caches	1990	SIGMOD	6.8592982e-05
7,953	Transaction Support in Read Optimized and Write Optimized File Systems	1990	VLDB	5.418389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,332	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
2	7,029	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB
3	12,214	Splaying Log-Structured Merge-Trees	2018	SIGMOD
4	2,018	A Practical Scalable Distributed B-Tree	2008	VLDB
5	630	Persistent B+-Trees in Non-Volatile Main Memory	2015	VLDB
6	3,026	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD
7	6,486	Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range Index	2024	VLDB
8	11,561	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB
9	9,559	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD
10	5,239	Multi-Disk B-trees	1991	SIGMOD