Multiversion concurrency control for large-scale service directories

In this paper we describe the implementation of mul-tiversion concurrency control on the Generalized Search Tree (GiST), an index structure introduced by Hellerstein. For large-scale service directories, the need arises for a data storage system capable of handling substantial amounts of multidimensional data efficiently, as well as being able to support queries which are natural to the type of data stored in the directory. The GiST is an indexing structure that lends itself particularly well to this type of application. However, the solutions that have been proposed to address concurrency control on the GiST do not meet the requirements of large-scale service directo-ries. The solution proposed here optimizes towards highly concurrent read accesses that are far more frequent than updates to the stored data.