On-line Reorganization of Sparsely-populated B+-trees

Summary: Online reorg of sparsely-populated B+-trees, leaves-first leaf-group compaction with key-order preservation. Adds minimal-page locking concurrency, Forward Recovery for crash-consistency, and a swap-reduction heuristic; switch-over to a B+-tree. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2877
Venue: SIGMOD
Year: 1996
Pagerank: 8.0358014e-05
Overall Rank: 2,913 | 79.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Chendong Zou
2. Betty Salzberg

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,405	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.5105866e-05
4,739	Locality preserving dictionaries: theory & application to clustering in databases	1999	PODS	6.6010222e-05
4,772	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.5840052e-05
7,680	Online B-Tree Merging	2005	SIGMOD	5.6255454e-05
7,829	On-line Reorganization in Object Databases	2000	SIGMOD	5.6035684e-05
8,974	Online Index Rebuild	2000	SIGMOD	5.4069224e-05
12,682	Online Scaling in a Highly Available Database	2001	VLDB	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
213	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024933106
894	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD	0.0001340515
3,154	Access Method Concurrency with Recovery	1992	SIGMOD	7.759192e-05
5,028	Redo Recovery after System Crashes	1995	VLDB	6.4624997e-05
5,418	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.2957791e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,414	Random Sampling from Pseudo-Ranked B+ Trees	1992	VLDB	6.7790326e-05
6,151	Compact B-Trees	1979	SIGMOD	6.0346122e-05
5,474	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.2732796e-05
458	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.0001818345
5,057	Multi-Disk B-trees	1991	SIGMOD	6.4473481e-05
11,010	Breathing New Life into An Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage Drives	2024	VLDB	5.1725247e-05
10,380	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.1725247e-05
13,086	Experiments With B-Tree Reorganization	1980	SIGMOD	5.1725247e-05
12,852	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB	5.1725247e-05
7,680	Online B-Tree Merging	2005	SIGMOD	5.6255454e-05