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: 9365
Venue: VLDB
Year: 2004
Pagerank: 9.9081882e-05
Overall Rank: 1,731 | 88.13%
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
488	Design of Flash-Based DBMS: An In-Page Logging Approach	2007	SIGMOD	0.00017615543
512	Tree Indexing on Solid State Drives	2010	VLDB	0.00017196795
2,906	Optimizing Optimistic Concurrency Control for Tree-Structured, Log-Structured Databases	2015	SIGMOD	7.9741374e-05
3,624	Fast General Distributed Transactions with Opacity	2019	SIGMOD	7.2461483e-05
4,870	Optimistic Concurrency Control by Melding Trees	2011	VLDB	6.4709622e-05
7,016	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.7253247e-05
7,189	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	5.6775326e-05
8,818	Resource-Adaptive Query Execution with Paged Memory Management	2025	CIDR	5.3637177e-05
9,461	Definition, Detection, and Recovery of Single-Page Failures, a Fourth Class of Database Failures	2012	VLDB	5.2636619e-05
10,543	How to Write to SSDs	2026	VLDB	5.093636e-05
10,965	Enhancing Transaction Processing through Indirection Skipping	2025	VLDB	5.093636e-05
11,970	Write-Optimized Skip Lists	2017	PODS	5.093636e-05
12,269	NoFTL: Database Systems on FTL-less Flash Storage	2013	VLDB	5.093636e-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.00040060625
133	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00030370315
214	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024680756
1,222	Data Compression in Oracle	2003	VLDB	0.00011602327
1,501	Key Range Locking Strategies for Improved Concurrency	1993	VLDB	0.00010559899
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
1,567	Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance	2002	SIGMOD	0.00010343873
2,738	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.1875737e-05
3,938	Write-Only Disk Caches	1990	SIGMOD	7.0081626e-05
7,790	Transaction Support in Read Optimized and Write Optimized File Systems	1990	VLDB	5.5440082e-05

Semantically Similar Papers

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