relaxed radix balanced · size table · 接缝

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

bit-partitioned vector 把 get、set、push、pop 全压到了 $O(\log_{32} n)$ ，却把 concat 与 slice 留在 $O(n)$ ：两者都要把结果整棵重建。对一个以「拼接文本片段」「取子序列」为主的场景来说，这等于没有持久化。

Bagwell 与 Rompf 在 2011 年给出的答案 [1] 只改一条不变量。

1 · 被 concat 打破的前提

纯位运算索引成立，靠的是一个很强的前提：每个内部节点除最后一个孩子外都恰好装满 32 个。有了它，第 $d$ 层的孩子号才能直接由下标的第 $5d$ 到 $5d+4$ 位读出。

concat 一定会破坏它。把长度 70 的向量接到长度 90 的后面，接缝处必然出现一个只有 6 个元素的叶子夹在中间。要恢复严格性只有一条路：把接缝右边的所有元素整体左移，也就是重建整棵右树。slice 同理，左端切在叶子中间时，后面全部元素的下标都要平移。

2 · size table 与松弛节点

定义 2.1（relaxed radix balanced tree） 一棵允许内部节点不满的 32 叉 trie。节点分两态：严格节点不带额外字段，索引走 $(i \gg \text{shift}) \mathbin{\&} 31$ ；松弛节点带一张 size table，即孩子规模的前缀和，索引时找第一个大于 $i$ 的表项，再把 $i$ 减去前一项回到子树的局部坐标。

两态共存是关键：一次 concat 只让接缝附近的少数节点变松弛，其余整棵子树仍是严格的，索引落到那里就退回纯位运算。判定一个新建节点是否严格，只需检查它的孩子是否都严格、且除最后一个外规模都等于 $32^{\text{level}}$ 。

图 2-1 · 拼接后的树上一次索引的逐层走法，橙色行是要查 size table 的松弛节点。可拖动下标越过接缝，观察走法在位运算与查表之间切换。

论文里给 size table 的查找留了个优化：从 $(i \gg \text{shift}) \mathbin{\&} 31$ 这个「假如严格会落在哪」的位置起线性向后扫，因为松弛节点只会比严格更「靠后」，平均扫不了几步。引擎里没做这一步，直接从 0 开始扫；节点最多 32 个孩子，差别在这个规模上量不出来。

3 · 接缝处的合并

concat 的做法是沿两棵树的接缝递归下探：取左树的最后一个孩子与右树的第一个孩子，在下一层继续合并，直到叶子层把两片不满的叶子并成一片（若装得下）。回溯时把左树剩下的孩子、合并结果、右树剩下的孩子拼成一个新节点；孩子数超过 32 就一分为二，超不过就只留一个，树高不涨。

图 3-1 · concat 与 slice 各自新建多少节点、复用多少，以及结果树里松弛节点的分布。可切到 slice 模式观察左端切口留下的碎叶子。

实测（两侧各是严格建出来的向量）：

操作	新建节点	复用节点	全量重建要建
1000 接 1000	3	64	66
100000 接 100000	5	6450	6454
100000 接 5	3	3226	3229
100000 取中间 40000	7	1288	1293

时间上，20 万元素的拼接是 0.0041 ms，同样内容全量重建一棵严格树是 2.023 ms，差 493 倍。slice 的账相同：只有左右两条边界路径要重建，中间整段子树原样挂过来。

4 · 不做完整再平衡的代价

论文的 concat 还有一步本页实现里没有的操作：合并完之后检查接缝附近节点的「search step」不变量（大意是节点数不得比理论最少值多出超过一个阈值），不满足就把这一层的孩子重新摊平。跳过它是有意的取舍，因为那一步的代码量大约是其余部分的总和，而它换来的只是常数因子。

代价可以量出来。把 10 万个长度 1 到 40 的小向量依次接成一个 2050937 元素的大向量：

指标	本实现	同规模严格树
树深	5	5
节点总数	90425	66161
叶子数	85107	64092
平均每片叶子的元素数	24.10	32.00
最瘦的叶子	1	1
松弛节点数	5318	0

树深没有恶化，这一条比预想的好——原先担心不做再平衡会让树越接越深，实测它稳定在与严格树相同的 5 层，因为「孩子数不超过 32 就不加层」这条规则本身已经把大部分松弛吸收掉了。真正付出的代价在密度：节点多 1.37 倍，叶子的平均填充率从 100% 掉到 75%。换算成读操作，多出来的 1.37 倍节点意味着同样的遍历要碰更多 cache line；换算成内存，多占三分之一。

警示 · 「没有再平衡，反复 slice 加 concat 会让密度单调恶化」这个担心被实测否掉了。保持规模在 5 万、连做 4000 轮「随机切一刀再首尾对调拼回去」，平均每叶始终是 31.97 个元素、节点 1618 个（同规模严格树 1615 个），四千轮下来一点没退化——每次 concat 都会把接缝上两片不满的叶子并成一片，正好抵掉 slice 制造的碎片。会累积的是另一种负载：把大量本身就不满 32 的小片段接起来，那些短叶子没有对手可并，填充率停在 24.10。判据因此不是「有没有 slice」，而是「拼进来的片段本身满不满」。上表的「最瘦的叶子 1 个元素」就出自后一种负载。

5 · 什么时候需要它

RRB 不是 bit-partitioned vector 的免费升级版：多出来的 size table 判断让所有索引都慢一点，即使树里一个松弛节点也没有。Scala 的 Vector 在 2.13 之后用了 RRB 风格的实现，Clojure 的 PersistentVector 至今没有。

判据是工作负载里 concat 与 slice 的占比。以 append 与随机读为主的场景，严格树更好；以「把若干片段拼起来」「取子序列」为主的场景，例如文本编辑器的 rope、并行计算的分块归并、不可变列表的 splice，RRB 把这两个操作从线性降到对数，量级上的改变盖过常数因子。

6 · 参考文献

Bagwell, P., & Rompf, T. (2011). RRB-Trees: Efficient immutable vectors. Technical Report EPFL-REPORT-169879, EPFL.
Stucki, N., Rompf, T., Ureche, V., & Bagwell, P. (2015). RRB vector: A practical general purpose immutable sequence. ICFP 2015, 342–354.
L'orange, J. N. (2014). Improving RRB-Tree performance through transience. Master's thesis, NTNU.
Scala 标准库 scala.collection.immutable.Vector 的 2.13 重写说明。