查找嵌套集的面包屑

Question

我使用嵌套集（aka修改的预定义树遍历）来存储组的列表，我试图找到一种快速方法来生成面包屑（作为字符串，而不是表）为所有的群体一次。我的数据也使用邻接列表模型进行存储（有触发器使两者保持同步）。

因此，例如：

ID Name ParentId Left Right 
0 Node A 0   1  12 
1 Node B 0   2  5 
2 Node C 1   3  4 
3 Node D 0   6  11 
4 Node E 3   7  8 
5 Node F 4   9  9 

其表示树：

• 节点A
  • 节点B
    • 节点C
  • 节点d
    • 节点E
    • 节点F

我想能够有一个返回表中的用户定义的函数：

ID Breadcrumb 
0 Node A 
1 Node A > Node B 
2 Node A > Node B > Node C 
3 Node A > Node D 
4 Node A > Node D > Node E 
5 Node A > Node D > Node F 

---

为了使这个稍微复杂一些（尽管它有点超出了问题的范围），但我也有需要遵守的用户限制。因此，举例来说，如果我只访问ID = 3，当我运行查询，我应该得到：

ID Breadcrumb 
3 Node D 
4 Node D > Node E 
5 Node D > Node F 

我有一个用户定义的函数，它接受一个用户ID作为参数，并返回一个表与所有有效的组的ID，所以只要在查询的某个地方

WHERE group.id IN (SELECT id FROM dbo.getUserGroups(@userid)) 

它会工作。

---

我有一个现有的标量函数可以做到这一点，但它只是没有在组（需要>经10秒钟2000组）的任何合理数量的工作。它将一个groupid和userid作为参数，并返回一个nvarchar。它查找给定的组父母（1个查询获取左/右值，另一个查找父母），将列表限制为用户有权访问的组（使用与上述相同的WHERE子句，以及另一个查询），然后使用游标遍历每个组并将其附加到一个字符串，然后才能最终返回该值。

我需要一种快速运行的方法（例如，< = 1s）。

这是在SQL Server 2005上。

Answer 1

我最终什么事做的是做一个大的联合，简单地捆绑此表本身，一遍又一遍，每级。

首先，我只填写第一级组（如果您只有一个根，您可以跳过此步骤），然后@userGroups与用户可以看到的组一起填充@topLevelGroups表。

SELECT groupid, 
    (level1 
    + CASE WHEN level2 IS NOT NULL THEN ' > ' + level2 ELSE '' END 
    + CASE WHEN level3 IS NOT NULL THEN ' > ' + level3 ELSE '' END 
    )as [breadcrumb] 
FROM (
    SELECT g3.* 
    ,g1.name as level1 
    ,g2.name as level2 
    ,g3.name as level3 
    FROM @topLevelGroups g1 
    INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid 
    INNER JOIN @userGroups g3 ON g3.parentid = g2.groupid 

    UNION 

    SELECT g2.* 
    ,g1.name as level1 
    ,g2.name as level2 
    ,NULL as level3 
    FROM @topLevelGroups g1 
    INNER JOIN @userGroups g2 ON g2.parentid = g1.groupid and g2.groupid <> g1.groupid 

    UNION 

    SELECT g1.* 
    ,g1.name as level1 
    ,NULL as level2 
    ,NULL as level3 
    FROM @topLevelGroups g1 

) a 
ORDER BY [breadcrumb] 

这是一个相当大的黑客，并明显限制在一定的数量级的（我的应用程序，有一个合理的限度我可以选择），这个问题，更多的层面得到支持，它以指数形式增加联接的数量，因此速度要慢得多。

在代码中做它最当然更容易，但对我来说简直是并不总是一个选择 - 有些时候我需要这个，请直接从一个SQL查询。

---

我接受这个作为回答，因为这是我落得这样做，它可能适用于其他人 - 但是，如果有人能拿出一个更有效的方法我就改成他们。

Answer 2

如果可以，使用路径（或我想我已经听说过它称为谱系）领域，如：

ID Name ParentId Left Right Path 
0 Node A 0   1  12  0, 
1 Node B 0   2  5  0,1, 
2 Node C 1   3  4  0,1,2, 
3 Node D 0   6  11  0,3, 
4 Node E 3   7  8  0,3,4, 
5 Node F 4   9  9  0,3,4, 

得到公正节点d及以后的（伪代码）：

path = SELECT Path FROM Nodes WHERE ID = 3 
SELECT * FROM Nodes WHERE Path LIKE = path + '%' 

Answer 3

没有SQL服务器的特定代码，但你只是在寻找：

SELECT * FROM表WHERE左<（currentid.left）和右>（currentid.right）

Answer 4

这里是为我工作，从树中的任何一点得到了“面包屑”路径的SQL。希望能帮助到你。

SELECT ancestor.id, ancestor.title, ancestor.alias 
FROM `categories` child, `categories` ancestor 
WHERE child.lft >= ancestor.lft AND child.lft <= ancestor.rgt 
AND child.id = MY_CURRENT_ID 
ORDER BY ancestor.lft 

凯丝

Answer 5

确定。这是针对MySQL的，而不是SQL Server 2005.它使用了GROUP_CONCAT和子查询。

这应该返回完整的面包屑单列。

SELECT 
(SELECT GROUP_CONCAT(parent.name SEPARATOR ' > ') 
FROM category parent 
WHERE node.Left >= parent.Left 
AND node.Right <= parent.Right 
ORDER BY Left 
) as breadcrumb 
FROM category node 
ORDER BY Left 

Answer 6

我修改凯西的陈述得到面包屑的每一个元素

SELECT 
    GROUP_CONCAT(
     ancestor.name 
     ORDER BY ancestor.lft ASC 
     SEPARATOR ' > ' 
    ), 
    child.* 
FROM `categories` child 
JOIN `categories` ancestor 
ON child.lft >= ancestor.lft 
AND child.lft <= ancestor.rgt 
GROUP BY child.lft 
ORDER BY child.lft 

随意例如增加一个WHERE条件

WHERE ancestor.lft BETWEEN 6 AND 11