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.7131504e-05
Overall Rank: 1,757 | 88.19%
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
499	Design of Flash-Based DBMS: An In-Page Logging Approach	2007	SIGMOD	0.0001729286
513	Tree Indexing on Solid State Drives	2010	VLDB	0.00017044842
2,841	Optimizing Optimistic Concurrency Control for Tree-Structured, Log-Structured Databases	2015	SIGMOD	7.9503824e-05
3,676	Fast General Distributed Transactions with Opacity	2019	SIGMOD	7.1063551e-05
4,935	Optimistic Concurrency Control by Melding Trees	2011	VLDB	6.3467229e-05
7,153	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.5979342e-05
7,325	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.5522404e-05
8,983	Resource-Adaptive Query Execution with Paged Memory Management	2025	CIDR	5.2433703e-05
9,622	Definition, Detection, and Recovery of Single-Page Failures, a Fourth Class of Database Failures	2012	VLDB	5.1496471e-05
10,725	How to Write to SSDs	2026	VLDB	4.9793485e-05
11,352	Enhancing Transaction Processing through Indirection Skipping	2025	VLDB	4.9793485e-05
12,268	Write-Optimized Skip Lists	2017	PODS	4.9793485e-05
12,560	NoFTL: Database Systems on FTL-less Flash Storage	2013	VLDB	4.9793485e-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.00039605949
137	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00029722253
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024274803
1,192	Data Compression in Oracle	2003	VLDB	0.00011590015
1,526	Key Range Locking Strategies for Improved Concurrency	1993	VLDB	0.0001035143
1,539	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010316015
1,586	Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance	2002	SIGMOD	0.00010146135
2,791	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.009544e-05
3,999	Write-Only Disk Caches	1990	SIGMOD	6.8623176e-05
7,949	Transaction Support in Read Optimized and Write Optimized File Systems	1990	VLDB	5.4208553e-05

Semantically Similar Papers

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