Concurrent algorithms for search structures (parallel, database)
Dennis E. Shasha · 1984
A search structure is a data structure that supports operations such as search, insert, and delete on a set of items. Common examples of search structures include lists, B-trees, and hash structures. Designing a sequential algorithm for a search structure is a well-understood problem. Designing a concurrent algorithm for such a structure is not. This thesis proposes a framework for the design and analysis of concurrent algorithms for search structures. It presents several new algorithms using this framework and describes a simulation kit to evaluate such algorithms. The framework has two salient features: a general model for search structures; and a correctness criterion based on specifications. We express algorithmic techniques as program fragments on the model. Because the model is general, these techniques apply to all search structures we know of. We consider computations to consist of actions at several levels of virtual machines. The highest level is the one that users interact with. Each action has a specification. For example, the specification of insert(x) is to ensure that x is in some set. We verify a concurrent computation by showing that it produces the same result as a sequence of user level actions performing according to their specifications. We present new algorithms for B-trees, multi-directory hash structures, and other search structures. We introduce concurrent algorithms for range queries, e.g. search for all items with keys between 100 and 110. These algorithms are only examples; one can design many more by following the guidelines of our framework. The purpose of the simulation kit is to evaluate the performance of concurrent search structure algorithms under a variety of conditions. As an example, we describe an experiment on eight B-tree algorithms.