下标分段 · tail · Clojure vector

bit-partitioned persistent vector

上一页的 HAMT 解决的是「按 key 取值」。按下标取值是另一回事：下标是连续的，不需要 hash，也不会稀疏。Clojure 的 PersistentVector 与 Immutable.js 的 List 就是为这个场景做的，骨架仍是 32 叉 trie，换掉的只有一件事——每层看的是下标的位，不是 hash 的位。

这个替换带来两个连锁后果。其一，trie 变得致密：下标 $0$ 到 $n-1$ 连续，除最后一个孩子外每个节点都装满 32 个，bitmap 与 popcount 这套稀疏压缩用不上也不需要。其二，索引变成纯移位与掩码，没有任何查表。

1 · 下标即路径

把下标 $i$ 的二进制按 5 位一段从低位切开：最低 5 位是叶子内的偏移，往上每 5 位是一层的孩子号。

\text{child}_d = (i \gg 5d) \mathbin{\&} 31, \qquad d = D-1, D-2, \dots, 0

$D$ 是树高。根节点的 shift 字段记着 $5(D-1)$ ，下降时每层减 5。整趟索引没有比较、没有分支，只有 $D$ 次移位加掩码。

图 1-1 · 下标的二进制被切成若干 5 位段，每段就是一层的孩子号。可拖动下标观察各段取值，也可把下标推到末尾 32 格看它落进 tail 而不进树。

2 · tail 缓冲

朴素实现里每次 push 都要新建一片叶子并复制沿途的内部节点，代价是 $O(\log_{32} n)$ 个节点。而 append 是 vector 最高频的操作，这笔账在建表场景里会占满全部开销。

Clojure 的做法是给尾部留一个不进树的裸数组，长度不超过 32。push 先往这个数组里塞；塞满 32 个之后才把它整片挂进树，同时开一个新的空数组。读操作对称：下标不小于 tailOff（即 size 减 tail.length）就直接查这个数组。

图 2-1 · 逐次 push 时 tail 的填充与树的生长，日志里每一步标出该步新建的树节点数。可连续 push 观察 32 步里只有 1 步碰树。

10 万次 push 的实测：96876 次（96.88%）一个树节点也没新建，只有 3124 次触发了「tail 挂进树」。摊还下来每次 push 新建 0.114 个节点。tail 还顺带优化了尾部的顺序读：迭代最后 32 个元素不必反复下降 4 层。

3 · 树深与新建量

树高只在树装满时涨一档。32 叉下的实测：

元素数	树深	tail 里	树内节点数
32	1	32	0
1024	2	32	32
32768	3	32	1056
100000	4	32	3227
1000000	4	32	32258

$32^7 = 34359738368$ ，远超 JS 数组的长度上限 $2^{32}-1$ ，所以任何实际规模的 vector 树深都不超过 7。工程上把 $O(\log_{32} n)$ 的随机访问当常数看，依据就是这个。

一次 set 复制根到该叶子的整条路径：10 万元素的 vector 上新建 4 个节点、与旧版本共享 3223 个，共享率 99.88%。

估算这一页的数字时栽过一次。按「每 32 次 push 挂一片叶子，偶尔还要建一两个上层节点」估，10 万次 push 应该新建三千多个节点；实测是 11441 个，差了三倍半。漏掉的是路径复制本身：每挂一片叶子，从根到它的那条路径上的每一个内部节点都要复制一份，而不只是新增的那一个。3124 次挂叶子平均每次新建 3.66 个节点，正好是当时的树高。最终活着的确实只有 3227 个（3124 片叶子加 98 加 4 加 1 个根），其余 8214 个在下一次挂叶子时就成了垃圾。「新建量」与「常驻量」是两个数，摊还分析算的是前者，内存占用看的是后者。

4 · 与 HAMT 的分野

两者的骨架完全一样：分支因子 32、树深不超过 7、写操作沿一条路径复制。列出分歧更有用。

	HAMT	bit-partitioned vector
索引来源	`hash(key)` 的 5 位一段	下标本身的 5 位一段
节点是否稀疏	稀疏，要 `bitmap` 加 `popcount`	致密，直接用数组下标
树是否平衡	由 hash 分布决定，实测第 4 到 6 层	恒定，全部叶子同深
有无碰撞处理	要 collision 节点	不需要
尾部优化	无意义	tail，摊还 append 常数
顺序遍历	要走完整棵 trie	叶子天然按下标有序

值得留意的是「致密」这条的连带收益：既然每个内部节点除最后一个外都满 32 个孩子，节点里就不必存孩子数，shift 一个字段就够描述整棵树的形状。RRB-tree 恰恰是放弃这条不变量换来 concat 与 slice 的对数化，代价见 RRB-tree。

5 · 参考文献

Bagwell, P. (2001). Ideal hash trees. Technical Report LAMP-REPORT-2001-001, EPFL.
Hickey, R. (2009). Persistent data structures and managed references. QCon London. Clojure 的 PersistentVector 设计说明。
L'orange, J. N. (2013). Understanding Clojure's persistent vectors, parts 1–3. hypirion.com
Bagwell, P., & Rompf, T. (2011). RRB-Trees: Efficient immutable vectors. Technical Report, EPFL.