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: 8454
Venue: VLDB
Year: 1995
Pagerank: 7.807389e-05
Overall Rank: 3,057 | 79.03%
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
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,155	Integrating the UB-Tree into a Database System Kernel	2000	VLDB	9.0713545e-05
2,227	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.9111106e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
6,488	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.865078e-05
7,463	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB	5.6111155e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
99	The Design of the POSTGRES Storage System	1987	VLDB	0.00034506601
214	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024680756
464	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00018055592
1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD	0.00010073735
3,114	Access Method Concurrency with Recovery	1992	SIGMOD	7.7405805e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,227	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD
2	5,530	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS
3	2,341	Parallel R-trees	1992	SIGMOD
4	2,257	Concurrency Control of Nested Transactions Accessing B-Trees	1989	PODS
5	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
6	4,783	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS
7	13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	13,036	New Concurrency Control Algorithms for Accessing and Compacting B-Trees	1994	VLDB
9	7,026	Operation Specific Locking In B-Trees	1987	PODS
10	1,663	Performance of B-Tree Concurrency Control Algorithms	1991	SIGMOD