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