The importance of multidimensional index structures to
numerous emerging database applications is well established.
However, before these index structures can be supported as
access methods in a ``commercial-strength'' database management
system (DBMS), efficient techniques to provide transactional
access to data via the index structure must be developed.
Concurrent access to data via a multidimensional index
structure introduces the problem of protecting the ranges
specified in the retrieval from phantom insertions and deletions
(the phantom problem). This paper presents a dynamic granular
locking approach to phantom protection in Generalized Search
Trees (GiSTs), an index structure supporting an extensible set
of queries and data types. GiSTs provide a set of interfaces
using which a new multidimensional index structure can be
easily integrated into a DBMS. The granular locking technique
provides a high degree of concurrency and has a low lock
overhead. Our experiments demonstrate that the technique scales
up to various degrees of system loads, complexities of
the data types and complexities of queries.
Since a wide variety of known multidimensional index structures
can be implemented using GiST, the developed algorithms provide
a general solution to concurrency control in multidimensional
access methods. To the best of our knowledge, this paper
provides the first such solution based on granular locking.