在拆分層次結構中查找失去的文件夾路徑

我有一個包含文件夾路徑的表。該表包含四列：

• 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的延續。我們的問題還包括以粗體顯示的第四條評論。

我看到有一種新類型叫做hierarchyid（從 SQL Server 2008 開始），我認為它可能對我們有所幫助。你怎麼看？

我會嘗試這樣的事情：

• 首先，創建一個新表並將現有數據複製到那裡。
• 然後迭代，並在每次迭代中，刪除每個文件路徑的最後一個節點（例如：'A\B\C\D\E'become '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 - 但我不知道這是否會或多或少有效。

引用自：https://dba.stackexchange.com/questions/173787