Name
Abstract | ||
|---|---|---|
We present a new algorithm for implementing a concurrent B-tree on a multiprocessor. The algorithm replicates B-tree nodes on multiple processors (particularly nodes near the root of the tree) to eliminate bottlenecks caused by contention for a single copy of each node. In contrast to other replication or caching strategies that provide some form of coherence, the algorithm uses a novel replication strategy, called multi-version memory . Multi-version memory weakens the semantics of coherent caches by allowing readers to access “old versions” of data. As a result, readers can run in parallel with a writer. Using multi-version memory for the internal nodes of a B-tree reduces the synchronization requirements and delays associated with updating the internal nodes. Experiments comparing the B-tree algorithm based on multi-version memory to other algorithms based on coherent replication show that using multi-version memory enhances throughput significantly, even for small numbers of processors, and also allows throughput to scale with increasing numbers of processors long past the point where other algorithms saturate and start to thrash. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1006/jpdc.1996.0003 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
multi-version memory,scalable concurrent b-trees | Data structure,Interleaved memory,Uniform memory access,Shared memory,Computer science,Parallel computing,B-tree,Distributed memory,Multiprocessing,Memory coherence,Distributed computing | Journal |
Volume | Issue | ISSN |
32 | 1 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
1 | 0.36 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Wang | 1 | 1 | 0.36 |
| William E. Weihl | 2 | 2614 | 903.11 |