相关疑难解决方法(0)

我一直在考虑修改前序树遍历算法,用于在平面表(例如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. 这与嵌套间隔相同吗？