1. A persistent data structure is a data structure that always preserves the previous version of itself when it is modified. They can be considered as ‘immutable’ as updates are not in-place. A data structure is partially persistent if all versions can be accessed but only the newest version can be modified. Fully persistent if every version can be both accessed and modified. Confluently persistent is when we merge two or more versions to get a new version. This induces a DAG on the version graph.
2. A persistent data structure is one in which no operations result in permanent changes to the underlying structure. It's called “persistent” because as the structure goes through successive operations, all versions of the structure persist over time. The notion of a structure with no permanent changes may sound like an oxymoron: The simplest example, a stack, will illustrate.
http://www.geeksforgeeks.org/persistent-data-structures/ (1.); http://www.toves.org/books/persist/ (2.)
Author: Simon Waterstradt