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.6094637e-05
Overall Rank: 3,121 | 79.09%
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
210	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024910589
2,076	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.0622765e-05
2,211	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	8.8443254e-05
2,279	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.6989205e-05
2,923	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8423791e-05
6,625	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.7130455e-05
7,607	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.4696523e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00081207565
101	The Design of the POSTGRES Storage System	1987	VLDB	0.00033939695
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.0002420049
475	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00017634372
1,698	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	9.8232497e-05
3,180	Access Method Concurrency with Recovery	1992	SIGMOD	7.5432668e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,279	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD
2	5,675	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
3	2,400	Parallel R-trees	1992	SIGMOD
4	2,311	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,324	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
6	4,929	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
7	13,512	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,373	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
9	7,187	Operation Specific Locking In B-Trees	1987	PODS
10	1,698	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD