Estoy pensando la respuesta es no, pero me encantaría que alguien tenía 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 estructura de árbol tabla (id, datos, datos, parent_id), y una fila en la tabla, es posible obtener todos descendientes (hijos o nietos/etc), o para el caso de todos los antepasados (padres/abuelos/etc) sin saber cuán lejos hacia abajo o hacia arriba se va a ir, el uso de una sola consulta?

O el uso de algún tipo de recursividad requieren, donde guardo la consulta de mas hasta que no hay nuevos resultados?

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

  • PostgreSQL permite la utilización directa de la cola-recursivo (= iterativo) las consultas, pero que yo sepa MySQL no. He utilizado con éxito esta técnica, antes de que en Postgres como un sustituto de la nested-conjuntos de enfoque. postgresql.org/docs/8.4/static/queries-with.html

9 Comentarios

  1. 37

    Sí, esto es posible, es un llamado a una Modificación de la Preorden del Árbol de Recorrido, como mejor se describe aquí

    Joe Celko los Árboles y las Jerarquías en SQL para Lacasitos

    Un ejemplo de trabajo (en PHP) que se proporciona aquí

    http://www.sitepoint.com/article/hierarchical-data-database/2/

    • Ok… tengo que conseguir ese libro ahora. He usado esa estructura varias veces, con diferente fuente de información cada vez…
    • En serio – get Celko SQL para Lacasitos. ES la biblia para SQL
    • (Eso es realmente aterrador.)
    • Hay un libro entero sobre eso?! No puede ser resumida en 2 o 3 páginas? (igual que el artículo en SitePoint!)
    • El sitePoint artículo es simplemente genial!
    • He llegado a través de esta idea un par de veces, pero hasta donde yo recuerdo, que el sistema, a pesar de parecer muy inteligente, abandona mucho de lo que hace RDBMS rápido y seguro. Si usted tiene un gran árbol y la necesidad de insertar algo en una de las ramas más antiguas, usted tendrá que actualizar casi cada registro de la tabla, y lo mismo si se elimina. Creo que me gustaría recomendar a los niños tomar la carretera más transitada cuando se trata de este problema. Pero yo no soy un experto.
    • Si usted lee el árbol más de lo que lo actualice, luego la estructura que se presenta es realmente ventajoso, y de la OMI, que es el escenario más común que se enfrentan.

  2. 23

    Aquí hay varios recursos:

    Básicamente, tendrás que hacer algún tipo de cursor en un procedimiento almacenado o una consulta o construir una tabla de adyacencia. Me gustaría evitar la recursividad fuera de la base de datos: dependiendo de la profundidad de su árbol, que podrían ponerse muy lento/vagos.

    • el segundo enlace donde se discuten los Conjuntos Anidados es muy bueno – nunca se me había ocurrido hacerlo de esa manera!
    • Ese enlace también menciona Joe Celko del libro.
  3. 3

    Daniel Beardsley la respuesta es que no es una mala solución a todos cuando las principales preguntas son «¿qué son todos mis hijos’ y ‘lo que son todos los de mis padres.

    En respuesta a Alex Weinstein, este método resulta en menos actualizaciones a los nodos de un padre movimiento que en el Celko técnica. En Celko de la técnica, en caso de un nivel de 2 nodo en el extremo izquierdo se mueve bajo un nivel de 1 nodo en el extremo derecho, entonces casi cada nodo en el árbol de las necesidades de actualización, en lugar de sólo el nodo hijos.

    Lo que yo diría, sin embargo, es que Daniel posiblemente almacena el camino de regreso a la raíz al revés.

    Podría almacenar de manera que la consulta sería

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

    Esto significa que mysql se puede hacer uso de un índice de los ‘antepasados’ columna, que no sería capaz de hacer con una de las principales %.

    • El almacenamiento de valores separados por comas en una columna tiene varios integridad y problemas de rendimiento. Es realmente tan malo.
    • No. No, No es así.
    • 52 por LO que los usuarios de acuerdo con usted: Es el almacenamiento de una lista separada por comas en una columna de base de datos realmente tan malo?
    • OK, así que usted copia de seguridad de su argumento. Acaba de decir » que no es una buena idea, sin copias de seguridad con un razonamiento es útil a nadie. El ejemplo que dan es que alguien está utilizando una lista separada por comas para almacenar una relación de uno a muchos relación. Esto fue claramente errónea. Sin embargo aquí nos están utilizando como un caché para acelerar el rendimiento de la consulta. Es totalmente diferente del caso de uso. No estamos proponiendo la sustitución de la parent_id columna en la tabla, simplemente almacenar en caché ruta de acceso de la raíz en una forma en que no tenemos de forma recursiva consulta de la estructura.
    • Es obvio que no me acaba de decir que no es una buena idea. Me dijo: «hay varios integridad y problemas de rendimiento.»
    • ( también es que no se dice, pero obvio , que esta técnica funciona solamente para ciertas longitudes de identificación de una cierta profundidad. Para árboles muy grandes que había agotado el espacio en la columna )
    • I don’t quiero entrar en una guerra llama, pero no se puede decir ‘hay problemas con esto’, sin decir cuáles son esas cuestiones. No aportan nada a la discusión.
    • Puedo ver la ventaja de la sencillez de este enfoque (el LIKE consulta que usted sugiere, y FIND_IN_SET cláusulas). La actualización de ascendencia descendencia podría lograrse en una sola UPDATE table SET ancestors=REPLACE(ancestors, old_path, new_path) WHERE ancestors LIKE old_path+'%'; estoy tratando de pensar en cualquier otra de las principales debilidades de este enfoque además de las cuestiones de integridad (que parece bastante fácil de manejar, con un bien diseñado capa de datos). En cuanto al rendimiento, de hecho, estoy curioso por saber si las búsquedas con este enfoque puede ser más rápido que algunos recursiva de los enfoques que he encontrado.

  4. 2

    Me encontré con este problema antes y había una extravagante idea. Se puede almacenar en un campo en cada registro que se concatena la cadena de antepasados directos’ id todo el camino de vuelta a la raíz.

    Imagínese que tiene discos como este (sangría implica jerarquía y los números de identificación, los 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»

    A continuación, a seleccionar los descendientes de identificación:6, acabo de hacer este

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

    Mantener los antepasados de la columna hasta la fecha podría ser más problemático de lo que vale la pena para usted, pero es una solución factible en cualquier DB.

    • mantener este sería el infierno. imagínese si el nodo 3 cambios. Usted necesita para hacer una ACTUALIZACIÓN en todos sus hijos.
    • Suponiendo que invertir el orden de la ruta, por lo que la raíz antepasado está a la izquierda (ex id 5 y 6, los antepasados=’1,2′), y más directa de los padres está en la derecha (como @Kray sugiere en su respuesta), la actualización de los niños podría lograrse en una sola consulta que establece antepasados = REPLACE(antepasados, old_path, new_path). Si la jerarquía de la estructura no es muy grande o no cambia a menudo, no creo que esta es una mala manera de ir. Utilizando COMO «1,2%» o FIND_IN_SET con esta estructura, la ascendencia consultas de base (para los descendientes o de los antepasados) podría ser simplificado en gran medida.
  5. 2

    Celko de la técnica (conjuntos anidados) es bastante bueno. También he utilizado una tabla de adyacencia con los campos «ancestro» y «descendiente» y «distancia» (por ejemplo la acción directa de los niños/padres tienen una distancia de 1, nietos o abuelos tienen una distancia de 2, etc).

    Esto debe mantenerse, pero es bastante fácil de hacer para las inserciones: puede utilizar una transacción, a continuación, poner el enlace directo (padre, hijo, distancia=1) en la tabla, a continuación, INSERTE IGNORAR una Selección de padres&niños mediante la adición de distancias (puedo abrir el SQL cuando tengo una oportunidad), que quiere un índice en cada uno de los 3 campos de actuación. Donde este enfoque pone fea es para las eliminaciones… básicamente tienes que marcar todos los artículos que han sido afectadas y luego reconstruirlas. Pero una ventaja de esto es que se puede manejar arbitraria acíclicos gráficos, mientras que el conjunto anidado modelo sólo se puede hacer directamente jerarquías (por ejemplo, cada elemento, excepto la raíz tiene uno y sólo uno de los padres).

  6. 1

    SQL no es Turing Completo idioma, lo que significa que no vas a ser capaz de realizar este tipo de bucle. Usted puede hacer algunas cosas muy inteligente con SQL y las estructuras de árbol, pero no puedo pensar en una manera de describir una fila que tiene una cierta identificación «en su jerarquía» para una jerarquía de profundidad arbitraria.

    Su mejor apuesta es algo a lo largo de las líneas de lo que @Dan sugiere, que es sólo el trabajo de su camino a través de los árboles en algunos otros, más capaces de lenguaje. En realidad se puede generar una cadena de consulta en un idioma de propósito general mediante un bucle, donde la consulta es sólo una complicada serie de combinaciones (o sub-consultas) que refleja la profundidad de la jerarquía que usted está buscando. Que sería más eficiente que el bucle y varias consultas.

  7. -1

    Casi seguro vas a querer emplear la recursividad para que. Y si usted está haciendo eso, entonces sería trivial (de hecho es más fácil) para obtener el árbol entero en lugar de los bits de a una profundidad fija.

    En realidad áspera de pseudo-código que usted querrá algo a lo largo de estas líneas:

    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 había rara vez quiero hacer algo como esto. Va a ser bastante ineficiente ya que se trata de hacer una solicitud para cada fila de la tabla, por lo que sólo vamos a ser sensatos, ya sea para pequeñas tablas o árboles que no son demasiado anidados. Para ser honesto, en cualquier caso, usted probablemente querrá limitar la profundidad.

    Sin embargo, dada la popularidad de este tipo de estructura de datos, es muy posible que algunos de MySQL cosas para ayudar con esto, específicamente para reducir el número de consultas que usted necesita hacer.

    Edit: de Haber pensado en ello, hace muy poco sentido hacer todas estas consultas. Si estás leyendo la tabla completa de todos modos, entonces usted puede obtener toda la cosa en la memoria RAM – asumiendo que es lo suficientemente pequeño!

Dejar respuesta

Please enter your comment!
Please enter your name here