An In-Depth Analysis of Concurrent B-Tree Algorithms
Abstract
The B tree is a data structure designed to efficiently support dictionary operations for a variety of applications. In order to increases throughput, many algorithms have been proposed to maintain concurrent operations on B-tree. Replicating objects in memory can play a large role in concurrent B- tree performance, especially for large distributed and parallel systems. Because most replication schemes are coherent, readers generally cannot operate concurrently with a writer. This thesis presents two new concurrent B-trees algorithms. The first is an link algorithm that uses coherent replication; it is based on the Lehman-Yao algorithm which performs better than any other proposed concurrent B-tree algorithm. The second is a similar algorithm that uses multi- version memory, a new semantics for replicated memory. Multi-version memory weakens the semantics of coherent replication by allowing readers to read old versions of data. As a result, readers can perform in parallel with a writer. Also, implementations of multi-version memory require less communication and synchronization. Simulation experiments comparing a variety of concurrent B-tree algorithms show that the first algorithm has better performance than previously proposed algorithms and that the second algorithm has significantly better performance and scaling properties than any algorithms using coherent replicated memory.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1991
- Accession Number
- ADA232287
Entities
People
- Paul Wang
Organizations
- Massachusetts Institute of Technology