查找嵌套集的面包屑 [英] Finding breadcrumbs for nested sets

问题描述

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

I'm using nested sets (aka modified preorder tree traversal) to store a list of groups, and I'm trying to find a quick way to generate breadcrumbs (as a string, not a table) for ALL of the groups at once. My data is also stored using the adjacency list model (there are triggers to keep the two in sync).

因此，例如：

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
    
    
    
    
    • 节点E
    
    
    • 节点F
    
    

    我希望能够有一个用户定义的函数来返回表：

    I would like to be able to have a user-defined function that returns a table:

    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，则在运行查询时，我应该得到：

    ---

    To make this slightly more complicated (though it's sort of out of the scope of the question), I also have user restrictions that need to be respected. So for example, if I only have access to id=3, when I run the query I should get:

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

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

    I do have a user-defined function that takes a userid as a parameter, and returns a table with the ids of all groups that are valid, so as long as somewhere in the query

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

    它将起作用。

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

    I have an existing scalar function that can do this, but it just does not work on any reasonable number of groups (takes >10 seconds on 2000 groups). It takes a groupid and userid as a parameter, and returns a nvarchar. It finds the given groups parents (1 query to grab the left/right values, another to find the parents), restricts the list to the groups the user has access to (using the same WHERE clause as above, so yet another query), and then uses a cursor to go through each group and append it to a string, before finally returning that value.

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

    I need a method to do this that will run quickly (eg. <= 1s), on the fly.

    这是在SQL Server 2005上。

    This is on SQL Server 2005.

    推荐答案

    我结束了什么

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

    First I populate a table @topLevelGroups with just the 1st level groups (if you only have one root you can skip this step), and then @userGroups with the groups that user can see.

    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]
    

    这是一个非常大的技巧，并且显然仅限于一定数量的级别（对于我的应用程序，我可以选择一个合理的限制），问题是支持的级别越多，它就会增加联接的数量成指数增长，因此速度要慢得多。

    This is a pretty big hack, and is obviously limited to a certain number of levels (for my app, there is a reasonable limit I can pick), with the problem that the more levels are supported, it increases the number of joins exponentially, and thus is much slower.

    用代码做起来肯定更容易，但是对我来说，这并不是总是一个选择-有时我需要直接从SQL查询中获得它。

    Doing it in code is most certainly easier, but for me that is simply not always an option - there are times when I need this available directly from a SQL query.

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

    I'm accepting this as the answer, since it's what I ended up doing and it may work for other people -- however, if someone can come up with a more efficient method I'll change it to them.

    这篇关于查找嵌套集的面包屑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！