database - tipos - ¿Cómo se ordena un árbol almacenado utilizando el modelo de conjunto anidado?

procedimientos almacenados sql ejemplos

Question

Cuando me refiero al modelo de conjunto anidado me refiero a lo que se describe aquí.

Necesito construir un nuevo sistema para almacenar "categorías" (no se me ocurre una palabra mejor) en una jerarquía definida por el usuario. Como el modelo de conjunto anidado está optimizado para lecturas en lugar de escrituras, decidí usar eso. Desafortunadamente, durante mi investigación y prueba de conjuntos anidados, me encontré con el problema de cómo mostrar el árbol jerárquico con nodos ordenados. Por ejemplo, si tengo la jerarquía:

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

Quiero que se ordene para que se muestre como:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

Tenga en cuenta que la fabricación aparece antes de la investigación.

De todos modos, después de una larga búsqueda, vi respuestas como "almacenar el árbol en una matriz multidimensional y ordenarlo" y "recurrir al árbol y volver a serializarlo en el modelo de conjunto anidado" (estoy parafrazándolo ...). De cualquier manera, la primera solución es una pérdida horrible de RAM y CPU, que son recursos muy limitados ... La segunda solución parece un código muy doloroso.

A pesar de eso, pude averiguar cómo (usando el modelo de conjunto anidado):

1. Comience un nuevo árbol en SQL
2. Insertar un nodo como hijo de otro nodo en el árbol
3. Insertar un nodo después de un nodo hermano en el árbol
4. Tire de todo el árbol con la estructura jerárquica de SQL
5. Extraiga un subárbol de un nodo específico (incluida la raíz) en la jerarquía con o sin un límite de profundidad
6. Encuentre el padre de cualquier nodo en el árbol

Así que pensé que # 5 y # 6 podrían usarse para hacer la clasificación que quería, y también podría usarse para reconstruir el árbol en orden ordenado.

Sin embargo, ahora que he visto todas estas cosas que aprendí a hacer, veo que # 3, # 5 y # 6 podrían usarse juntos para realizar inserciones clasificadas. Si hice insertos ordenados, siempre se ordenan. Sin embargo, si alguna vez cambio los criterios de clasificación o si deseo un orden de clasificación diferente, volveré al punto uno.

¿Podría ser esta la limitación del modelo de conjunto anidado? ¿Su uso inhibe la clasificación de consulta de la salida?

Answer 1

Creo que esto es una limitación del modelo de conjunto anidado. No puede ordenar fácilmente los nodos secundarios dentro de su nodo padre respectivo, porque el orden del conjunto de resultados es esencial para reconstruir la estructura del árbol.

Creo que es probablemente el mejor enfoque para mantener ordenado el árbol al insertar, actualizar o eliminar nodos. Esto incluso hace consultas muy rápido, que es uno de los objetivos principales de esta estructura de datos. Si implementa procedimientos almacenados para todas las operaciones, es muy fácil de usar.

También puede revertir el orden de clasificación de un árbol preseleccionado. Solo tiene que usar ORDER BY node.rgt DESC lugar de ORDER BY node.lft ASC .

Si realmente necesita soportar otro criterio de clasificación, podría implementarlo añadiendo un segundo índice lft y rgt a cada nodo y mantenerlo ordenado por los otros criterios en cada inserción / actualización / eliminación.

Answer 2

Sí, es una limitación del modelo de conjunto anidado, ya que los conjuntos anidados son una representación preordenada de una jerarquía. Este preordenamiento es la razón por la cual es tan rápido para leer. El modelo de adyacencia, también descrito en la página a la que se vincula, proporciona la clasificación y el filtrado más flexibles, pero con un impacto significativo en el rendimiento.

Mi enfoque preferido para inserciones y movimientos en un conjunto anidado es manejar la rama afectada como en el modelo de adyacencia: obtener una lista de los nuevos hermanos; encuentre el lugar correcto en la lista para el nuevo nodo; y construye las declaraciones de actualización requeridas (ese es el bit donde realmente debes tener cuidado). En cuanto a cambiar sus criterios de ordenamiento: se trata de un trabajo discontinuo, por lo que puede permitirse utilizar RAM y CPU, la respuesta más flexible sería dividir la representación anidada en una representación de adyacencia y reconstruir el conjunto anidado de la adyacencia basada en nuevos criterios.

Answer 3

He usado mucho Nested Sets y me he enfrentado con frecuencia al mismo problema. Lo que hago, y lo que recomendaría, es simplemente no ordenar los elementos en la base de datos. En su lugar, ordénelos en la interfaz de usuario. Después de extraer todos los nodos de la base de datos, es probable que tenga que convertirlos en una estructura de datos jerárquica, de todos modos. En esa estructura, ordena todas las matrices que contienen los hijos del nodo.

Por ejemplo, si su interfaz es una aplicación Flex, y los elementos secundarios de un nodo se almacenan en un ICollectionView, puede usar la propiedad de ordenar para que se muestren de la forma que desee.

Otro ejemplo, si su interfaz es un resultado de un script PHP, puede tener los elementos secundarios de cada nodo en una matriz y utilizar las funciones de clasificación de matriz de PHP para realizar su clasificación.

Por supuesto, esto solo funciona si no necesita las entradas de datos reales para ser ordenadas, ¿verdad?

Answer 4

Acabo de terminar de escribir lo siguiente que me sirve para ordenar todo un árbol de conjunto anidado.

El género (idealmente) requiere una vista que enumere el nivel actual de cada nodo en el árbol y un procedimiento para intercambiar dos nodos, ambos se incluyen a continuación, el código de intercambio hermano viene del libro Tree & Hierarchies de Joe Celkos, que recomiendo encarecidamente a cualquiera que use conjuntos anidados.

El tipo se puede modificar en la instrucción ''INSERT INTO @t'', aquí se trata de un tipo alfanumérico simple en ''Name''

Esta puede ser una forma pobre de hacerlo especialmente usando el cursor para un código basado en el set pero como digo que funciona para mí, espero que ayude.

ACTUALIZAR:

El siguiente código muestra la versión sin usar cusor. Veo mejoras de velocidad 10x

CREATE VIEW dbo.tree_view

AS

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  
FROM dbo.tree t1,dbo.tree t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name

GO

----------------------------------------------

  DECLARE @CurrentNodeID int
DECLARE @CurrentActualOrder int
DECLARE @CurrentRequiredOrder int
DECLARE @DestinationNodeID int
DECLARE @i0 int
DECLARE @i1 int
DECLARE @i2 int
DECLARE @i3 int

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL)


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder)
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC)
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1
    WHERE tv2.rgt > tv2.lft+1

    DELETE FROM @t where ActualOrder = RequiredOrder


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder)
BEGIN


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder
    FROM @t 
    WHERE ActualOrder <> RequiredOrder
    ORDER BY toplft,requiredorder

    SELECT @DestinationNodeID = NodeID
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END,
            @i1 =  CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END,
            @i2 =  CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END,
            @i3 =  CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END
    FROM dbo.tree c
    CROSS JOIN dbo.tree d
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID

    UPDATE dbo.tree
    SET lft = CASE  WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1
                    WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2
            ELSE @i0 + @i3 + lft - @i1 - @i2
            END,
        rgt = CASE  WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1
                    WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2
            ELSE @i0 + @i3 + rgt - @i1 - @i2
            END
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1
    AND @i1 < @i2
    AND @i2 < @i3

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID

    DELETE FROM @t where ActualOrder = RequiredOrder

END

Answer 5

Creo que, en su caso, donde los nodos que desea intercambiar no tienen descendientes, simplemente puede intercambiar los valores de lft y rgt. Considera este árbol:

   A
 /   /
B     C
     / /
    D   E

Esto podría convertirse en este grupo de conjuntos anidados:

1 A 10 
2 B 3  
4 C 9
5 D 6
7 E 8

Ahora considere que desea intercambiar D y E. Los siguientes conjuntos anidados son válidos y D y E se intercambian:

1 A 10
2 B 3 
4 C 9 
7 D 8
5 E 6 

El intercambio de nodos que tienen subárboles no se puede hacer de esta manera, por supuesto, porque también necesitarías actualizar los valores lft y rgt de los niños.

Answer 6

La clasificación de conjuntos anidados no tiene límites y no es difícil. Solo ordene por la glorieta IZQUIERDA (ancla, lo que sea) y listo. Si tiene un NIVEL para cada nodo, también puede obtener una sangría correcta según el Nivel.

Answer 7

Vea mi solución simple del método de mi clase. $ this-> table-> order es el código de Nette framework para obtener datos de DB.

$tree = Array();
$parents = Array();
$nodes = $this->table->order(''depth ASC, parent_id ASC, name ASC'');
$i = 0;
$depth = 0;
$parent_id = 0;

foreach($nodes as $node) {
    if($depth < $node->depth || $parent_id < $node->parent_id) {
        $i = $parents["{$node->parent_id}"] + 1;
    }
    $tree[$i] = $node;
    $parents["{$node->id}"] = $i;
    $depth = $node->depth;
    $parent_id = $node->parent_id;
    $i += (($node->rgt - $node->lft - 1) / 2) + 1;
}
ksort($tree);

Answer 8

Puedes ordenarlo cuando renderices. Expliqué el renderizado aquí Cómo renderizar todos los registros de un conjunto anidado en un árbol html real