代码之家  ›  专栏  ›  技术社区  ›  gregmac

查找嵌套集的面包屑

  •  4
  • gregmac  · 技术社区  · 15 年前

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

    例如:

    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))
    

    它会起作用的。


    我有一个现有的标量函数可以做到这一点,但它不能在任何合理数量的组上工作(2000个组需要10秒)。它以groupid和userid作为参数,并返回nvarchar。它查找给定的组父级(1个查询获取左/右值,另一个查询查找父级),将列表限制为用户有权访问的组(使用与上面相同的WHERE子句,另一个查询),然后使用光标遍历每个组并将其附加到字符串,最后返回该值。

    我需要一种快速运行的方法(例如<=1s)。

    这在SQL Server 2005上。

    6 回复  |  直到 15 年前
        1
  •  3
  •   Kathy Keating    13 年前

    这是SQL,它帮助我从树中的任何点获取“breadcrumb”路径。希望有帮助。

    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
    

    凯丝

        2
  •  3
  •   sorohan    10 年前

    好啊。这是针对MySQL的,而不是针对SQL Server 2005的。它将组concat与子查询一起使用。

    这应该将完整的breadcrumb作为单列返回。

    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
    
        3
  •  2
  •   rball    15 年前

    如果可以,请使用路径(或者我认为我听说过它被称为沿袭)字段,如下所示:

    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和向前(psuedocode):

    path = SELECT Path FROM Nodes WHERE ID = 3
    SELECT * FROM Nodes WHERE Path LIKE = path + '%'
    
        4
  •  1
  •   gregmac    15 年前

    我最后做的是创建一个大型的连接,它简单地将这个表与它本身联系起来,在每一个级别上一次又一次。

    首先,我用一级组填充一个表@toplevelgroups(如果您只有一个根,则可以跳过此步骤),然后用用户可以看到的组填充@user groups。

    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查询中获得它。


    我接受这一点作为答案,因为这是我最终要做的,而且可能对其他人有用——但是,如果有人能想出一个更有效的方法,我会把它改为其他人。

        5
  •  1
  •   Squall    10 年前

    我修改了凯西的陈述以获取每个元素的面包屑。

    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
    
        6
  •  0
  •   Evert    15 年前

    没有特定于SQL Server的代码,但您只是在寻找:

    从表中选择*左<(currentid.left)和右>(currentid.right)

    推荐文章