代码之家 › 专栏 › 技术社区 › itsadok

改进的前序树遍历算法的可扩展性改进

nested-sets scalability algorithm sql

itsadok · 技术社区 · 17 年前

我一直在想 modified preorder tree traversal 在平面表(如SQL)中存储树的算法。

必须接触(平均)N/2的节点(左或右高于插入点的所有节点)。

我看到的实现依赖于顺序编号的值。这就没有更新的余地了。

这似乎不利于并发性和伸缩性。假设你有一棵树根在世界上,包含了一个大型系统中每个帐户的用户组,它非常大,以至于你必须将树的子集存储在不同的服务器上。触摸所有节点的一半以将节点添加到树的底部是不好的。

这是我正在考虑的想法。基本上通过划分键空间并在每个级别上划分来为插入留出空间。

_最大值

                     0:64
              ________|________
             /                 \
         1:31                   32:63
        /    \                 /     \
    2:14    15-30         33:47       48:62

在这里,一个节点被添加到树的左半部分。

                     0:64  
              ________|________
             /                 \
         1:31                  32:63
      /   |   \               /     \
  2:11  11:20  21:30     33:47       48:62

必须扩展alogorithm,以便插入和删除过程递归地对子树的左/右索引重新编号。由于查询节点的直接子节点很复杂,我认为在表中也存储父id是有意义的。然后,算法可以选择子树(使用left>p.left&right<p.right),然后使用节点.id以及节点.父级对列表进行处理,对索引进行细分。

这个想法是否已经正式化或实施?
这和嵌套间隔一样吗?

3 回复 | 直到 15 年前

Cowan 17 年前

我以前听说过有人这样做,出于同样的原因,是的。

注意,这样做确实会失去算法的一些小优点

通常,您可以通过((right-left+1)div 2)来判断一个节点的后代数。如果你想在树状视图中显示一个计数,这个计数应该包括在树的下一级可以找到的子级的数量,这有时是有用的
从上面可以看出,很容易选择出所有叶节点——其中(right=left+1)。

也就是说,像上面提到的,物化路径听起来对你可能更有用。

Nick Johnson 17 年前

我觉得你最好换个方法来储存树木。如果您的树很宽,但不是很深(对于您所建议的情况,这似乎很有可能),您可以针对每个节点存储祖先的完整列表,直到根。这样,修改节点不需要接触除被修改节点之外的任何节点。

Dmitry Risenberg 17 年前

你提出的解决方案看起来像 B-tree . 如果可以估计树中节点的总数,则可以事先选择树的深度。