logo标签列表

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

sqlalgorithmscalabilitynested-sets
9
我一直在思考修改的先序遍历树遍历算法，用于在平面表（如SQL）中存储树。
标准方法让我不喜欢其中一个特性：插入节点时，您必须平均触及N/2个节点（所有左侧或右侧高于插入点的内容）。
我看到的实现依赖于连续编号的值。这对于更新留下了没有余地。
这对并发和扩展来说似乎很糟糕。想象一下，您在存储整个世界的用户组的树，该用户组包含大型系统中每个帐户的用户组，它非常庞大，以至于您必须在不同的服务器上存储树的子集。接触一半的所有节点以将节点添加到树的底部是不好的。
这就是我正在考虑的想法。基本上，通过分区键空间并在每个级别上进行划分，为插入留出空间。
以下是一个示例，其中Nmax=64（通常为DB的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. 这是否与嵌套区间相同？
3个回答
5
我听说过人们为了同样的原因而这样做。
请注意，这样做会失去算法的一些小优势。
通常情况下，您可以通过 ((right - left + 1) div 2) 来告诉一个节点的后代数量。如果您在树形视图中显示计数，应包括树中更深处可以找到的子级的数量，这可能偶尔很有用。
由上述可知，很容易选择所有叶节点 -- WHERE (right = left + 1)。
这些都是相对较小的优点，对您可能没有用处，但对某些使用模式显然很方便。
话虽如此，像上面建议的那样，材料化路径似乎对您更有用。
2

我认为你最好考虑一种不同的树的存储方式。如果你的树是宽而不是深（这似乎适用于你提出的情况），你可以针对每个节点存储到根节点的完整祖先列表。这样，修改一个节点不需要触及除被修改的节点之外的任何节点。

1
FYI，这种方法被称为“材料化路径”。我认为这可能是目前最安全的方法。它当然更容易编写正确（不太复杂）。不过我还在继续研究 :-) - Mark Renouf
1
你可以将表格分成两个部分：第一个是（节点ID，节点值），第二个是（节点ID，子节点ID），它存储了树的所有边缘。插入和删除操作变成了O（树深度）（您必须导航到元素并修复其下面的内容）。
您提出的解决方案看起来像是B-tree。如果您能够估计树中节点的总数，则可以预先选择树的深度。
这是邻接表模型。问题在于读取整棵树需要O(树深度)的查询次数。嵌套集模型显著改进了这一点（只需一个查询）。 - Mark Renouf
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接