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.