Abstract
The authors present a method for concurrent B-tree manipulation in which insertions are performed as in an earlier paper by P. Lehman and S. B. Yao (1981) and deletions are done in a symmetrical, novel fashion. The result is an algorithm in which each process holds locks on at most one node at a time, except in rare cases. To allow this low level of synchronization, the integrity constraints on the data structure are reexamined. This information is useful in verifying the algorithm by a general semantic serializability proof method. Simulation shows that the algorithm is capable of achieving significantly better concurrency than algorithms that perform insertions and deletions symmetrically.
Original language | English (US) |
---|---|
Title of host publication | Fall joint computer conference, November 1986 |
Editors | Harold S. Stone |
Publisher | IEEE |
Pages | 380-389 |
Number of pages | 10 |
ISBN (Print) | 0818607432 |
State | Published - 1986 |
ASJC Scopus subject areas
- General Engineering