松弛基数平衡树(RRB-trees) 是不可变向量的泛化（用于 Clojure 和 Scala），具有“有效恒定”的索引和更新时间。RRB 树保持高效的索引和更新，但也允许高效的连接（log n）。
作者以我难以理解的方式呈现数据结构。我不太确定每个节点维护的不变量是什么。
在 2.5 节中，他们描述了他们的算法。我认为他们确保索引到节点只需要在基数搜索之后进行额外的线性搜索步骤。我不明白他们是如何得出额外步骤的公式的，我想也许我不确定每个变量的含义（特别是“总共 p 个子树分支”）。
RRB-tree 连接算法是如何工作的？
他们确实在第 2.4 节中描述了一个不变量“但是，如前所述，B-Trees 节点不便于基数搜索。相反，我们选择了允许节点大小介于m
和之间的初始不变量m - 1。这定义了一个平衡树族已知 2-3 棵树、3-4 棵树和（对于 m=32）31-32 棵树。这个不变量保证了平衡并在大多数情况下实现了基数分支搜索。偶尔在基数搜索之后需要进行几步线性搜索以找到正确的分支。更高级别所需的额外步骤会增加。
查看他们的公式，看起来他们已经计算出存储在子树中的最大和最小可能值数量。两者之间的差异是一个点下的最大和最小值之间的最大可能差异。如果将其除以插槽下的值的数量，则当您计算出要查看的插槽以查看它是否包含您正在搜索的索引时，您将获得最大的插槽数。
@mcdowella 是正确的，这就是他们所说的放松节点。但是，如果您要拆分和连接节点，从m到m -1 的范围意味着您有时必须调整最多m -1 ( m -2?) 个节点才能从节点中添加或删除单个元素。这似乎非常低效。我认为它们的意思是在m和 (2 m ) - 1 之间，因为这允许节点在它们变得太大时分成 2 个，或者当它们太小时将 2 个节点合并为一个，而无需更改第三个节点。因此，论文中的“2 m ”中缺少“2”是一个错字。 Jean Niklas L'orange 的硕士论文支持我的观点。
此外，所有严格节点的长度都相同，必须是 2 的幂。原因是 Rich Hickey 的 Clojure PersistentVector 中的优化。好吧，我认为重要的是打包剩下的所有严格节点（稍后会详细介绍），这样您就不必猜测要下降树的哪个分支。但是能够移位和位掩码而不是除法是一个很好的奖励。我没有在宽松的 Scala 向量上计时 get() 操作，但宽松的 Paguro 向量比严格的向量慢 10 倍。因此，它尽一切努力尽可能严格，如果您在 0 处重复插入，甚至会产生 2 个严格级别。
他们的树也有一个均匀的高度——所有的叶子节点到根的距离都是相等的。我认为如果放松的树必须在一个层次之内，它仍然可以工作，比如说，一个另一个层次，虽然不确定那会给你带来什么。
松弛节点可以有严格的子节点，反之则不行。
严格节点必须从左侧（低索引）无间隙地填充。任何非完整的 Strict 节点必须位于树的右侧（高索引）边缘。如果您确实附加到焦点或尾部（更多内容见下文），则所有严格叶节点总是可以满的。
您可以通过搜索Paguro 实现中的 debugValidate() 方法来查看大部分不变量。那不是他们的论文，但主要是基于它。实际上，论文中也没有提到Scala 实现中的“显示”变量。如果你要研究这些东西，你可能想先看看 Clojure PersistentVector因为 RRB 树里面有一个。它与 RRB Tree 的两个区别是：1. RRB Tree 允许“松弛”节点；2. RRB Tree 可能有“焦点”而不是“尾巴”。焦点和尾部都是小缓冲区（可能与严格的叶节点大小相同），不同之处在于焦点可能会定位到向量的最后插入/附加到的任何区域，而尾部始终位于末尾（PerSitentVector 只能追加，不能插入）。这两个区别是允许 O(log n) 任意插入和删除，加上 O(log n) split() 和 join() 操作。