Making data structures persistent

James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

461 Scopus citations


This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and efficient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.

Original languageEnglish (US)
Pages (from-to)86-124
Number of pages39
JournalJournal of Computer and System Sciences
Issue number1
StatePublished - Feb 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Making data structures persistent'. Together they form a unique fingerprint.

Cite this