算法与数据结构 / 持久化与不可变结构 · 从 path copying 到 RRB-tree 待审核 7 页

持久化与不可变结构 · 从 path copying 到 RRB-tree

一个数据结构叫 persistent，是说它的每次修改都产出一个新版本，而全部旧版本仍可查询。朴素做法是每次全量复制，代价 O(n)O(n)；实测里这个代价大得离谱——10 万元素的数组做 1 万次「改一格并留档」，光格子写入就是 10910^9 次，按每格 8 字节算 7.6 GB。

path copying 把这笔账压到 O(log⁡n)O(\log n)：树形结构里改一个叶子，只有根到该叶子这一条路径上的节点需要新建，其余子树两个版本共用同一批对象。10 万元素的 32 叉 trie 树深只有 4，于是一次修改新建 4 个节点、共享 3223 个，共享率 99.88%。本系列前两页把这件事画出来，并用它做出主席树的区间第 kk 小。

后半是工程实现。HAMT 用 bitmap 加 popcount 把 32 槽节点压到只存实际存在的孩子，是 Clojure、Scala 与 Immutable.js 的 Map 底层；bit-partitioned vector 换成按下标的二进制位分段，加一个 tail 让尾部 append 摊还常数；transient 用所有权标记临时放弃持久性，把 10 万次 push 的新建节点从 11441 个降到 3228 个；RRB-tree 给节点挂 size table，让 concat 与 slice 也进对数级。

地基：路径复制与三个持久化级别

partial / full / confluent 三级的分野是「哪些版本能被改、能不能合并」，而三级共用同一个手法。把线段树的一次单点修改改写成 path copying 之后，旧根一个字节都不动，新根与旧根共享 2n−2−⌈log⁡2n⌉2n - 2 - \lceil \log_2 n \rceil 个节点——这个共享量就是主席树能存下 nn 个前缀版本的全部理由。

path copying · partial / full / confluent

路径复制与持久化的分级

持久化按「哪些版本可改、能否合并」分成 partial、full、confluent 三级，三级共用同一个手法。path copying 改一个叶子只重建根到该叶子的路径，其余子树按引用共享，一次修改的额外空间因此是 O(log n)。

 persistent segment tree · 前缀版本 · 值域作差

可持久化线段树与区间第 k 小

把 path copying 用到值域计数线段树上，每插入一个数就留下一个版本。两个前缀版本相减即得任意区间的值分布，于是区间第 k 小只需一次自顶向下的下探。实测 10 万数据 1 万次查询 21.7 ms。

为什么持久化几乎总是从树形结构起手

path copying 的代价是「根到被改位置的路径长度」，所以它只在路径短的结构上划算。数组的「路径」是整个数组，链表的路径是前缀，两者都退化成 O(n)O(n)。平衡树与 trie 的路径是 O(log⁡n)O(\log n)，这才是持久化文献几乎只谈树的原因。 反过来说，任何结构只要先套一层树形索引就能持久化：数组套线段树（见 路径复制与三个持久化级别），hash table 套 trie（见 HAMT），队列与双端队列套 finger tree。代价是常数变大，收益是版本数从 1 变成任意多。

持久化的理论一侧 · 延伸阅读

32 叉 trie 的两种索引来源

HAMT 与 persistent vector 的骨架相同：分支因子 32、树深不超过 7、一次修改只复制一条路径。分歧只在「第几层看哪几位」——HAMT 看 hash 的 5 位一段，故节点稀疏、要 bitmap 压缩；vector 看下标的 5 位一段，故节点致密、可纯位运算。RRB-tree 是第三种：允许节点不满，代价是索引要查 size table。

hash array mapped trie · bitmap · popcount

HAMT：bitmap 加 popcount 的 32 叉 trie

Clojure 与 Immutable.js 的不可变 Map 底层。32 叉 trie 每层吃 hash 的 5 位，节点用一个 32 位 bitmap 加一个紧凑数组表示，孩子下标由 popcount 算出。

 下标分段 · tail · Clojure vector

bit-partitioned persistent vector

Clojure 的 vector 与 Immutable.js 的 List 底层。同样是 32 叉 trie，索引却来自下标的二进制位，再加一个 tail 缓冲让尾部 append 摊还常数。10 万元素树深 4。

 relaxed radix balanced · size table · 接缝

RRB-tree：让 concat 与 slice 也进对数级

严格 radix 树要求除末尾外每个节点都装满，而 concat 与 slice 必然破坏这个前提。RRB 允许节点松弛，用一张 size table 换来对数级的拼接与切片。实测 20 万元素拼接只新建 5 个节点。

分支因子 32 不是「树深最小」算出来的

树深 ⌈log⁡32n⌉\lceil \log_{32} n \rceil 在 n=105n = 10^5 时是 4，换成 64 叉是 3——单看深度，更宽更好。但一次修改要复制沿途每个节点的整个孩子数组，代价是 O(blog⁡bn)O(b \log_b n)：bb 越大，每层复制越贵。b=32b = 32 的实测账是一次 set 新建 4 个节点、复制 4×32=1284 \times 32 = 128 个指针。 32 这个值另有两条现实理由：一个 32 位 bitmap 刚好索引 32 个槽（b=64b = 64 就要 64 位掩码，JS 的位运算只有 32 位）；32 个指针在 64 位机上是 256 字节，正好四条 cache line。Bagwell 在 2001 年的论文里试过 16 与 32，选了后者。

HAMT / vector / RRB · 一手资料

落到工程：批量构建与共享的代价

不可变结构在生产里能用，靠的是两件正文常常略过的事。transient 让批量构建期间的中间版本不必真的存在；引用相等让「这棵子树变没变」的判断从逐项比较降成一次指针比较——实测 10 万项的深比较单次 45.5 µs，指针比较 17.2 ns。代价也有：只保留最新版本时，91.9% 的新建节点当即成为垃圾。

transient · ownership · withMutations

transient：临时放弃持久性的可变窗口

批量构建时每一步都造一个不可变中间版本，代价全部浪费。transient 给节点打上所有权标记，标记对得上就原地改，构建完再冻结。实测 10 万次 set 的新建节点从 399872 降到 3227。

 写入量 · GC 压力 · 引用相等

结构共享的代价与收益

结构共享把「改一格并留档」的写入量降了四个数量级，但墙钟时间只降一个量级，而且九成新建节点当场成垃圾。真正无法用别的手段换来的收益是引用相等：一次指针比较回答关于十万个元素的问题。

不可变数据在前端 · 延伸阅读