Multiversion Concurrency Control for Multidimensional Index Structures

摘要

Prevailing concurrency control mechanisms for multidimensional index structures, such as the Generalized Search Tree (GiST), are based on locking techniques. These approaches may cause significant overhead in settings where the indexed data is rarely updated and read access is highly concurrent. In this paper we present the Multiversion-GiST (MVGiST), which extends the GiST with Multiversion Concurrency Control. Beyond enabling lock-free read access, our approach provides readers a consistent view of the whole index structure, which is achieved through the creation of lightweight, read-only versions of the GiST that share unchanging nodes amongst themselves. Our evaluation confirms that for low update rates, the MVGiST significantly improves scalability w.r.t. the number of concurrent accesses when compared to a traditional, locking-based concurrency control mechanism.