Как отсортировать связанный список в SQL?

Question

Я реализовал связанный список в виде таблицы базы данных с самообращением:

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

где Id - это первичный ключ, а ParentId - это идентификатор предыдущего узла в списке. Первый узел имеет ParentId = NULL.

Теперь я хочу ВЫБРАТЬ из таблицы, сортируя строки в том порядке, в котором они должны отображаться, как узлы в списке.

Например: если таблица содержит строки

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

Затем сортировка по критериям должна привести к:

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

Вы должны использовать столбец SomeData в качестве элемента управления, поэтому, пожалуйста, не читайте, делая ЗАКАЗ SomeData : -)

Answer 1

Я нашел решение для SQLServer, но выглядит большим и гораздо менее элегантным, чем

Кассной

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

Answer 2

В 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. Использовать NULL как ParentID - плохая практика, так как он не доступен для поиска по индексам. Вставьте суррогатный корень с идентификатором 0 или -1 вместо этого и используйте START WITH ParentID = 0.

Answer 3

(edit: d'oh! Пока я отлаживал, вы тоже его нашли!)

В 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]