在计算机编程中，可持久化数据结构（Persistent data structure） 是一种能够在修改之后其保留历史版本（即可以在保留原来数据的基础上进行修改——比如增添、删除、赋值）的数据结构 。这种数据结构实际上是不可变对象 ，因为相关操作不会直接修改被保存的数据，而是会在原版本上产生一个新分支。这个术语是在1986年Driscoll、Sarnak、Sleator和Tarjans的文章中提出的。[1]
如果一个数据结构包括当前版本在内的所有历史版本都可以被访问，但只有当前版本可以被修改，那么该数据结构就是部分可持久化数据结构。如果该数据结构的所有版本都可以被查询或修改，那么这种数据结构就是完全可持久化数据结构。如果存在能够创建基于两个历史版本的新版本（即合并两个版本 meld() （浇铸（？） 混合（？））或 merge() （合并）操作），那么这种数据结构就是可汇合的可持久化数据结构。不可持久化的数据结构被称为短暂性数据结构 。[2]
这些类型的数据结构在逻辑编程 和函数式编程 之中非常常见。[2]
部分可持久化与完全可持久化 在部分可持久化模型中，编程者可以查询该类数据结构的任一历史版本，但是只能修改（更新）最新版本。这意味着数据结构的每个版本之间是线性排序 的。[3] Rope 数据结构 [4] [5]
保留历史版本的方法 “Copy on Write”（写入时复制） 创建可持久化数据结构的一种方式是使用平台提供的短暂数据结构（比如数组 ）来存储数据结构中的数据，并对对于数据结构的任何更改使用复制整个数据结构 的方式来记录每次更改。这是一种效率低下的技术，因为每次写入都必须复制整个数据结构，这使得对一个大小为 n {\displaystyle n} m {\displaystyle m} O ( n m ) {\displaystyle {\text{O}}(nm)} [來源請求]
“Fat node”（胖节点） “胖节点”的方法是将对于该节点的所有更改记录在节点本身，但是在修改时不覆盖节点上原来的数值。这就要求允许节点能任意“变胖”。换句话说，每一个胖节点都包含了与它的历史版本的信息和指针字段 ，同时还拥有任意数量的额外字段值空间。每个额外的字段值都有一个相关联的字段名和一个版本戳，它表示该节点在哪个版本中被更改和被改为值。此外，每个胖节点都有自己的版本戳，用于记录该版本是在那个版本中被修改的。节点的版本戳的唯一目的是确保每个节点在被一个版本中的每一个字段仅仅包含一个唯一的值。为了浏览结构，每个节点中每个原始字段值的版本戳为零。
“胖节点”算法的时间复杂度 使用“胖节点”算法完成可持久化，每次修改需要 O ( 1 ) {\displaystyle {\text{O}}(1)} O ( 1 ) {\displaystyle {\text{O}}(1)} 均摊分析 的（假设修改历史存储在一个可以扩大的数组 之中）。在查询时，必须遍历整个结构以找到每个节点的正确的版本。如果要进行 m {\displaystyle m} O ( log m ) {\displaystyle {\text{O}}(\log m)}
“Path copying”（路径复制） 路径复制算法，将即将被修改的点路径上的所有节点克隆出一个新的。这些修改必须通过数据结构逐级连接：克隆而得的所有节点指向旧节点的指针必须被修改为指向新节点。这些修改会引起连锁更改，直达根节点。
參考資料 ^ Driscoll JR, Sarnak N, Sleator DD, Tarjan RE. Making data structures persistent. 1986: 109–121. ISBN 978-0-89791-193-1doi:10.1145/12130.12142 . ^ 2.0 2.1 Kaplan, Haim. Persistent data structures. Handbook on Data Structures and Applications. 2001 [2020-07-29 ] . （原始内容于2020-07-29）. ^ Conchon, Sylvain; Filliâtre, Jean-Christophe, Semi-persistent Data Structures, Programming Languages and Systems, Lecture Notes in Computer Science 4960 , Springer Berlin Heidelberg: 322–336, 2008, ISBN 9783540787389doi:10.1007/978-3-540-78739-6_25 ^ Tiark, Bagwell, Philip Rompf. RRB-Trees: Efficient Immutable Vectors. 2011. OCLC 820379112 . ^ Brodal, Gerth Stølting; Makris, Christos; Tsichlas, Kostas, Purely Functional Worst Case Constant Time Catenable Sorted Lists, Lecture Notes in Computer Science (Springer Berlin Heidelberg), 2006: 172–183, ISBN 9783540388753doi:10.1007/11841036_18
外部連結
可持久化数据结构, 在计算机编程中, persistent, data, structure, 是一种能够在修改之后其保留历史版本, 即可以在保留原来数据的基础上进行修改, 比如增添, 删除, 赋值, 的数据结构, 这种数据结构实际上是不可变对象, 因为相关操作不会直接修改被保存的数据, 而是会在原版本上产生一个新分支, 这个术语是在1986年driscoll, sarnak, sleator和tarjans的文章中提出的, 如果一个数据结构包括当前版本在内的所有历史版本都可以被访问, 但只有当前版本可以被修改, . 在计算机编程中 可持久化数据结构 Persistent data structure 是一种能够在修改之后其保留历史版本 即可以在保留原来数据的基础上进行修改 比如增添 删除 赋值 的数据结构 这种数据结构实际上是不可变对象 因为相关操作不会直接修改被保存的数据 而是会在原版本上产生一个新分支 这个术语是在1986年Driscoll Sarnak Sleator和Tarjans的文章中提出的 1 如果一个数据结构包括当前版本在内的所有历史版本都可以被访问 但只有当前版本可以被修改 那么该数据结构就是部分可持久化数据结构 如果该数据结构的所有版本都可以被查询或修改 那么这种数据结构就是完全可持久化数据结构 如果存在能够创建基于两个历史版本的新版本 即合并两个版本 meld 浇铸 混合 或 merge 合并 操作 那么这种数据结构就是可汇合的可持久化数据结构 不可持久化的数据结构被称为短暂性数据结构 2 这些类型的数据结构在逻辑编程和函数式编程之中非常常见 2 目录 1 部分可持久化与完全可持久化 2 保留历史版本的方法 2 1 Copy on Write 写入时复制 2 2 Fat node 胖节点 2 2 1 胖节点 算法的时间复杂度 2 3 Path copying 路径复制 3 參考資料 4 外部連結部分可持久化与完全可持久化 编辑在部分可持久化模型中 编程者可以查询该类数据结构的任一历史版本 但是只能修改 更新 最新版本 这意味着数据结构的每个版本之间是线性排序的 3 在完全持久化模型中 编程者可以查询和修改 更新 该类数据结构的所有版本 在某些情况之下 允许查询和或修改 更新 历史版本的功能会削减 比如 Rope 数据结构 英语 Rope data structure 就是如此 4 另外 如果一个数据结构除了完全可持久化外 还可以将同种数据结构的两个版本合并成一个新的版本 且这个新版本仍然是完全持久化的 那么这个数据结构就可以被称为可汇合的持久化的 5 保留历史版本的方法 编辑 Copy on Write 写入时复制 编辑 创建可持久化数据结构的一种方式是使用平台提供的短暂数据结构 比如数组 来存储数据结构中的数据 并对对于数据结构的任何更改使用复制整个数据结构的方式来记录每次更改 这是一种效率低下的技术 因为每次写入都必须复制整个数据结构 这使得对一个大小为 n displaystyle n 的数组进行 m displaystyle m 次修改时 出现最差情况下的时间复杂度为 O n m displaystyle text O nm 來源請求 Fat node 胖节点 编辑 胖节点 的方法是将对于该节点的所有更改记录在节点本身 但是在修改时不覆盖节点上原来的数值 这就要求允许节点能任意 变胖 换句话说 每一个胖节点都包含了与它的历史版本的信息和指针字段 同时还拥有任意数量的额外字段值空间 每个额外的字段值都有一个相关联的字段名和一个版本戳 它表示该节点在哪个版本中被更改和被改为值 此外 每个胖节点都有自己的版本戳 用于记录该版本是在那个版本中被修改的 节点的版本戳的唯一目的是确保每个节点在被一个版本中的每一个字段仅仅包含一个唯一的值 为了浏览结构 每个节点中每个原始字段值的版本戳为零 胖节点 算法的时间复杂度 编辑 使用 胖节点 算法完成可持久化 每次修改需要 O 1 displaystyle text O 1 的空间 只需要存储新数据 每一次修改都需要额外的 O 1 displaystyle text O 1 的时间来在历史版本的结尾处存储更改 这是均摊分析的 假设修改历史存储在一个可以扩大的数组之中 在查询时 必须遍历整个结构以找到每个节点的正确的版本 如果要进行 m displaystyle m 次修改 那么每一次查询操作都会遭到 O log m displaystyle text O log m 的减速 这是在数组中寻找最近修改的版本造成的 Path copying 路径复制 编辑 路径复制算法 将即将被修改的点路径上的所有节点克隆出一个新的 这些修改必须通过数据结构逐级连接 克隆而得的所有节点指向旧节点的指针必须被修改为指向新节点 这些修改会引起连锁更改 直达根节点 參考資料 编辑 Driscoll JR Sarnak N Sleator DD Tarjan RE Making data structures persistent 1986 109 121 ISBN 978 0 89791 193 1 doi 10 1145 12130 12142 journal 被忽略 帮助 2 0 2 1 Kaplan Haim Persistent data structures Handbook on Data Structures and Applications 2001 2020 07 29 原始内容存档于2020 07 29 Conchon Sylvain Filliatre Jean Christophe Semi persistent Data Structures Programming Languages and Systems Lecture Notes in Computer Science 4960 Springer Berlin Heidelberg 322 336 2008 ISBN 9783540787389 doi 10 1007 978 3 540 78739 6 25 Tiark Bagwell Philip Rompf RRB Trees Efficient Immutable Vectors 2011 OCLC 820379112 Brodal Gerth Stolting Makris Christos Tsichlas Kostas Purely Functional Worst Case Constant Time Catenable Sorted Lists Lecture Notes in Computer Science Springer Berlin Heidelberg 2006 172 183 ISBN 9783540388753 doi 10 1007 11841036 18 外部連結 编辑 取自 https zh wikipedia org w index php title 可持久化数据结构 amp oldid 73311265, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。