sql - 提高改进的前序树遍历算法的可扩展性

Question

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

我不喜欢标准方法的一个特性是插入一个节点必须接触(平均)N/2 个节点(所有左侧或右侧高于插入点的节点)。

我见过的实现依赖于按顺序编号的值。这没有留下更新的空间。

这似乎不利于并发性和扩展性。想象一下，您有一棵 Root 于世界的树，其中包含大型系统中每个帐户的用户组，它非常大，以至于您必须将树的子集存储在不同的服务器上。触摸所有节点的一半以将节点添加到树的底部是不好的。

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

这是一个 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

插入和删除过程必须扩展算法以递归地重新编号到子树的左/右索引。由于查询节点的直接子节点很复杂，我认为将父节点 ID 也存储在表中是有意义的。该算法然后可以选择子树(使用 left > p.left && right < p.right)，然后使用 node.id 和 node.parent 遍历列表，分割索引。

这比仅递增所有索引以为插入腾出空间(或递减以移除)更复杂，但它有可能影响更少的节点(仅插入/移除节点的父节点的后代)。

我的问题基本上是:

1. 这个想法是否正式化或实现了？

2. 这和嵌套区间一样吗？

Answer 1

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

请注意，这样做确实会失去算法的几个小优势

• 通常，您可以通过 ((right - left + 1) div 2) 来判断一个节点的后代数。这偶尔会有用，例如你会在 TreeView 中显示一个计数，其中应该包括在树的更下方找到的 child 的数量
• 综上所述，很容易选出所有叶节点——WHERE(right = left + 1)。

这些都是相当小的优势，可能对您没有用，但对于某些使用模式来说，它们显然很方便。

也就是说，正如上面所建议的那样，物化路径听起来确实对您更有用。