Symmetric concurrent B-tree algorithm

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.