BIB-VERSION:: CS-TR-v2.0
ID:: UCB//S2K-94-56
ENTRY:: January 4, 1995
DATE:: December 1994
TITLE:: High-Concurrency Locking in R-Trees*
AUTHOR:: Banks, Douglas
AUTHOR:: Kornacker, Marcel
AUTHOR:: Stonebraker, Michael
PAGES:: 15
ABSTRACT:: In this paper we present a solution to the problem of
        concurrent operations in R-trees, 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 pointers to nodes, a technique first deployed in
        B-link tree, a variant of the R-tree that adds sibling 
        pointers to nodes, a technique first deployed in B-link trees,
        to compensatyee 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, 
        insertion and deletion algorithms for R-link trees are designed
        to lock at most two nodes at a time and the locking can be 
        shown to be deadlock-free.  In addition, we describe how R-link
        trees can be made recoverable so that they are instantly 
        available after a crash and we further describe how to achieve
        degree 3 consistency with an inexpensive predicate locking
        mechanism.    

RETRIEVAL:: postscript  (in s2k-94-56.ps)
END::  UCB//S2K-94-56