提高修改的预订树遍历算法的可扩展性

Question

我一直在考虑修改前序树遍历算法,用于在平面表(例如SQL)中存储树.

我不喜欢标准方法的一个属性是插入一个节点,你必须触摸(平均)N/2个节点(左边或右边高于插入点的所有东西).

我见过的实现依赖于顺序编号的值.这没有留下更新的余地.

这对于并发和扩展似乎很糟糕.想象一下,你有一棵植根于世界的树,它包含大型系统中每个帐户的用户组,它非常大,你必须将树的子集存储在不同的服务器上.触摸所有节点的一半以将节点添加到树的底部是不好的.

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

这是N _max = 64 的示例(这通常是数据库的MAX_INT)

                     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),然后使用node.id和node.parent来处理列表,细分索引.

这比仅增加所有索引以便为插入腾出空间(或递减删除)更复杂,但它有可能影响更少的节点(仅插入/删除节点的父节点的后果).

我的问题基本上是:

1. 这个想法是否已正式化或实施？

2. 这与嵌套间隔相同吗？

Answer 1

我之前听说有人这样做,出于同样的原因,是的.

请注意,通过执行此操作,您确实会失去算法的一些小优势

• 通常,您可以通过((右 - 左+ 1)div 2)来判断节点的后代数.这可能偶尔会有用,例如,您在树视图中显示一个计数,其中应包括要在树中找到的子项数
• 从上面开始,很容易选择所有叶节点 - WHERE(right = left + 1).

这些都是相当小的优点,无论如何可能对你没用,虽然对于一些使用模式,它们显然很方便.

也就是说,听起来像物化路径可能对您更有用,如上所述.

Answer 2

您可以将表分成两个：第一个是（节点ID，节点值），第二个是（节点ID，子ID），它存储树的所有边。然后插入和删除变成 O（树深度）（您必须导航到该元素并修复其下方的内容）。

您提出的解决方案看起来像B 树。如果您可以估计树中的节点总数，那么您可以预先选择树的深度。