Recuperando lista enlazada en la base de datos MySQL

Tengo una tabla de base de datos MySQL con esta estructura:

table id INT NOT NULL PRIMARY KEY data .. next_id INT NULL 

Necesito buscar los datos en orden de la lista enlazada. Por ejemplo, dada esta información:

  id | next_id ----+--------- 1 | 2 2 | 4 3 | 9 4 | 3 9 | NULL 

Necesito buscar las filas para id = 1, 2, 4, 3, 9, en ese orden. ¿Cómo puedo hacer esto con una consulta de base de datos? (Puedo hacerlo desde el lado del cliente. Tengo curiosidad de saber si esto se puede hacer desde el lado de la base de datos. Por lo tanto, decir que es imposible está bien (dada la suficiente evidencia)).

Sería bueno tener un punto de terminación también (por ejemplo, detenerse después de 10 recuperaciones, o cuando alguna condición en la fila se convierte en verdadera) pero esto no es un requisito (se puede hacer en el lado del cliente). Yo (espero que) no necesite verificar referencias circulares.

Algunas marcas de bases de datos (por ejemplo, Oracle, Microsoft SQL Server) admiten una syntax SQL adicional para ejecutar “consultas recursivas”, pero MySQL no admite ninguna de esas soluciones.

El problema que está describiendo es lo mismo que representar una estructura de árbol en una base de datos SQL. Solo tienes un árbol largo y flaco.

Existen varias soluciones para almacenar y obtener este tipo de estructura de datos de un RDBMS. Vea algunas de las siguientes preguntas:

  • ” ¿Cuál es la forma más eficiente / elegante de analizar una tabla plana en un árbol? ”
  • ” ¿Es posible hacer una consulta SQL recursiva? ”

Como mencionas que quieres limitar la “profundidad” devuelta por la consulta, puedes lograrlo al consultar la lista de esta manera:

 SELECT * FROM mytable t1 LEFT JOIN mytable t2 ON (t1.next_id = t2.id) LEFT JOIN mytable t3 ON (t2.next_id = t3.id) LEFT JOIN mytable t4 ON (t3.next_id = t4.id) LEFT JOIN mytable t5 ON (t4.next_id = t5.id) LEFT JOIN mytable t6 ON (t5.next_id = t6.id) LEFT JOIN mytable t7 ON (t6.next_id = t7.id) LEFT JOIN mytable t8 ON (t7.next_id = t8.id) LEFT JOIN mytable t9 ON (t8.next_id = t9.id) LEFT JOIN mytable t10 ON (t9.next_id = t10.id); 

Funcionará como melaza, y el resultado volverá en una fila (por lista vinculada), pero obtendrá el resultado.

Si lo que intenta evitar es tener varias consultas (una para cada nodo) y puede agregar columnas, entonces podría tener una nueva columna que vincule al nodo raíz. De esta forma, puede obtener todos los datos a la vez mediante el ID raíz, pero igual tendrá que ordenar la lista (o el árbol) en el lado del cliente.

Entonces, en este ejemplo, tendrías:

  id | next_id | root_id ----+---------+--------- 1 | 2 | 1 2 | 4 | 1 3 | 9 | 1 4 | 3 | 1 9 | NULL | 1 

Por supuesto, la desventaja de esto en comparación con las listas o árboles vinculados tradicionales es que la raíz no puede cambiar sin escribir en un orden de magnitud de O (n) donde n es el número de nodos. Esto se debe a que tendrías que actualizar el ID de la raíz para cada nodo. Afortunadamente, sin embargo, siempre debes poder hacer esto en una única consulta de actualización a menos que estés dividiendo una lista / árbol en el medio.

Esto es menos una solución y más una solución, pero, para una lista lineal (en lugar del árbol que Bill Karwin mencionó), podría ser más eficiente usar una columna de clasificación en su lista. Por ejemplo:

 TABLE `schema`.`my_table` ( `id` INT NOT NULL PRIMARY KEY, `order` INT, data .., INDEX `ix_order` (`sort_order` ASC) ); 

Entonces:

 SELECT * FROM `schema`.`my_table` ORDER BY `order`; 

Esto tiene la desventaja de las inserciones más lentas (debe reposicionar todos los elementos ordenados más allá del punto de inserción) pero debe ser rápido para la recuperación porque la columna de orden está indexada.