25. 翻译： RRB-Trees Efficient Immutable Vectors （上）

[funfish]

概论

不可变结构是一种很便利的函数式编程的数据结构，也是现代语言标准库如 Clojure 和 Scala 的一部分。其相同的部分是基于有固定数量的子节点的多阶树，允许快速查询和更新操作。在本文中我们采用了一种新的潜在的 vector 结构 Relaxed Radix Balanced Trees（RRB-Trees）。并展示了这种数据结构在 O(logN) 的时间里进行不可变数据 vector 的串联，插入和分割操作，同时维持着和原始 vector 数据结构的查询、更新和迭代接近的速度。

1 介绍

不可变数据结构可以便利地处理在多核并发的环境中存在的问题。不可变数据像 List 可以在函数式编程中很有作用，但是他们的顺序性使其不适用于并发处理。Guy Steele 在总结其 ICFP 09 的主题时用到的一句很出名的话 “去除弊端”。新的数据结构有有效的渐进行为和良好的常数因子，这种数据结构要能在并行处理时，分解输入的数据，同时可以有效的组合计算结果。

在可变数据里面，数组通常是以列表的形式的，这样访问元素的时间复杂度为常数，而不是线性，同时同一数组的不相交部分也可以并行处理。对常见的可变数据，构建一个高效的不可变数据模型，即一个可索引的有序序列，不是件容易的事。因为幼稚的创建不可变数据行为是在更新独立的元素时，时间复杂度采用不能接受的线性时间。不可变 vector 数据结构由编程语言 Clojure 首创，并在读写性能上有良好的平衡性，有效的支持多种常用的编程模式。在 Clojure，不可变结构有一个至关重要的语言实现设计，Ideal Hash Tries(HAMTs) 用在不可变结构的基本哈希字典上和同样结构的 32 分叉树上。这样设计的使得有效的迭代和单元素添加的时间复杂度都是常数级别，查询的时间复杂度在 log32 N = (1/5)lg N，更新的时间复杂度在(32/5)lg N。使用宽为 32 的数组作为树的节点可以使得数据结构的缓存更加友好。一个索引的更新只会在间接内存的访问里消耗 (1/5)lg N 时间，这意味着，为了实用的目的，程序员可以考虑将所有的操作都当作 “有效的常数时间”。

然而并行操作需要数据结构的高效的 vector 串联，给定序号分割和插入，而这种的结构并不能简单的实现。本文介绍的方式扩展了潜在的 vector 结构来支持 O(logN) 的串联和插入操作，而不是线性时间，同时不会影响现有业务。这种新的数据结构适用于常见理解类型的并行处理。一个 vector 进行拆分，可以认为是等效并行的。对于很多常见的操作例如 filter，拆分大小是能不预先知道。一个子 vector 可以串联并返回一个 vector，并且不是线性拷贝。这种方式下，并行处理在汇总的时候不会遗失数据。

尽管现在的研究是针对在编程语言 Scala 里的，但是该数据结构也适用于其他语言环境，例如 Clojure，C，C++等等。其他用例如：字符串的特别实现等也都促进基于模板的网页生成。

在本文的其他部分，我们会用术语 vector (结构容器) 来指代 Scala 和 Clojure 创建的 32分叉的数据结构。

1.1 相关内容

以前的研究已经阐述了，不可变数据结构对串联问题有所改进，特别是 Ropes、2-3 finger tree、平衡树等结构。然而每个都有限制的地方。Ropes，这个数据结构原本就是创建来支持字符串串联的，其实现方式是，简单的创建一个有两个子字符串的二叉树。通过向节点添加两个字符串的大小，在串联后可以有效的排序。至于分割，可以通过在 Rope 上创建一个分割的节点，并使用上下分割边界值就能实现。然而进行重复的串联和分割时候，性能会下降。索引的时间复杂度，变成 s + lg c，其中 c 是串联的数量，而 s 是沿着 Rope 树的路径的拆分数量。这里需要考虑平衡性，以免导致最坏的情况。如果不拷贝，分割也会导致内存泄漏，因为原始字符串的分割后排除的部分若不被引用，将不会被收集回收。

2-3 finger tree 的查询和更新的时间都是 lg N，同时添加到 vector 的操作保持在平均常数的时间内。串联也是在 lg N 的时间内完成。尽管挺吸引人的，但是使用这种数据结构对于 (1/5) lg N 查询的折中方法，理论中还是要慢5倍。在 Okasaki 的书中，数据结构的不同在于常数因子。

在本文中，我们介绍 Relaxed Radex Balanced Trees(RRB-Trees)，一种新的数据结构，扩展了 vector 结构，并保持了其基本特性，同时允许高效的串联，分割和插入操作。

1.2 Vectors

如图所示，我们用 4 分叉树来作为所有 m 阶树的替代。除了特别的说明外，这个方式都适用于所有 m 阶树结构，包括 32 阶--这个有趣的不可变结构。如图1 就是用这种替代的方式来说明基础的 vector 结构。我们可以想象一个 32 阶版本，只要通过将 4 阶替换为32阶。

在为 Clojure 开发不可变哈希字典时，开发组长 Rich Hickey 用了 Hash Array Mapped Tries(HAMT) 做底子。HAMT's 用 32 阶分支结构来实现一个可变的哈希字典。这个由 Clojure 首创的可变版本中，当项目被添加或移除字典的时候，树的路径才会被重写。同样的 32 阶分支结构被用来提供一个不可变数据的 vecter。在这里，对于项目来说 ‘key’ 是其在 vector 中的索引，而不仅仅是键名的哈希值。不可变性的实现是在修改和添加的时候拷贝或升级树的路径，这使得 32 阶分叉的查询时间复杂度是 (1/5) lgN。
选择 32 作为 m 阶分叉的 vector，是从结构的不同使用来权衡确定的。分叉因子的提高会提高查询和迭代的性能，同时趋向于降低更新和扩展的性能。当 m 变化的时候，原则上查询时间等比与 logm N，而更新用时等比喻 m logm N。而实际上，由于高速缓冲行的原因，在64-128位的现代处理器下，使得复制了该大小的小块非常便宜。

正如我们在图2 看到的， m = 32 是在查询和更新耗时中有良好的平衡，尤其是平时使用查询和迭代的次数要远多于更新。

选择 m 为 2 的乘方可以允许位操作，从而在索引中得到分支值序号，而不是昂贵的模运算。尽管这是在过去需要的考虑的重要问题，如今现代计算机使得其额外的有优势。

图 2 演示了使用 m 阶结构要比二叉树或 2-3 finger tree 要有优势。使用 32 阶的数据结构要是他们的 4 倍，而更新时间是相似的。这个原则上五倍的优势，被上层节点的缓存给稀释减少了。

1.3 串联

在图 3 中展示了两个 vector。一个幼稚的方式是将一个 vector 向左移动，然后将所有的右手边的 vector 的节点复制到被串联的 vector 上合适的位置，根据右手边的 vector 的大小，决定处理的线性时间长短。或者可以遍历右手边的 vector 并将其添加到左侧的 vector 中，这也是线性处理。在本文的剩余部分，我们将会提出 RRB-Trees 是如何有效的进行串联。

2. RRB-Trees

RRB-Trees 通过调整固定的分叉数 m 来扩展已有的结构。为了实现该方法，关键是要防止树退化到线性列表，同时要维持树高度为 lg N。

2.1 B-树

B-树维持每一级中的最大分叉数 Mm 和最小分叉数 Ml。相应的最大高度 Hm，和最小高度 Hl，可以通过给定的项数 N 来表示：

平衡性好的有一个高度比：Hr，并且这个值接近 1 的是玩美的平衡。

Ml 越是接近 Mm，则树的平衡性越好。对于B-树，如果 Ml 是 Mm 的一半，则：

当 Mm 变大的时候，B-树那就更平衡，这是总所周知的特性。

2.2 Relaxed Radix Search

在这个结构下，分叉数 m 一直是 32，同时树也完美的平衡。索引的时候可以直接使用基数查询的方式。当两个这样的树串联的时候要放宽约束来避免线性的复制。少于 m 的项或子树可能存储在同一个节点中。这也意味着我们不能再使用任何简单的基数查询了。

基数查询依赖于每个给定的层级的子树上希望的节点数是刚好 m 的 h-1 次方个。因此对于索引 i， 在该节点的子树中被找到的概率是 [i/(m 的 h-1 次方)]（ps：索引和节点都是基于 0 偏移）。如果节点少于希望的，我们需要用另外一个方式，我们称之为宽松的基数查询。

在B-树，通过在父节点中存储一定区间 key，使用线性或则二进制查询父节点来找到包含目标 key 的子节点。在 RRB-树，当叉数少于 m 的时候，使用相似的方法，然而存储在父节点的数组中的是索引的区间而不是 keys 的区间。

图 4 展示了RRB树的基本结构。树节点 A 包含了一个指向子树的数组， C, D, 和 E。该数组包含了这些子树的总的累计的子叶的数量。为了方便，我们将一个指向及该数组的相关区间称之为槽，例如，槽位 0 指向节点 C，该数组的区间说明了其包含了三个子树，这些子树同时也是子叶。

假设我们想要获取序号为 3 的节点，也就是节点 D 的第一个项。该序号被 4 整除，将会落在槽位 0。然而我们发现当查找的序号等于或大于该槽位的区间时，需要查找下一个槽位 1。索引少于槽位 1 的区间的话，可以在槽位 1 的子树 D 中继续查询。在这之前，我们需要用查询的序号减掉槽位 0 的 3 个序号，使得后续是从零开始的新索引查询。可以发现想要查询的索引在节点 D 的第 0 个位置。

通常的，如果 Ml 接近 m，父节点上的基数查询将会快速接近希望的槽位。例如，如果 Ml = m -1，树高为 2时，最差的情况下，只会有 (m-1)平方 个项。为了查询第 m 个槽位，希望在选中的槽位中找到相应的子树，然而有时候，下一个槽位也必须被检查到。

在查询的时候，必须要先检查子树的区间来确定进入哪个子树查询（没有必要回溯查询）。区间值是该槽位的子叶的实际项目数量。我们可能需要检查两个可能的区间值。而不是直接查询正确的路径。这个额外的检测在现代计算机中是很简便的。读取第一个值就会引起缓冲行的加载，接着相邻的几个值会和第一个同样速度的进入缓冲。进行一个短的线性查询有较小的开销。接着，如果考虑所有可能的序号，并且槽位上节点数量也是均匀 m 或者 m - 1，我们可以预计这次的基数查询的成功率是 3/4。

槽位的平均节点数是 (m - 1)/2。（接下来这段文字都看懂了，但是不知道什么意思。。就不翻译了。。。）。

2.3 缓存行意识和二进制查询

缓存行加载可以通过短暂的线性查询，对基数查询带来上面的益处。对于二进制查询，这个是很合适的，因为其在串联算法中需要较少的约束。然而，32 阶的二进制查询可能在缓存行加载的时候导致多个缓存丢失，并且不能简单的预取缓存。经测试表明，宽松的基数查询要比二进制或纯线性查询要块三倍。