Concurrent search structure algorithms

Dennis Shasha, Nathan Goodman

Research output: Contribution to journalArticlepeer-review


A dictionary is an abstract data type supporting the actions member, insert, and delete. A search structure is a data structure used to implement a dictionary. Examples include B trees, hash structures, and unordered lists. Concurrent algorithms on search structures can achieve more parallelism than standard concurrency control methods would suggest, by exploiting the fact that many different search structure states represent one dictionary state. We present a framework for verifying such algorithms and for inventing new ones. We give several examples, one of which exploits the structure of Banyan family interconnection networks. We also discuss the interaction between concurrency control and recovery as applied to search structures.

Original languageEnglish (US)
Pages (from-to)53-90
Number of pages38
JournalACM Transactions on Database Systems (TODS)
Issue number1
StatePublished - Jan 3 1988


  • Algorithms
  • B-tree
  • concurrency
  • data structure
  • hash structure
  • parallel

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Concurrent search structure algorithms'. Together they form a unique fingerprint.

Cite this