1

我在 Microsoft SQL Server (2019) 中使用邻接列表模型（例如 、 ）存储了一个大型层次结构（2,500 多条记录Id）ParentId。我正在寻找一种有效的方法来根据层次结构中的特定路径查找记录。换句话说，给定一个路径（例如/Root/FolderA/SubfolderA），我想检索Id与最终节点关联的（即，SubfolderA在这种情况下）。

注意：节点名称不是全局唯一的。即，我们不能只寻找SubfolderA并假设它映射到/Root/FolderA/SubfolderA. SubfolderA层次结构中可能有多个节点。

设置

等级制度

/Root
  /FolderA
    /SubfolderA
    /SubfolderB
  /FolderB
    /SubfolderA
    /SubfolderB

结构

CREATE 
TABLE   [dbo].[Tree] (
        [Id]            INT             NOT NULL PRIMARY KEY, 
        [ParentId]      INT             NULL, 
        [Name]          VARCHAR(255)    NOT NULL, 
        CONSTRAINT      [FK_Hierarchy]  
        FOREIGN KEY     (ParentId) 
        REFERENCES      [Tree]([Id])
)

数据

INSERT INTO Tree VALUES (1,    NULL, 'Root');
INSERT INTO Tree VALUES (2,    1,    'FolderA');
INSERT INTO Tree VALUES (3,    2,    'SubfolderA');
INSERT INTO Tree VALUES (4,    2,    'SubfolderB');
INSERT INTO Tree VALUES (5,    1,    'FolderB');
INSERT INTO Tree VALUES (6,    5,    'SubfolderA');
INSERT INTO Tree VALUES (7,    5,    'SubfolderB');

天真的方法

关于如何将邻接列表转换为物化路径有很多线程，包括：

看法

我们可以使用其中一种方法来使用 rCTE将整个邻接列表转换为物化路径：

CREATE 
VIEW            [dbo].[MaterializedPaths]
WITH            SCHEMABINDING
AS 

WITH RCTE AS (

  SELECT        Id,
                ParentId,
                CAST('/' + Name AS VARCHAR(255)) AS Path
  FROM          [dbo].[Tree] root
  WHERE         root.Id = 1

  UNION ALL

  SELECT        this.Id,
                this.ParentId,
                CAST(parent.Path + '/' + this.Name AS VARCHAR(255)) AS Path
  FROM          [dbo].[Tree] AS this
  INNER JOIN    RCTE parent
    ON          this.ParentId = parent.Id
)
SELECT          Id,
                Path
FROM            RCTE as hierarchy

输出

这会产生以下输出：

Id    Path
1     /Root
2     /Root/FolderA
3     /Root/FolderA/SubfolderA
4     /Root/FolderA/SubfolderB
5     /Root/FolderB
6     /Root/FolderB/SubfolderA
7     /Root/FolderB/SubfolderB

询问

我们可以使用一个简单的WHERE子句过滤该输出：

SELECT          Id
FROM            MaterializedPaths
WHERE           Path = '/Root/FolderA/SubfolderA'

问题

天真的方法效果很好。问题是查询大型层次结构的效率非常低，因此速度很慢，因为它需要在每次调用时动态重建整个物化路径集。就我而言，这需要 8-9 秒。显然，我可以将这些数据存储在一个表中，并在数据更改的任何时候通过触发器重新生成它。但我宁愿找到更有效的查询并避免额外的复杂性。

问题

构建此查询的有效方法是什么？或者，冒着使这成为 XY 问题的风险，有没有办法限制 rCTE，使其只需要评估层次结构中的节点，而不是每次都重建整个层次结构？

4

1 回答 1

2

有没有办法限制 rCTE，使其只需要评估层次结构中的节点，而不是每次都重建整个层次结构？

限制 rCTE

有几种方法可以限制每个递归查询的范围，以便它只评估层次结构中的相关节点。一种相当有效的方法是简单地将 rCTE 限制为源路径（我们称之为@Path）以以下开头的记录：

INNER JOIN  RCTE recursive
  ON        this.ParentId = recursive.Id
  AND       @Path LIKE CAST(recursive.Path + '/' + this.Name AS VARCHAR(MAX)) + '%'

这会将查询限制为路径中的每条记录：

Id    Path
1     /Root
2     /Root/FolderA
3     /Root/FolderA/SubfolderA

然后可以根据一个简单的WHERE子句轻松过滤到最终记录：

WHERE Path = @Path

将其打包为函数

我们可以将它与原始 rCTE 组合成一个函数。把它们放在一起，它可能看起来像：

CREATE
FUNCTION        [dbo].[GetIdFromPath]
(
    @Path       VARCHAR(MAX)
)
RETURNS         INT
AS

BEGIN

  DECLARE       @Id         INT = -1


  ;WITH RCTE AS (

    SELECT      Id,
                ParentId,
                CAST('/' + Name AS VARCHAR(MAX)) AS Path
    FROM        [dbo].[Tree] root
    WHERE       root.Id = 1

    UNION ALL

    SELECT      this.Id,
                this.ParentId,
                CAST(parent.Path + '/' + this.Name AS VARCHAR(MAX)) AS Path
    FROM        [dbo].[Tree] AS this
    INNER JOIN  RCTE parent
      ON        Tree.ParentId = parent.Id
      AND       @Path LIKE CAST(parent.Path + '/' + this.Name AS VARCHAR(MAX)) + '%'
  )
  SELECT        @Id = Id
  FROM          RCTE as hierarchy
  WHERE         Path = @Path

  RETURN        @Id

END

按路径查询

给定上述函数，您现在可以通过简单地将完整路径传递给GetIdFromPath()函数来查询邻接列表：

SELECT          dbo.GetIdFromPath('/Root/FolderA/SubfolderA') AS Id

鉴于原始帖子中的示例数据，它将返回3.

表现

我已经针对具有 2,500 条样本记录的具有可比大小的表测试了这种方法，并且它始终在不到一秒的时间内执行，这是对幼稚方法的显着改进。显然，您需要根据您自己的数据库和性能要求来评估它，以确定它是否足够高效。

于 2020-09-01T23:21:16.973 回答