Jak posortować połączoną listę w sql?

Zaimplementowałem listę linkowaną jako samodzielną tabelę bazy danych: 

CREATE TABLE LinkedList(
    Id bigint NOT NULL,
    ParentId bigint NULL,
    SomeData nvarchar(50) NOT NULL)

Gdzie Id jest kluczem głównym, a ParentId jest identyfikatorem poprzedniego węzła na liście. Pierwszy węzeł ma ParentId = NULL.

Chcę teraz wybrać z tabeli, sortując wiersze w tej samej kolejności, w jakiej powinny się pojawić, jako węzły na liście.

Np.: jeśli tabela zawiera wiersze 

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60088   60089     3
60089   38324     2
61039   61497     5
61497   60088     4
109397  109831    7
109831  61039     6

Następnie sortowanie go, stosując kryteria, powinno skutkować: 

Id      ParentId  SomeData
24971   NULL      0
38324   24971     1
60089   38324     2
60088   60089     3
61497   60088     4
61039   61497     5
109831  61039     6
109397  109831    7

You ' re supposed aby użyć SomeData colum jako kontrolki, więc proszę nie oszukiwać wykonując ORDER BY SomeData :-)

Author: John Calsbeek, 2009-02-05
Source

3 answers

W Oracle: 

SELECT Id, ParentId, SomeData
FROM (
  SELECT ll.*, level AS lvl
  FROM LinkedList ll
  START WITH
    ParentID IS NULL
  CONNECT BY
    ParentId = PRIOR Id
)
ORDER BY
  lvl

P. S. używanie NULL jako ParentID jest złą praktyką, ponieważ nie można go przeszukiwać indeksami. Wstawić zastępczy root o id 0 lub {[4] } zamiast tego i użyć START WITH ParentID = 0.

 9
Author: Quassnoi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-05 13:22:59

Znalazłem rozwiązanie dla SQLServer, ale wygląda na duże i znacznie mniej eleganckie niż Quassnoi 

WITH SortedList (Id, ParentId, SomeData, Level)
AS
(
  SELECT Id, ParentId, SomeData, 0 as Level
    FROM LinkedList
   WHERE ParentId IS NULL
  UNION ALL
  SELECT ll.Id, ll.ParentId, ll.SomeData, Level+1 as Level
    FROM LinkedList ll
   INNER JOIN SortedList as s
      ON ll.ParentId = s.Id
)

SELECT Id, ParentId, SomeData
  FROM SortedList
 ORDER BY Level
 10
Author: Nuno G,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-05 13:17:13

(edit: d ' Oh! Podczas debugowania też go znalazłeś!)

W Sql Server: 

;WITH cte (Id, ParentId, SomeData, [Level]) AS (
    SELECT Id, ParentId, SomeData, 0
    FROM LinkedList
    WHERE ParentId IS NULL
    UNION ALL
    SELECT ll.Id, ll.ParentId, ll.SomeData, cte.[Level] + 1
    FROM LinkedList ll
    INNER JOIN cte ON ll.ParentID = cte.ID
)
SELECT * FROM cte
ORDER BY [Level]
 5
Author: Marc Gravell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-05 13:27:09