搜索具体化路径树的最右侧节点

Question

是否可以按物化路径树的 path 文本字段排序，以便找到树的最右侧节点？例如，考虑这个使用 django-treebeard 的 MP_Node:

的 python 函数

def get_rightmost_node():
    """Returns the rightmost node in the current tree.

    :rtype: MyNode
    """
    # MyNode is a subclass of django-treebeard's MP_Node.
    return MyNode.objects.order_by('-path').first()

从我所有的测试来看，它似乎 return 我所期望的，但我不知道如何用数学来证明它。而且我还没有找到任何关于在物化路径树上执行此操作的信息。

Treebeard 的实现在路径中没有分隔符，所以路径看起来像这样：0001、00010001、000100010012 等

Answer 1

简答：否

Here is a SQLFiddle 展示了我在评论中描述的问题。

对于这个简单的设置：

id, path
1,  '1'
2,  '1'
3,  '1'
4,  '1'
5,  '1'
6,  '1'
7,  '1'
8,  '1'
9,  '1'
10, '1'

尝试通过简单排序获取最右边的叶子 (id = 10) 将失败:

SELECT TOP 1
  id,
  path
FROM hierarchy
ORDER BY path DESC

returns:

id, path
9,  1

因为 path 是 text-based 列，所以 1 将在之后 1 降序排列（参见fiddle).

中第二个查询的结果

即使您开始跟踪深度和路径长度（通常价格低廉且易于跟上），也完全有可能获得如下路径：

path       depth  length
12  4      9
5  4      9

仍然无法正确排序。

即使您使用字母而不是数字，这也只会将问题范围推到第 26 个 child 而不是第 10 个：

SQLFiddle using letters

我对物化路径操作不像对嵌套集和邻接列表那样熟悉，也没有使用 django 的经验，所以如果有我不知道的方法，我会尊重其他人，但你几乎肯定必须对 path 列执行某种解析才能始终如一地获得正确的叶子。

编辑 - 解决了排序是否是有效解决方案的问题后，经过一些讨论和对问题的思考，这里有一些关于其他潜在解决方案的附加说明：

-"Rightmost" 是一个模糊的术语，当节点可以有两个以上的 children 时（即树不是二叉树）。如果一个节点有10个children，哪些在parent的左边，哪些在右边？您必须先定义此条件，然后才能定义问题的解决方案。

-一旦 "rightmost" 为您的问题 space 正确定义，请了解最右边的节点不一定位于树的最低级别：

        1
       / \
    1   1 <= This is the rightmost node
    /
  1 <= This is the lowest node

-一旦定义了"rightmost"，就可以使用一个简单的循环以编程方式找到最右边的节点：

//in pseudocode
function GetRightmostNode(Node startNode)
{
  Node currentNode = startNode;

  while(currentNode.RightChildren != null)
  {
    currentNode = maximum of currentNode.RightChildren;
  }

  return currentNode;
}

这个循环会在当前节点的右边寻找当前节点的children。如果它们存在，它会选择最右边的 children 并重复。一旦到达右侧没有 children 的节点，它就会成为当前节点 returns，因为它找到了以 startNode 为根的树（或子树）最右边的节点.

Answer 2

你可以使用@Paul 解释的方法 modifications.You 可以在每个数字前面附加 0 并且每个路径的长度可以统一。

节点可以指定路径为，

id |  path
-----------------
1  |  '01'
2  |  '01'
3  |  '01'
4  |  '01'
5  |  '01'
6  |  '01'
7  |  '01'
8  |  '01'
9  |  '01'
10 |  '01'
11 |  '01'
12 |  '01'

如果最大子节点数的节点的子节点数小于100，则可以使用上面的例子。

如果它在 100 到 1000 之间，那么您可以明智地添加一个额外的 0 作为 001[=14=]3[=14=]2[=14=]5。

然后就可以得到最右边的节点12 as,

SELECT TOP 1 id
FROM tree
ORDER BY path DESC

您可以在此处找到演示。 Demo

Answer 3

编辑：Paul Griffin 正确地指出我的回答是不可靠的，因为它假定节点将低于某个值。这是一个更好的尝试，在 Denis de Bernardy 的深度函数上结合了两个自旋。

使用两种排序标准，一种用于深度，另一种用于最左边节点转换为整数的值：

SELECT path, 
       length(regexp_replace(path, '[^/]+', '', 'g')) as depth,
       regexp_replace(path, '^.*/', '')::int as last       
FROM test 
ORDER BY depth DESC, last DESC;

这会将具有最高值的最深节点放在顶部。

SQLFiddle

Answer 4

Is it possible to sort by a materialized path tree's path text field in order to find the right-most node of the tree?

没有。例如，如果节点路径存储为 '/1/3/6/2'，请考虑：

/1
/1/3
/1/3/6/2
/1/3/6/5
/1/3/6/21
/1/40

请参阅 Paul 的回答，了解无法对上述内容进行排序的原因。

尽管如此，所有的希望都没有消失。如果您正在搜索 "the right-most node"，我假设您指的是树中最深的节点，您可以简单地计算分隔符。例如：

select length(regexp_replace('/1/3/6/2', '[^/]+', '', 'g')) as depth;

如果您正在寻找最大值，请使用类似的东西：

order by length(regexp_replace(path, '[^/]+', '', 'g')) desc

... 或等效的 python 代码。索引选项包括索引相同的表达式，或将结果存储在单独的深度字段中并对其进行索引。

如果您仍然对 ID 的实际值感兴趣，上面的数字通常与 ID 相对应，因此请使用该列进一步排序。如果它们不同，则使用不同的正则表达式提取最右边的数字，并将其转换为整数，以便自然地对它们进行排序 (1, 11, 2) 而不是按字典顺序 (1, 11, 2):

select regexp_replace('/1/3/6/2', '^.+/', '')::int as value;

搜索具体化路径树的最右侧节点

Searching for the right-most node of a materialized path tree

sql

postgresql

tree

materialized-path-pattern

django-treebeard