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|
|Number of pages||10|
|State||Published - 1986|
ASJC Scopus subject areas