Online B-Tree Merging

Summary: Online B-tree merging of two indexes with the same key range; leaf-page merges piggyback on transactions, yielding single-index visibility. Forward-recoverable merging with logging ensures consistency and no lost work; experiments show IO savings. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3709
Venue: SIGMOD
Year: 2005
Pagerank: 5.5415082e-05
Overall Rank: 7,804 | 46.46%
DOI: 10.1145/1066157.1066196

Incoming Non-self Citations Over Time

Authors

1. Xiaowei Sun (Northeastern University)
2. Rui Wang (Northeastern University)
3. Betty Salzberg (Northeastern University)
4. Chendong Zou (IBM)

BibTeX Citation

@inproceedings{sun_sigmod05,
        title = {{Online B-Tree Merging}},
        author = {Sun, Xiaowei and Wang, Rui and Salzberg, Betty and Zou, Chendong},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066196},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066196},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,843	Rose: Compressed, log-structured replication	2008	VLDB	8.0617003e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
214	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024680756
807	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.00013884448
924	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD	0.00013185068
958	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012956148
981	Incremental Organization for Data Recording and Warehousing	1997	VLDB	0.0001284025
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
2,968	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.9149281e-05
3,114	Access Method Concurrency with Recovery	1992	SIGMOD	7.7405805e-05
3,416	Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases	1996	SIGMOD	7.430628e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05
4,839	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.4838601e-05
5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.1856695e-05
9,103	Online Index Rebuild	2000	SIGMOD	5.3245321e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,114	Access Method Concurrency with Recovery	1992	SIGMOD
2	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
3	7,026	Operation Specific Locking In B-Trees	1987	PODS
4	6,396	Contention and Space Management in B-Trees	2021	CIDR
5	9,103	Online Index Rebuild	2000	SIGMOD
6	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
7	1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR
8	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
9	1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD
10	2,968	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD