持久化数据结构

定义

持久化数据结构(Persistent Data Structure)指每次"修改"都返回新版本、同时旧版本仍然可用的数据结构。它并非把数据写入磁盘的"持久化存储",而是版本意义上的持久:所有历史版本都可继续读取甚至更新。

原理

关键技术是结构共享(Structural Sharing):新版本只复制从根到被改节点路径上的少量节点,其余部分与旧版本共享。以宽分支的树(如 32 叉的 HAMT 与 RRB-Tree)实现向量与哈希表,可把每次更新的代价控制在近似常数级别。Chris Okasaki 的《Purely Functional Data Structures》系统研究了该领域。

应用

Clojure 的 vector/map、Scala 的默认不可变集合、Haskell 的容器库都基于持久化结构;JavaScript 生态的 Immutable.js、Immer 亦借鉴此思想。Git 的对象模型同样是持久化树的典型应用。

优缺点

优点是天然线程安全、支持廉价快照与撤销/重做;代价是常数因子高于可变结构,且依赖垃圾回收管理共享节点。