Symmetric concurrent B-tree algorithm

Vladimir Lanin, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationFall joint computer conference, November 1986
EditorsHarold S. Stone
Number of pages10
ISBN (Print)0818607432
StatePublished - 1986

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Symmetric concurrent B-tree algorithm'. Together they form a unique fingerprint.

Cite this