Relaxed Radix Balanced Trees(RRB树)是不可变 vector (在Clojure和Scala中使用)的推广，具有“有效恒定”的索引编制和更新时间。 RRB树保持有效的索引编制和更新，但也允许有效的串联(日志n)。
作者以难以发现的方式介绍了数据结构。我不太确定每个节点所维护的不变性。
在2.5节中，他们描述了他们的算法。我认为他们正在确保索引到节点将只需要在基数搜索之后执行线性搜索的额外步骤。我不明白他们是如何得出额外步骤的公式的，并且我想也许我不确定每个变量的含义(尤其是“总共p个子树分支”)。
RRB树串联算法的工作原理是什么？
最佳答案
它们确实在第2.4节“但是，如前所述
B树节点不便于基数搜索。相反，我们选择了
允许节点大小介于m之间的初始不变量
和m - 1。这定义了一个以
众所周知的2-3棵树，3-4棵树和(对于m = 32)31-32棵树。这个
不变式可确保平衡，并在
大多数情况下。有时需要几步线性搜索
在基数搜索之后找到正确的分支。
更高级别需要增加额外的步骤。”
查看他们的公式，看来他们已经计算出存储在子树中的最大和最小数量的值。两者之间的差异是一个点下面的最大和最小数量的值之间的最大可能差异。如果将其除以插槽下面的值数，则可以算出要查看哪个插槽以查看其中是否包含要搜索的索引，从而可以使用的最大插槽数为零。
关于algorithm - RRB树保持什么不变性？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14007153/