High-Concurrency Locking in R-Trees

Summary: R-link tree: a high-concurrency R-tree variant with B-link style sibling pointers for concurrent updates. Sequence numbers reconstruct lineage; operations avoid locks during I/O; degree-3 consistency with predicate locking; WAL recoverability; experiments show gains over basic locking. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hcf8a62ba026f7cdc
Venue: VLDB
Year: 1995
Pagerank: 7.633977e-05
Overall Rank: 3,113 | 79.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Marcel Kornacker (University of Hamburg)
2. Douglas Banks (University of California Berkeley)

BibTeX Citation

@article{kornacker_vldb95,
        title = {{High-Concurrency Locking in R-Trees}},
        author = {Kornacker, Marcel and Banks, Douglas},
        journal = {PVLDB},
        series = {{VLDB} '95},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
207	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024976482
2,065	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0904572e-05
2,199	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.8732148e-05
2,265	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.7267108e-05
2,912	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8683521e-05
6,618	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.7313827e-05
7,590	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4877983e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00081200096
99	The Design of the POSTGRES Storage System	1987	VLDB	0.00034019355
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024269058
472	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.0001769063
1,691	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	9.8555388e-05
3,170	Access Method Concurrency with Recovery	1992	SIGMOD	7.5681486e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,265	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD
2	5,662	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
3	2,390	Parallel R-trees	1992	SIGMOD
4	2,300	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,306	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
6	4,905	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
7	13,471	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,332	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
9	7,166	Operation Specific Locking In B-Trees	1987	PODS
10	1,691	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD