sql - transact - tipo de dato hierarchyid

SQL optimizado para estructuras de árbol

Question

¿Cómo obtendría datos estructurados en árbol de una base de datos con el mejor rendimiento? Por ejemplo, supongamos que tiene una jerarquía de carpetas en una base de datos. Donde la carpeta-database-row tiene ID , nombre y columnas ParentID .

¿Utilizaría un algoritmo especial para obtener todos los datos a la vez, minimizando la cantidad de llamadas a la base de datos y procesándolo en código?

¿O utilizarías muchas llamadas a la base de datos y obtendrás la estructura de la base de datos directamente?

Tal vez hay diferentes respuestas basadas en x cantidad de filas de bases de datos, jerarquía de profundidad o lo que sea.

Editar : uso Microsoft SQL Server, pero las respuestas desde otras perspectivas también son interesantes.

Answer 1

Celko escribió sobre esto (2000):

http://www.dbmsmag.com/9603d06.html

http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

y otras personas preguntaron:

Unirse a otras tablas en consultas de árbol oráculo

Cómo calcular la suma de valores en un árbol usando SQL

¿Cómo almacenar el directorio / jerarquía / estructura de árbol en la base de datos?

Rendimiento de procedimientos almacenados recursivos en MYSQL para obtener datos jerárquicos

¿Cuál es la forma más eficiente / elegante de analizar una tabla plana en un árbol?

finalmente, podrías mirar los complementos "acts_as_tree" (leer-pesado) y "acts_as_nested_set" (escribir-pesado). No tengo un buen enlace para compararlos.

Answer 2

De todas las maneras de almacenar un árbol en un RDMS, las más comunes son listas de adyacencia y conjuntos anidados. Los conjuntos anidados están optimizados para lecturas y pueden recuperar un árbol completo en una sola consulta. Las listas de adyacencia están optimizadas para escrituras y se pueden agregar en una consulta simple.

Con las listas de adyacencia, cada nodo tiene una columna que hace referencia al nodo primario o al nodo secundario (otros enlaces son posibles). Al usar eso, puede construir la jerarquía en base a las relaciones primarias de los padres. Desafortunadamente, a menos que restrinja la profundidad de su árbol, no puede extraer todo en una consulta y, por lo general, leer es más lento que actualizarlo.

Con el modelo de conjunto anidado, el inverso es verdadero, la lectura es rápida y fácil, pero las actualizaciones se vuelven complejas porque debe mantener el sistema de numeración. El modelo de conjunto anidado codifica la paternidad y el orden de clasificación al enumerar todos los nodos utilizando un sistema de numeración basado en preorden.

He usado el modelo de conjunto anidado y, si bien es complejo para optimizar la lectura de una jerarquía grande, lo vale. Una vez que hagas algunos ejercicios para dibujar el árbol y numerar los nodos deberías entenderlo.

Mi investigación sobre este método comenzó en este artículo: Gestión de datos jerárquicos en MySQL .

Answer 3

En Oracle hay instrucción SELECT ... CONNECT BY para recuperar árboles.

Answer 4

En el producto en el que trabajo, tenemos algunas estructuras de árbol almacenadas en SQL Server y utilizamos la técnica mencionada anteriormente para almacenar la jerarquía de un nodo en el registro. es decir

tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)

Mantener la jerarquía es el truco por supuesto y hace uso de desencadenantes. Pero generarlo en una inserción / eliminación / movimiento nunca es recursivo, porque la jerarquía del padre o del niño tiene toda la información que necesita.

puedes obtener todos los descendientes del nodo por lo tanto:

SELECT * FROM tblNode WHERE Hierarchy LIKE ''%.100.%''

Aquí está el disparador de inserción:

--Setup the top level if there is any
UPDATE T 
SET T.TreeNodeHierarchy = ''.'' + CONVERT(nvarchar(10), T.TreeNodeID) + ''.''
FROM tblTreeNode AS T
    INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)

WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
    BEGIN
        --Update those items that we have enough information to update - parent has text in Hierarchy
        UPDATE CHILD 
        SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + ''.''
        FROM tblTreeNode AS CHILD 
            INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
        WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
    END

y aquí está el activador de actualización:

--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
    BEGIN
        --Update the changed items to reflect their new parents
        UPDATE CHILD
        SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN ''.'' + CONVERT(nvarchar,CHILD.TreeNodeID) + ''.'' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + ''.'' END
        FROM tblTreeNode AS CHILD 
            INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
            LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID

        --Now update any sub items of the changed rows if any exist
        IF EXISTS (
                SELECT * 
                FROM tblTreeNode 
                    INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
            )
            UPDATE CHILD 
            SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
            FROM tblTreeNode AS CHILD 
                INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + ''%'')
                INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID

    END

un bit más, una restricción de verificación para evitar una referencia circular en nodos de árbol:

ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
((charindex((''.'' + convert(nvarchar(10),[TreeNodeID]) + ''.''),[TreeNodeHierarchy],(charindex((''.'' + convert(nvarchar(10),[TreeNodeID]) + ''.''),[TreeNodeHierarchy]) + 1)) = 0))

También recomendaría desencadenantes para evitar más de un nodo raíz (padre nulo) por árbol y para evitar que los nodos relacionados pertenezcan a diferentes TreeID (pero estos son un poco más triviales que los anteriores).

Deberá verificar su caso particular para ver si esta solución funciona aceptablemente. ¡Espero que esto ayude!

Answer 5

Google para "Camino Materializado" o "Árboles Genéticos" ...

Answer 6

Hay varios tipos comunes de consultas en una jerarquía. La mayoría de otros tipos de consultas son variaciones de estos.

1. De un padre, encuentre a todos los niños.

   a. A una profundidad específica. Por ejemplo, dado mi padre inmediato, todos los niños a una profundidad de 1 serán mis hermanos.

   segundo. Al pie del árbol.

2. Desde un niño, encuentre a todos los padres.

   a. A una profundidad específica. Por ejemplo, mi padre inmediato es padres con una profundidad de 1.

   segundo. A una profundidad ilimitada

Los (a) casos (una profundidad específica) son más fáciles en SQL. El caso especial (profundidad = 1) es trivial en SQL. La profundidad distinta de cero es más difícil. Una profundidad finita, pero distinta de cero, se puede hacer a través de un número finito de uniones. Los (b) casos, con profundidad indefinida (arriba, abajo), son realmente difíciles.

Si tu árbol es ENORME (millones de nodos), entonces estás en un mundo herido sin importar lo que trates de hacer.

Si su árbol tiene menos de un millón de nodos, simplemente tráigalo todo a la memoria y trabaje allí. La vida es mucho más simple en un mundo OO. Simplemente busque las filas y construya el árbol a medida que se devuelven las filas.

Si tienes un árbol enorme , tienes dos opciones.

• Cursores recursivos para manejar la búsqueda ilimitada. Esto significa que el mantenimiento de la estructura es O (1): simplemente actualice algunos nodos y listo. Sin embargo, la búsqueda es O (n * log (n)) porque debe abrir un cursor para cada nodo con hijos.

• Los algoritmos inteligentes de "numeración de pila" pueden codificar el origen de cada nodo. Una vez que cada nodo está correctamente numerado, se puede usar un SQL SELECT trivial para los cuatro tipos de consultas. Los cambios en la estructura del árbol, sin embargo, requieren volver a numerar los nodos, lo que hace que el costo de un cambio sea bastante alto en comparación con el costo de recuperación.

Answer 7

No va a funcionar para todas las situaciones, pero por ejemplo se le da una estructura de comentarios:

ID | ParentCommentID

También puede almacenar TopCommentID que representa el comentario más destacado:

ID | ParentCommentID | TopCommentID

Donde TopCommentID y ParentCommentID son null o 0 cuando es el comentario más alto. Para comentarios secundarios, ParentCommentID apunta al comentario anterior y TopCommentID apunta al padre superior.

Answer 8

Realmente depende de cómo va a acceder al árbol.

Una técnica inteligente es dar a cada nodo un ID de cadena, donde el ID del padre es una subcadena predecible del niño. Por ejemplo, el padre podría ser ''01'', y los hijos serían ''0100'', ''0101'', ''0102'', etc. De esta manera puede seleccionar un subárbol completo de la base de datos a la vez con:

SELECT * FROM treedata WHERE id LIKE ''0101%'';

Como el criterio es una subcadena inicial, un índice en la columna de ID aceleraría la consulta.

Answer 9

Si tiene muchos árboles en la base de datos, y solo obtendrá el árbol completo, yo almacenaría una ID de árbol (o ID de nodo raíz) y una ID de nodo padre para cada nodo en la base de datos, obtendría todos los nodos para una ID de árbol particular, y proceso en memoria.

Sin embargo, si va a obtener subárboles, solo puede obtener un subárbol de una ID de nodo padre particular, por lo que debe almacenar todos los nodos principales de cada nodo para usar el método anterior o realizar múltiples consultas SQL a medida que desciende al árbol (¡espero que no haya ciclos en su árbol!), aunque puede reutilizar el mismo Estado Preparado (suponiendo que los nodos son del mismo tipo y están todos almacenados en una sola tabla) para evitar volver a compilar el SQL, por lo que podría no ser más lento, de hecho, con las optimizaciones de bases de datos aplicadas a la consulta podría ser preferible. Es posible que desee ejecutar algunas pruebas para averiguarlo.

Si solo está almacenando un árbol, su pregunta se convierte en una pregunta de subárboles solamente, y la segunda respuesta aplicada.

Answer 10

Soy un fan del método simple de almacenar una identificación asociada con su parentID:

ID     ParentID
1      null
2      null
3      1
4      2
...    ...

Es fácil de mantener y muy escalable.

Answer 11

mira en el modelo de jerarquía de conjuntos anidados . es genial y útil.

Answer 12

Este artículo es interesante, ya que muestra algunos métodos de recuperación, así como una forma de almacenar el linaje como una columna derivada. El linaje proporciona un método de acceso directo para recuperar la jerarquía sin demasiadas uniones.