¿Cómo puedo ordenar una lista vinculada en sql?

Question

he implementado una lista enlazada como una tabla de base de datos de referencia a sí misma:

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

donde ID es la clave principal y parentid es el ID del nodo anterior en la lista. El primer nodo tiene ParentId = NULL.

Ahora quiero SELECCIONAR de la tabla, ordenando las filas en el mismo orden en que deberían aparecer, como nodos en la lista.

Ej .: si la tabla contiene las filas

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 

Luego de clasificación, utilizando los criterios, debería resultar en:

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 

Se supone que debes usar el somedata Colum como control, así que no haga trampa haciendo PEDIDO por SomeData :-)

Answer 1

En 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. Es una mala práctica utilizar NULL como ParentID, ya que no se puede buscar por índices. Inserte una raíz sustituta con id de 0 o -1 en su lugar, y use START WITH ParentID = 0.

Answer 2

he encontrado una solución para SQL Server, pero se ve grande y mucho menos elegante que el de 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 

Answer 3

(edit: d'oh Mientras estaba depurando lo encontró también!)

En SQL servidor:

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