High-Concurrency Locking in R-Trees.

Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145

@inproceedings{DBLP:conf/vldb/KornackerB95,
  author    = {Marcel Kornacker and
               Douglas Banks},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {High-Concurrency Locking in R-Trees},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {134-145},
  ee        = {db/conf/vldb/KornackerB95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we present a solution to the problem of concurrent operations in the R-tree, a dynamic access structure capable of storing multidimensional and spatial data. We describe the R-link tree, a variant of the R-tree that adds sibling pointersto nodes, a technique first deployed in B-link trees, to compensate for concurrent structure modifications. The main obstacle to the use of sibling pointers is the lack of linear ordering among the keys in an R-tree; we overcome this by assigning sequence numbers to nodes that let us reconstruct the "lineage" of a node at any point in time. The search, insert and delete algorithms for R-link trees are designed to completely avoid holding locks during I/O operations and to allow concurrent modifications of the tree structure. In addition, we further describe how to achieve degree 3 consistency with an inexpensive predicate locking mechanism and demonstrate how to make R-link trees recoverable in a write-ahead logging environment. Experiments verify the performance advantage of R-link trees over simpler locking protocols.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents

References

[BaMc72]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[BaSc77]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977)
[Bent75]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975)
[BKS94]: ...
[BKSS90]: Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
[EGLT76]: Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976)
[Gray78]: Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481
[Gutt84]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[Illu94]: ...
[JoSh93]: Theodore Johnson, Dennis Shasha: The Performance of Current B-Tree Algorithms. ACM Trans. Database Syst. 18(1): 51-101(1993)
[LaSh86]: Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389
[LeYa81]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
[LoSa90]: David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990)
[LoSa92]: David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360
[Moha89]: C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405
[MoLe89]: C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380
[NgKa93]: Vincent Ng, Tiko Kameda: Concurrent Access to R-Trees. SSD 1993: 142-161
[Niev84]: Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
[Robi81]: John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18
[Sagi86]: Yehoshua Sagiv: Concurrent Operations on B*-Trees with Overtaking. J. Comput. Syst. Sci. 33(2): 275-296(1986)
[SrCa91]: V. Srinivasan, Michael J. Carey: Performance of B-Tree Concurrency Algorithms. SIGMOD Conference 1991: 416-425
[SRF87]: Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518
[Ston87]: Michael Stonebraker: The Design of the POSTGRES Storage System. VLDB 1987: 289-300