可持久化資料結構

在计算机编程中，可持久化数据结构（Persistent data structure）是一种能够在修改之后其保留历史版本（即可以在保留原来数据的基础上进行修改——比如增添、删除、赋值）的数据结构。这种数据结构实际上是不可变对象，因为相关操作不会直接修改被保存的数据，而是会在原版本上产生一个新分支。这个术语是在1986年Driscoll、Sarnak、Sleator和Tarjans的文章中提出的。 如果一个数据结构包括当前版本在内的所有历史版本都可以被访问，但只有当前版本可以被修改，那么该数据结构就是部分可持久化数据结构。如果该数据结构的所有版本都可以被查询或修改，那么这种数据结构就是完全可持久化数据结构。如果存在能够创建基于两个历史版本的新版本（即合并两个版本 meld （浇铸（？）混合（？））或 merge （合并）操作），那么这种数据结构就是可汇合的可持久化数据结构。不可持久化的数据结构被称为短暂性数据结构。 这些类型的数据结构在逻辑编程和函数式编程之中非常常见。