查找嵌套集的面包屑

Question

我正在使用嵌套集（又名经过修改的预排序树遍历）来存储组列表，并且我试图找到一种快速方式来一次为所有组生成面包屑（作为字符串，而不是表）。我的数据也使用邻接表模型存储（有一些触发器可以使两者保持同步）。

因此，例如：

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

我确实有一个用户定义的函数，该函数将一个userid作为参数，并返回一个表，其中包含所有有效组的ID，因此只要查询中的某个位置

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

它会工作。

我已有一个可以执行此操作的标量函数，但是它不适用于任何合理数量的组（在2000个组上需要>
10秒的时间）。它使用一个groupid和userid作为参数，并返回一个nvarchar。它找到给定的组父母（1个查询以获取左/右值，另一个查询以查找父母），将列表限制为用户有权访问的组（使用与上述相同的WHERE子句，因此使用另一个查询），然后使用游标遍历每个组并将其附加到字符串，最后返回该值。

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

这是在SQL Server 2005上。

Answer 1

我最终要做的是建立一个大型联接，该联接简单地将此表与其自身联系起来，遍及每个级别。

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

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查询中获得此功能。

我接受这作为答案，因为这是我最终要做的，并且可能对其他人有用-但是，如果有人可以提出一种更有效的方法，我将其更改为他们。