the adjacency mysql sql database-design data-structures hierarchical-data

adjacency - ¿Es posible consultar una tabla de estructura de árbol en MySQL en una sola consulta, a cualquier profundidad?



mysql category tree (9)

Aquí hay varios recursos:

Básicamente, tendrá que hacer algún tipo de cursor en un procedimiento almacenado o consulta o crear una tabla de adyacencia. Evitaría la recursión fuera del DB: dependiendo de cuán profundo sea tu árbol, podría ser realmente lento / incompleto.

Estoy pensando que la respuesta es no, pero me encantaría que alguien tuviera alguna idea de cómo rastrear una estructura de árbol a cualquier profundidad en SQL (MySQL), pero con una sola consulta

Más específicamente, dada una tabla estructurada por árbol (id, datos, datos, parent_id) y una fila en la tabla, es posible obtener todos los descendientes (hijo / nieto / etc), o para el caso todos los antepasados ​​(padre / abuelo / etc) sin saber cuán abajo o hacia abajo funcionará, usando una sola consulta?

¿O es necesario recurrir a algún tipo de recurrencia, donde continúo investigando hasta que no hay nuevos resultados?

Específicamente, estoy usando Ruby and Rails, pero supongo que eso no es muy relevante.

Definitivamente va a querer emplear alguna recursión para eso. Y si estás haciendo eso, entonces sería trivial (de hecho más fácil) obtener todo el árbol en lugar de bits hasta una profundidad fija.

En un pseudo-código realmente tosco, querrás algo en esta línea:

getChildren(parent){ children = query(SELECT * FROM table WHERE parent_id = parent.id) return children } printTree(root){ print root children = getChildren(root) for child in children { printTree(child) } }

Aunque en la práctica rara vez querrás hacer algo como esto. Será bastante ineficiente ya que está haciendo una solicitud para cada fila en la tabla, por lo que solo será sensata para tablas pequeñas o árboles que no estén anidados demasiado profundamente. Para ser honesto, en cualquier caso, probablemente quieras limitar la profundidad.

Sin embargo, dada la popularidad de este tipo de estructura de datos, es muy posible que haya algunas cosas de MySQL para ayudarlo con esto, específicamente para reducir el número de consultas que necesita realizar.

Editar: habiéndolo pensado, tiene muy poco sentido hacer todas estas consultas. Si de todos modos lees toda la tabla, puedes sorber todo en RAM, ¡suponiendo que sea lo suficientemente pequeño!

Esto definitivamente se puede hacer y no es tan complicado para SQL. Respondí esta pregunta y proporcioné un ejemplo de trabajo usando el código de procedimiento de mysql aquí:

MySQL: Cómo encontrar hojas en un nodo específico

Booth: si está satisfecho, debe marcar una de las respuestas como aceptada.

La respuesta de Daniel Beardsley no es una solución tan mala cuando las principales preguntas que hace son "¿qué son todos mis hijos?" Y "¿qué son todos mis padres?".

En respuesta a Alex Weinstein, este método realmente da como resultado menos actualizaciones de nodos en un movimiento parental que en la técnica de Celko. En la técnica de Celko, si un nodo de nivel 2 en el extremo izquierdo se mueve debajo de un nodo de nivel 1 en el extremo derecho, entonces casi todos los nodos en el árbol necesitan actualización, en lugar de solo los hijos del nodo.

Sin embargo, lo que diría es que Daniel posiblemente almacena el camino de regreso para rootear el camino equivocado.

Los almacenaría para que la consulta sea

SELECT FROM table WHERE ancestors LIKE "1,2,6%"

Esto significa que mysql puede hacer uso de un índice en la columna ''ancestros'', que no sería capaz de hacer con un% inicial.

La técnica de Celko (conjuntos anidados) es bastante buena. También utilicé una tabla de adyacencia con los campos "ancestro" y "descendiente" y "distancia" (por ejemplo, los hijos / padres directos tienen una distancia de 1, los nietos / abuelos tienen una distancia de 2, etc.).

Esto debe mantenerse, pero es bastante fácil de hacer para inserciones: usa una transacción, luego coloca el enlace directo (padre, hijo, distancia = 1) en la tabla, luego INSERTAR IGNORAR una SELECCIÓN de padres e hijos existentes agregando distancias ( Puedo extraer el SQL cuando tengo la oportunidad), que quiere un índice en cada uno de los 3 campos para el rendimiento. Donde este enfoque se pone feo es para eliminaciones ... básicamente tienes que marcar todos los elementos que han sido afectados y luego reconstruirlos. Pero una ventaja de esto es que puede manejar gráficos acíclicos arbitrarios, mientras que el modelo de conjuntos anidados solo puede hacer jerarquías rectas (por ejemplo, cada elemento, excepto que la raíz tiene uno y solo uno principal).

Me encontré con este problema antes y tuve una idea loca. Puede almacenar un campo en cada registro que sea cadena concatenada de sus identidades de ancestros directos desde la raíz.

Imagina que tienes registros como este (la sangría implica jerarquía y los números son id, antepasados).

  • 1, "1"
    • 2, "2,1"
      • 5, "5,2,1"
      • 6, "6,2,1"
        • 7, "7,6,2,1"
        • 11, "11,6,2,1"
    • 3, "3,1"
      • 8, "8,3,1"
      • 9, "9,3,1"
      • 10, "10,3,1"

Luego, para seleccionar los descendientes de id: 6 , solo haz esto

SELECT FROM table WHERE ancestors LIKE "%6,2,1"

Mantener la columna de los antepasados ​​actualizada puede ser más problemático de lo que vale para ti, pero es una solución factible en cualquier DB.

SQL no es un lenguaje de Turing Complete, lo que significa que no podrá realizar este tipo de bucle. Puede hacer algunas cosas muy inteligentes con SQL y estructuras de árbol, pero no puedo pensar en una manera de describir una fila que tiene una determinada identificación "en su jerarquía" para una jerarquía de profundidad arbitraria.

Su mejor apuesta es algo en la línea de lo que @Dan sugirió, que es simplemente abrirse paso en el árbol en otro lenguaje más capaz. En realidad, puede generar una cadena de consulta en un lenguaje de uso general mediante un bucle, donde la consulta es solo una serie complicada de uniones (o subconsultas) que refleja la profundidad de la jerarquía que está buscando. Eso sería más eficiente que el bucle y las consultas múltiples.

Utilicé la rutina "Con Emulador" que se describe en https://.com/questions/27013093/recursive-query-emulation-in-mysql (proporcionada por https://.com/users/1726419/yossico ). Hasta ahora, he obtenido muy buenos resultados (en cuanto a rendimiento), pero no tengo una gran cantidad de datos o un gran número de descendientes para buscar a través de / for.