SCALABLE CONCURRENT B-TREES USING MULTIVERSION MEMORY

We present a new algorithm for implementing a concurrent B-tree on a m ultiprocessor, The algorithm replicates B-tree nodes on multiple proce ssors (particularly nodes near the root of the tree) to eliminate bott lenecks caused by contention for a single copy of each node. In contra st to other replication or caching strategies that provide some form o f coherence, the algorithm uses a novel replication strategy, called m ulti-version memory. Multi-version memory weakens the semantics of coh erent caches by allowing readers to access ''old versions'' of data. A s a result, readers can run in parallel with a writer. Using multi-ver sion memory for the internal nodes of a B-tree reduces the synchroniza tion requirements and delays associated with updating the internal nod es, Experiments comparing the B-tree algorithm based on multi-version memory to other algorithms based on coherent replication show that usi ng multiversion memory enhances throughput significantly, even for sma ll numbers of processors, and also allows throughput to scale with inc reasing numbers of processors long past the point where other algorith ms saturate and start to thrash. (C) 1996 Academic Press, Inc.