De oplossing die ik hier voorstel, maakt gebruik van het concept van een gematerialiseerd pad. Het volgende is een voorbeeld van gerealiseerde paden met behulp van uw voorbeeldgegevens. Ik hoop dat het je helpt om het concept van het gematerialiseerde pad te begrijpen:
+----+--------------------------+----------+------------------+
| ID | Name | ParentID | MaterializedPath |
+----+--------------------------+----------+------------------+
| 1 | Parent 1 | 0 | 1 |
| 2 | Parent 2 | 0 | 2 |
| 4 | Parent 2 Child 1 | 2 | 2.4 |
| 6 | Parent 2 Child 1 Child 1 | 4 | 2.4.6 |
| 7 | Parent 2 Child 1 Child 2 | 4 | 2.4.7 |
| 3 | Parent 1 Child 1 | 1 | 1.3 |
| 5 | Parent 1 Child 1 Child | 3 | 1.3.5 |
+----+--------------------------+----------+------------------+
Elk knooppunt N heeft een gematerialiseerd pad, dit pad vertelt je de weg van het hoofdknooppunt naar het knooppunt N . Het kan worden gebouwd door de node-ID's aan elkaar te koppelen. Om bijvoorbeeld knooppunt 5 . te bereiken beginnend bij zijn hoofdknooppunt, bezoekt u knooppunt 1 , knoop 3 , en knoop 5 , dus knoop 5 gematerialiseerd pad is 1.3.5
Toevallig kan de volgorde die u zoekt, worden bereikt door het gematerialiseerde pad te volgen.
In het vorige voorbeeld zijn gematerialiseerde paden alleen aaneengeschakelde strings, maar ik geef om een aantal redenen de voorkeur aan binaire aaneenschakeling.
Om de gematerialiseerde paden te bouwen, hebt u de volgende recursieve CTE nodig:
CREATE TABLE Tree
(
ID int NOT NULL CONSTRAINT PK_Tree PRIMARY KEY,
Name nvarchar(250) NOT NULL,
ParentID int NOT NULL,
)
INSERT INTO Tree(ID, Name, ParentID) VALUES
(1, 'Parent 1', 0),
(2, 'Parent 2', 0),
(3, 'Parent 1 Child 1', 1),
(4, 'Parent 2 Child 1', 2),
(5, 'Parent 1 Child 1 Child', 3),
(6, 'Parent 2 Child 1 Child 1', 4),
(7, 'Parent 2 Child 1 Child 2', 4)
GO
WITH T AS
(
SELECT
N.ID, N.Name, N.ParentID, CAST(N.ID AS varbinary(512)) AS MaterializedPath
FROM
Tree N
WHERE
N.ParentID = 0
UNION ALL
SELECT
N.ID, N.Name, N.ParentID, CAST( T.MaterializedPath + CAST(N.ID AS binary(4)) AS varbinary(512) ) AS MaterializedPath
FROM
Tree N INNER JOIN T
ON N.ParentID = T.ID
)
SELECT *
FROM T
ORDER BY T.MaterializedPath
Resultaat:
+----+--------------------------+----------+----------------------------+
| ID | Name | ParentID | MaterializedPath |
+----+--------------------------+----------+----------------------------+
| 1 | Parent 1 | 0 | 0x00000001 |
| 3 | Parent 1 Child 1 | 1 | 0x0000000100000003 |
| 5 | Parent 1 Child 1 Child | 3 | 0x000000010000000300000005 |
| 2 | Parent 2 | 0 | 0x00000002 |
| 4 | Parent 2 Child 1 | 2 | 0x0000000200000004 |
| 6 | Parent 2 Child 1 Child 1 | 4 | 0x000000020000000400000006 |
| 7 | Parent 2 Child 1 Child 2 | 4 | 0x000000020000000400000007 |
+----+--------------------------+----------+----------------------------+
De bovenstaande recursieve CTE begint met de wortelknooppunten. Het berekenen van het gematerialiseerde pad voor een hoofdknooppunt is triviaal eenvoudig, het is de ID van het knooppunt zelf. Bij de volgende iteratie verbindt de CTE de hoofdknooppunten met zijn onderliggende knooppunten. Het gematerialiseerde pad voor een onderliggende node CN is de aaneenschakeling van het gematerialiseerde pad van zijn bovenliggende knoop PN en de id van knooppunt CN . Daaropvolgende iteraties gaan een niveau lager in de boom totdat de bladknopen zijn bereikt.