在拆分层次结构中查找丢失的文件夹路径

Question

我有一个包含文件夹路径的表。该表包含四列：

• DirID - 文件夹的 ID。
• BaseDirID- 层次结构中第一个文件夹的 ID。因此，来自同一层次结构的所有文件夹（路径）在此列中共享相同的值。
• DirLevel - 文件夹的深度。
• DisplayPath - 文件夹的路径。

我需要找到层次结构中这些文件夹之间的所有“差距”。

示例数据例如：

DirID BaseDirID DirLevel DisplayPath
1         1        1     'A'
2         1        3     'A\B\C'
3         1        5     'A\B\C\D\E'
4         1        3     'A\B\F'
5         1        5     'A\B\F\G\H'
6         2        1     'U'
7         2        3     'U\V\W'
8         2        5     'U\V\W\X\Y'
9         2        3     'U\V\M'
10        2        5     'U\V\M\L\O'

所以我们需要找到以下数据：

BaseDirID   DisplayPath
1           'A\B'
1           'A\B\C\D'
1           'A\B\F\G'
2           'U\V'
2           'U\V\W\X'
2           'U\V\M\L'

注释：

1. 该表包含超过250,000条文件夹的记录，因此我们寻求最有效的方法来执行此操作，否则脚本将卡住很长时间，我们没有时间。
2. 我没有所有文件夹的列表。我拥有的是“根”文件夹和“叶”文件夹，我需要在层次结构中找到它们之间的“间隙”。
3. 该表可以包含多个层次结构，我们需要找到所有层次结构中的“差距”。
4. 每个层次结构都可以拆分，正如您在示例数据中看到的，第一个层次结构从“A\B”文件夹拆分为两个文件夹路径：“A\B\C”和“A\B\F”。第二层级从“U\V”文件夹拆分为两个文件夹路径：“U\V\W”和“U\V\M”。即使在层次结构分裂的情况下，我们也需要找到所有的“差距”。
5. 我们可以对表进行任何更改 - 添加 pk、索引等...
6. SQL Server 版本是 2012 SP3。
7. 真正的文件夹名称可以是任何名称 - 一个或多个。
8. 结果必须只包含“差距”。
9. 所有丢失的中间文件夹都是必需的。

此 dbfiddle 中的扩展示例数据和预期结果。

这个问题是 Stack Overflow 问题Find missing hierarchy Folders (Paths) in a table的延续。我们的问题还包括以粗体显示的第 4 条评论。

我看到有一种叫做（从 SQL Server 2008 开始）的新类型hierarchyid，我认为它可能对我们有帮助。你怎么认为？

Answer 1

我会尝试这样的事情：

• 首先，创建一个新表并将现有数据复制到那里。
• 然后迭代，在每次迭代中，删除每个文件路径的最后一个节点（例如：'A\B\C\D\E'变成'A\B\C\D'）并在表中添加这些新文件路径，如果它们还没有的话。
• 当迭代不产生新行时停止。

初始化：

-- step 0
CREATE TABLE filepaths
  ( BaseDirID int NOT NULL,
    DirLevel int NOT NULL,
    DisplayPath varchar(1000) NOT NULL,   -- adjust the size according to your data,
    ReverseDisplayPath varchar(1000) NOT NULL,
    Iteration int NOT NULL,
    PRIMARY KEY (Iteration, ReverseDisplayPath),
    UNIQUE (ReverseDisplayPath)
  ) ;

INSERT INTO filepaths
  ( BaseDirID, DirLevel, DisplayPath, ReverseDisplayPath, Iteration )
SELECT
    BaseDirID, DirLevel, DisplayPath, reverse(DisplayPath), 0
FROM 
    existing_table ;

和迭代：

DECLARE @new_items bigint ;
DECLARE @iter int ;
SET @iter = 0 ;

-- repeat
repeat:     
    INSERT INTO filepaths
        (BaseDirID, DirLevel, DisplayPath, ReverseDisplayPath, Iteration)
    SELECT DISTINCT
        f.BaseDirID, f.DirLevel - 1, reverse(r.rdp), r.rdp, @iter + 1
    FROM 
        filepaths AS f
      CROSS APPLY
        ( SELECT substring(f.ReverseDisplayPath, 
                           1 + charindex('\', f.ReverseDisplayPath), 
                           1000) AS rdp
        ) AS r
    WHERE 
          f.Iteration = @iter
      AND f.DirLevel > 1 
      AND NOT EXISTS
          ( SELECT *
            FROM filepaths AS ex
            WHERE ex.ReverseDisplayPath = r.rdp
          ) ;
    SET @new_items = @@ROWCOUNT ;

    SET @iter = @iter + 1 ;
    -- until new_items = 0
    IF (@new_items > 0) GOTO repeat; 

该过程完成后，您可以通过简单的查询仅获取丢失的文件路径：

SELECT DisplayPath FROM filepaths 
WHERE Iteration > 0 
ORDER BY DisplayPath ;

在dbfiddle.uk 中测试。

反向字符串不是严格需要的，但它们简化了字符串的拆分。你可以不用它们（以及更复杂的代码）。您也可以只将反向路径存储在新的filepaths表中，当迭代完成时，将它们再次反向到目标表（我猜是现有的表或您希望它们去的任何地方）。

整个事情也可以通过一次完成 - 使用递归 CTE - 但我不知道这是否会或多或少有效。