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

517

Suponga que tiene una tabla plana que almacena una jerarquía de árbol ordenada:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

Aquí hay un diagrama, donde tenemos [id] Name. El nodo raíz 0 es ficticio.

                       [0] RAÍZ
                          / \ 
              [1] Nodo 1 [3] Nodo 2
              / \ \
    [2] Nodo 1.1 [6] Nodo 1.2 [5] Nodo 2.1
          / /          
 [4] Nodo 1.1.1

¿Qué enfoque minimalista usarías para enviar eso a HTML (o texto, para el caso) como un árbol correctamente ordenado y correctamente sangrado?

Supongamos además que solo tiene estructuras de datos básicas (matrices y hashmaps), sin objetos sofisticados con referencias padre / hijo, sin ORM, sin marco, solo sus dos manos. La tabla se representa como un conjunto de resultados, al que se puede acceder aleatoriamente.

El pseudo código o el inglés simple está bien, esta es una pregunta puramente conceptual.

Pregunta adicional: ¿existe una forma fundamentalmente mejor de almacenar una estructura de árbol como esta en un RDBMS?


EDICIONES Y ADICIONES

Para responder a la pregunta de un comentarista ( Mark Bessey ): No es necesario un nodo raíz, porque de todos modos nunca se mostrará. ParentId = 0 es la convención para expresar "estos son de nivel superior". La columna Orden define cómo se ordenarán los nodos con el mismo padre.

El "conjunto de resultados" del que hablé se puede representar como una matriz de hashmaps (para mantenerse en esa terminología). Para mi ejemplo, estaba destinado a estar allí. Algunas respuestas hacen un esfuerzo adicional y lo construyen primero, pero está bien.

El árbol puede ser arbitrariamente profundo. Cada nodo puede tener N hijos. Sin embargo, no tenía exactamente en mente un árbol de "millones de entradas".

No confunda mi elección de nombre de nodo ('Nodo 1.1.1') con algo en lo que confiar. Los nodos también podrían llamarse 'Frank' o 'Bob', no implica una estructura de nombres, esto era simplemente para que fuera legible.

He publicado mi propia solución para que ustedes puedan hacerla pedazos.

Tomalak
fuente
2
"no hay objetos elegantes con referencias padre / hijo" - ¿por qué no? Crear un objeto Node básico con .addChild (), el método .getParent () le permite modelar la relación de nodo bastante bien.
mate b
2
¿Es un árbol regular (n hijos donde n puede ser> 2) o un árbol binario (el nodo puede tener 0, 1 o 2 hijos)?
BKimmel
Como puede implementar una estructura de datos de nodo adecuada con un hashmap, aquí no hay una restricción real, solo más trabajo.
Svante
... y eso es exactamente lo que hiciste.
Svante

Respuestas:

451

Ahora que MySQL 8.0 admite consultas recursivas , podemos decir que todas las bases de datos SQL populares admiten consultas recursivas en sintaxis estándar.

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

Probé consultas recursivas en MySQL 8.0 en mi presentación Recursive Query Throwdown en 2017.

A continuación se muestra mi respuesta original de 2008:


Hay varias formas de almacenar datos estructurados en árbol en una base de datos relacional. Lo que muestra en su ejemplo utiliza dos métodos:

  • Lista de adyacencia (la columna "padre") y
  • Enumeración de ruta (los números de puntos en su columna de nombre).

Otra solución se llama Conjuntos anidados , y también se puede almacenar en la misma tabla. Lea " Árboles y jerarquías en SQL para Smarties " de Joe Celko para obtener más información sobre estos diseños.

Por lo general, prefiero un diseño llamado Tabla de cierre (también conocido como "Relación de adyacencia") para almacenar datos estructurados en árbol. Requiere otra tabla, pero luego consultar árboles es bastante fácil.

Cubro la Tabla de cierre en mi presentación Modelos para datos jerárquicos con SQL y PHP y en mi libro Antipatterns de SQL: Evitar las trampas de la programación de bases de datos .

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Almacene todas las rutas en la Tabla de cierre, donde hay una ascendencia directa de un nodo a otro. Incluya una fila para que cada nodo haga referencia a sí mismo. Por ejemplo, usando el conjunto de datos que mostró en su pregunta:

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

Ahora puede obtener un árbol que comienza en el nodo 1 como este:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

El resultado (en el cliente MySQL) tiene el siguiente aspecto:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

En otras palabras, los nodos 3 y 5 están excluidos, porque son parte de una jerarquía separada, que no desciende del nodo 1.


Re: comentario de e-satis sobre hijos inmediatos (o padres inmediatos). Puede agregar una path_lengthcolumna " " a la ClosureTablepara facilitar la consulta específica de un hijo o padre inmediato (o cualquier otra distancia).

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

Luego, puede agregar un término en su búsqueda para consultar los elementos secundarios inmediatos de un nodo determinado. Estos son descendientes cuyo path_lengthes 1.

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

Re comentario de @ashraf: "¿Qué tal si ordenamos todo el árbol [por nombre]?"

Aquí hay una consulta de ejemplo para devolver todos los nodos que son descendientes del nodo 1, unirlos a la FlatTable que contiene otros atributos de nodo como namey ordenarlos por el nombre.

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

Re comentar de @Nate:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

Un usuario sugirió una edición hoy. Los moderadores de SO aprobaron la edición, pero la estoy revocando.

La edición sugirió que ORDER BY en la última consulta anterior debería ser ORDER BY b.path_length, f.name, probablemente para asegurarse de que el orden coincida con la jerarquía. Pero esto no funciona, porque ordenaría "Nodo 1.1.1" después de "Nodo 1.2".

Si desea que el orden coincida con la jerarquía de una manera sensata, es posible, pero no simplemente ordenando por la longitud de la ruta. Por ejemplo, vea mi respuesta a la base de datos jerárquica de MySQL Closure Table: cómo extraer la información en el orden correcto .

Bill Karwin
fuente
66
Esto es muy elegante, gracias. Punto de bonificación otorgado. ;-) Sin embargo, veo un pequeño inconveniente: ya que almacena la relación secundaria explícita e implícitamente, debe realizar una ACTUALIZACIÓN cuidadosa incluso para un pequeño cambio en la estructura de árbol.
Tomalak
16
Es cierto que cada método para almacenar estructuras de árbol en una base de datos requiere algo de trabajo, ya sea al crear o actualizar el árbol, o al consultar árboles y subárboles. Elija el diseño en función del cual le gustaría ser más simple: escribir o leer.
Bill Karwin
2
@buffer, existe la posibilidad de crear inconsistencias a medida que crea todas las filas para una jerarquía. La Lista de adyacencia ( parent_id) solo tiene una fila para expresar cada relación padre-hijo, pero la Tabla de cierre tiene muchas.
Bill Karwin
1
@BillKarwin Una cosa más, son las tablas de cierre adecuadas para un gráfico con múltiples rutas a cualquier nodo dado (por ejemplo, una jerarquía de categorías donde cualquier nodo hoja o no hoja puede pertenecer a más de un padre)
usuario
2
@Reza, de modo que si agrega un nuevo nodo hijo, puede consultar todos los descendientes de (1) y esos son los antepasados ​​del nuevo hijo.
Bill Karwin
58

Si usa conjuntos anidados (a veces denominados Recorrido de árbol de pedido anticipado modificado) puede extraer toda la estructura de árbol o cualquier subárbol dentro de ella en orden de árbol con una sola consulta, a costa de que las inserciones sean más caras, ya que necesita administrar columnas que describen una ruta en orden a través de la estructura de árbol.

Para django-mptt , utilicé una estructura como esta:

id parent_id tree_id nivel lft derecho
- --------- ------- ----- --- ----
 1 nulo 1 0 1 14
 2 1 1 1 2 7
 3 2 1 2 3 4
 4 2 1 2 5 6
 5 1 1 1 8 13
 6 5 1 2 9 10
 7 5 1 2 11 12

Que describe un árbol que se ve así (con la idrepresentación de cada elemento):

 1
 + - 2
 El | + - 3
 El | + - 4
 El |
 + - 5
     + - 6
     + - 7

O, como un diagrama de conjunto anidado que hace más obvio cómo funcionan los valores lfty rght:

 __________________________________________________________________________
El | Raíz 1 |
El | ________________________________ ________________________________ |
El | El | Niño 1.1 | El | Niño 1.2 | El |
El | El | ___________ ___________ | El | ___________ ___________ | El |
El | El | El | C 1.1.1 | El | C 1.1.2 | El | El | El | C 1.2.1 | El | C 1.2.2 | El | El |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
El | | ________________________________ | | ________________________________ | El |
| __________________________________________________________________________ |

Como se puede ver, para obtener todo el subárbol de un nodo dado, con el fin árbol, sólo tiene que seleccionar todas las filas que tienen lfty rghtlos valores entre sus lfty rghtvalores. También es simple recuperar el árbol de antepasados ​​para un nodo dado.

La levelcolumna es un poco de desnormalización por conveniencia más que nada y la tree_idcolumna le permite reiniciar lfty rghtnumerar para cada nodo de nivel superior, lo que reduce el número de columnas afectadas por inserciones, movimientos y eliminaciones, ya que las columnas lfty rghtdeben ser ajustado en consecuencia cuando estas operaciones tienen lugar para crear o cerrar brechas. Tomé algunas notas de desarrollo en el momento en que estaba tratando de entender las consultas requeridas para cada operación.

En términos de trabajar realmente con estos datos para mostrar un árbol, creé una tree_item_iteratorfunción de utilidad que, para cada nodo, debería proporcionarle información suficiente para generar cualquier tipo de visualización que desee.

Más información sobre MPTT:

Jonny Buchanan
fuente
99
Desearía que dejáramos de usar abreviaturas como lfty rghtpara los nombres de columna, quiero decir, ¿cuántos caracteres no tuvimos que escribir? ¡¿uno?!
orustammanapov
21

Es una pregunta bastante antigua, pero como tiene muchas opiniones, creo que vale la pena presentar una alternativa, y en mi opinión, una solución muy elegante.

Para leer una estructura de árbol, puede usar expresiones de tabla comunes (CTE) recursivas. Ofrece la posibilidad de recuperar toda la estructura de árbol a la vez, tener la información sobre el nivel del nodo, su nodo principal y el orden dentro de los hijos del nodo principal.

Déjame mostrarte cómo funcionaría esto en PostgreSQL 9.1.

  1. Crear una estructura

    CREATE TABLE tree (
        id int  NOT NULL,
        name varchar(32)  NOT NULL,
        parent_id int  NULL,
        node_order int  NOT NULL,
        CONSTRAINT tree_pk PRIMARY KEY (id),
        CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
          REFERENCES tree (id) NOT DEFERRABLE
    );
    
    
    insert into tree values
      (0, 'ROOT', NULL, 0),
      (1, 'Node 1', 0, 10),
      (2, 'Node 1.1', 1, 10),
      (3, 'Node 2', 0, 20),
      (4, 'Node 1.1.1', 2, 10),
      (5, 'Node 2.1', 3, 10),
      (6, 'Node 1.2', 1, 20);
  2. Escribir una consulta

    WITH RECURSIVE 
    tree_search (id, name, level, parent_id, node_order) AS (
      SELECT 
        id, 
        name,
        0,
        parent_id, 
        1 
      FROM tree
      WHERE parent_id is NULL
    
      UNION ALL 
      SELECT 
        t.id, 
        t.name,
        ts.level + 1, 
        ts.id, 
        t.node_order 
      FROM tree t, tree_search ts 
      WHERE t.parent_id = ts.id 
    ) 
    SELECT * FROM tree_search 
    WHERE level > 0 
    ORDER BY level, parent_id, node_order;

    Aquí están los resultados:

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)

    Los nodos del árbol están ordenados por un nivel de profundidad. En el resultado final los presentaríamos en las siguientes líneas.

    Para cada nivel, se ordenan por parent_id y node_order dentro del padre. Esto nos dice cómo presentarlos en el nodo de enlace de salida al padre en este orden.

    Con una estructura así, no sería difícil hacer una presentación realmente agradable en HTML.

    Los CTE recursivos están disponibles en PostgreSQL, IBM DB2, MS SQL Server y Oracle .

    Si desea leer más sobre consultas SQL recursivas, puede consultar la documentación de su DBMS favorito o leer mis dos artículos que cubren este tema:

Michał Kołodziejski
fuente
18

A partir de Oracle 9i, puede usar CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

A partir de SQL Server 2005, puede usar una expresión de tabla común recursiva (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Ambos generarán los siguientes resultados.

Nombre
'Nodo 1'
'Nodo 1.1'
'Nodo 1.1.1'
'Nodo 1.2'
'Nodo 2'
'Nodo 2.1'
Eric Weilnau
fuente
cte se puede usar en sqlserver y oracle @Eric Weilnau
Nisar
9

La respuesta de Bill es bastante buena, esta respuesta le agrega algunas cosas que me hacen desear respuestas roscadas tan compatibles.

De todos modos, quería apoyar la estructura de árbol y la propiedad Order. Incluí una sola propiedad en cada Nodo llamado leftSiblingque hace lo mismo que Orderdebe hacer en la pregunta original (mantener el orden de izquierda a derecha).

mysql> nodos desc;
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
El | Campo | Tipo | Nulo | Clave | Predeterminado | Extra |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
El | id | int (11) | NO | PRI | NULL | auto_increment |
El | nombre | varchar (255) | SI | El | NULL | El |
El | leftSibling | int (11) | NO | El | 0 | El |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
3 filas en conjunto (0.00 seg)

mysql> desc adyacencias;
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
El | Campo | Tipo | Nulo | Clave | Predeterminado | Extra |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
El | relacionId | int (11) | NO | PRI | NULL | auto_increment |
El | padre | int (11) | NO | El | NULL | El |
El | niño | int (11) | NO | El | NULL | El |
El | pathLen | int (11) | NO | El | NULL | El |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
4 filas en conjunto (0.00 seg)

Más detalles y código SQL en mi blog .

Gracias Bill, tu respuesta fue útil para comenzar.

bobobobo
fuente
7

Bien dada la opción, estaría usando objetos. childrenCrearía un objeto para cada registro donde cada objeto tiene una colección y los almacenaría en una matriz asociada (/ hashtable) donde el Id es la clave. Y revise la colección una vez, agregando a los niños a los campos de niños relevantes.Simple.

Pero debido a que no estás siendo divertido al restringir el uso de una buena POO, probablemente repetiría en base a:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Editar: esto es similar a un par de otras entradas, pero creo que es un poco más limpio. Una cosa que agregaré: esto es extremadamente intensivo en SQL. Es desagradable . Si tiene la opción, vaya a la ruta OOP.

Oli
fuente
Eso es lo que quise decir con "sin marcos": está utilizando LINQ, ¿no? Con respecto a su primer párrafo: el conjunto de resultados ya está allí, ¿por qué copiar primero toda la información a una nueva estructura de objeto? (No estaba lo suficientemente claro sobre ese hecho, lo siento)
Tomalak
Tomalak: no, el código es seudocódigo. Por supuesto, tendría que dividir las cosas en selecciones e iteradores adecuados ... ¡y una sintaxis real! ¿Por qué OOP? Porque puedes reflejar exactamente la estructura. Mantiene las cosas agradables y resulta ser más eficiente (solo una selección)
Oli
Tampoco tenía en mente selecciones repetidas. Con respecto a la OOP: Mark Bessey dijo en su respuesta: "Puede emular cualquier otra estructura de datos con un hashmap, por lo que no es una limitación terrible". Su solución es correcta, pero creo que hay un margen de mejora incluso sin OOP.
Tomalak
5

Esto fue escrito rápidamente, y no es ni bonito ni eficiente (¡además de autoboxes mucho, convertir entre inty Integeres molesto!), Pero funciona.

Probablemente rompa las reglas ya que estoy creando mis propios objetos, pero bueno, estoy haciendo esto como una distracción del trabajo real :)

Esto también supone que el resultSet / table se lee completamente en algún tipo de estructura antes de comenzar a construir Nodos, lo que no sería la mejor solución si tiene cientos de miles de filas.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}
mate b
fuente
Siempre me resulta difícil filtrar la parte específica del algoritmo de la parte específica de la implementación cuando se me presenta una gran cantidad de código fuente. Es por eso que pedí una solución que no fuera específica del idioma en primer lugar. Pero hace el trabajo, ¡así que gracias por tu tiempo!
Tomalak
Ahora entiendo lo que quieres decir, si no es obvio que el algoritmo principal está en NodeBuilder.build (), probablemente podría haber hecho un mejor trabajo al resumir esto.
mate b
5

Existen soluciones realmente buenas que explotan la representación interna btree de los índices sql. Esto se basa en una gran investigación realizada alrededor de 1998.

Aquí hay una tabla de ejemplo (en mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Los únicos campos necesarios para la representación del árbol son:

  • tw: El índice de pedido anticipado DFS de izquierda a derecha, donde root = 1.
  • pa: La referencia (usando tw) al nodo padre, la raíz tiene un valor nulo.
  • sz: el tamaño de la rama del nodo, incluido él mismo.
  • nc: se usa como azúcar sintáctico. es tw + nc y representa el tw del "próximo hijo" del nodo.

Aquí hay un ejemplo de población de 24 nodos, ordenado por tw:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Cada resultado de árbol se puede hacer de forma no recursiva. Por ejemplo, para obtener una lista de antepasados ​​del nodo en tw = '22 '

Antepasados

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Los hermanos y los niños son triviales, solo use el ordenamiento de campo pa por tw.

Descendientes

Por ejemplo, el conjunto (rama) de nodos que están enraizados en tw = 17.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Notas adicionales

Esta metodología es extremadamente útil para cuando hay un número mucho mayor de lecturas que inserciones o actualizaciones.

Debido a que la inserción, movimiento o actualización de un nodo en el árbol requiere que el árbol se ajuste, es necesario bloquear la tabla antes de comenzar con la acción.

El costo de inserción / eliminación es alto porque los valores de índice tw y sz (tamaño de rama) deberán actualizarse en todos los nodos después del punto de inserción, y para todos los antepasados, respectivamente.

El movimiento de rama implica mover el valor tw de la rama fuera del rango, por lo que también es necesario deshabilitar las restricciones de clave externa al mover una rama. Básicamente, se requieren cuatro consultas para mover una rama:

  • Mueva la rama fuera del rango.
  • Cerrar la brecha que dejó. (el árbol restante ahora está normalizado).
  • Abra el espacio donde irá.
  • Mueva la rama a su nueva posición.

Ajustar consultas de árbol

La apertura / cierre de huecos en el árbol es una subfunción importante utilizada por los métodos crear / actualizar / eliminar, así que la incluyo aquí.

Necesitamos dos parámetros: una bandera que represente si estamos reduciendo o reduciendo el tamaño, y el índice tw del nodo. Entonces, por ejemplo tw = 18 (que tiene un tamaño de rama de 5). Supongamos que estamos reduciendo el tamaño (eliminando tw); esto significa que estamos usando '-' en lugar de '+' en las actualizaciones del siguiente ejemplo.

Primero usamos una función ancestro (ligeramente alterada) para actualizar el valor sz.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Luego, necesitamos ajustar el tw para aquellos cuyo tw es más alto que la rama que se va a eliminar.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Luego, necesitamos ajustar el padre para aquellos cuyo tw de pa es más alto que la rama que se eliminará.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;
Konchog
fuente
3

Suponiendo que sabe que los elementos raíz son cero, aquí está el pseudocódigo para enviar al texto:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)
wcm
fuente
3

Puede emular cualquier otra estructura de datos con un hashmap, por lo que no es una limitación terrible. Al escanear de arriba a abajo, crea un hashmap para cada fila de la base de datos, con una entrada para cada columna. Agregue cada uno de estos hashmaps a un hashmap "maestro", tecleado en la identificación. Si algún nodo tiene un "padre" que aún no ha visto, cree una entrada de marcador de posición para él en el mapa hash maestro y complételo cuando vea el nodo real.

Para imprimirlo, haga un simple pase de profundidad primero a través de los datos, haciendo un seguimiento del nivel de sangría en el camino. Puede hacer esto más fácil manteniendo una entrada "secundaria" para cada fila y rellenándola mientras escanea los datos.

En cuanto a si hay una "mejor" forma de almacenar un árbol en una base de datos, eso depende de cómo va a utilizar los datos. He visto sistemas que tenían una profundidad máxima conocida que usaban una tabla diferente para cada nivel en la jerarquía. Eso tiene mucho sentido si los niveles en el árbol no son del todo equivalentes después de todo (las categorías de nivel superior son diferentes a las hojas).

Mark Bessey
fuente
1

Si se pueden crear mapas o matrices hash anidados, entonces simplemente puedo bajar de la tabla desde el principio y agregar cada elemento a la matriz anidada. Debo rastrear cada línea hasta el nodo raíz para saber en qué nivel de la matriz anidada insertar. Puedo emplear la memorización para no tener que buscar al mismo padre una y otra vez.

Editar: Primero leería toda la tabla en una matriz, por lo que no consultará la base de datos repetidamente. Por supuesto, esto no será práctico si su mesa es muy grande.

Después de construir la estructura, primero debo atravesarla en profundidad e imprimir el HTML.

No hay una mejor manera fundamental de almacenar esta información usando una tabla (aunque podría estar equivocado;), y me encantaría ver una mejor solución). Sin embargo, si crea un esquema para emplear tablas db creadas dinámicamente, entonces abre un mundo completamente nuevo con el sacrificio de la simplicidad y el riesgo del infierno SQL;).

tchen
fuente
1
Prefiero no cambiar el diseño de la base de datos solo porque se necesita un nuevo nivel de subnodos. :-)
Tomalak
1

Si los elementos están en orden de árbol, como se muestra en su ejemplo, puede usar algo como el siguiente ejemplo de Python:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

Lo que esto hace es mantener una pila que representa la posición actual en el árbol. Para cada elemento de la tabla, muestra elementos de la pila (cerrando los divs coincidentes) hasta que encuentra el elemento primario del elemento actual. Luego genera el inicio de ese nodo y lo empuja a la pila.

Si desea generar el árbol utilizando sangría en lugar de elementos anidados, simplemente puede omitir las declaraciones de impresión para imprimir los divs e imprimir un número de espacios igual a algún múltiplo del tamaño de la pila antes de cada elemento. Por ejemplo, en Python:

print "  " * len(stack)

También podría usar fácilmente este método para construir un conjunto de listas anidadas o diccionarios.

Editar: veo por su aclaración que los nombres no estaban destinados a ser rutas de nodo. Eso sugiere un enfoque alternativo:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

Esto construye un árbol de matrices de tuplas (!). idx [0] representa la raíz (s) del árbol. Cada elemento en una matriz es una tupla de 2 que consta del nodo en sí y una lista de todos sus elementos secundarios. Una vez construido, puede conservar idx [0] y descartar idx, a menos que desee acceder a los nodos por su ID.

Nick Johnson
fuente
1

Para ampliar la solución SQL de Bill, básicamente puede hacer lo mismo con una matriz plana. Además, si todas sus cadenas tienen la misma longitud y se conoce su número máximo de hijos (digamos en un árbol binario), puede hacerlo usando una sola cadena (matriz de caracteres). Si tiene un número arbitrario de hijos, esto complica un poco las cosas ... Tendría que revisar mis notas anteriores para ver qué se puede hacer.

Luego, sacrificando un poco de memoria, especialmente si su árbol es escaso y / o no equilibrado, puede, con un poco de matemática de índice, acceder a todas las cadenas de forma aleatoria almacenando su árbol, el ancho primero en la matriz de esta manera (para un binario árbol):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

sabes la longitud de tu cuerda, lo sabes

Ahora estoy en el trabajo, así que no puedo pasar mucho tiempo en ello, pero con interés puedo obtener un poco de código para hacer esto.

Solíamos hacerlo para buscar en árboles binarios hechos de codones de ADN, un proceso construyó el árbol, luego lo aplanamos para buscar patrones de texto y cuando lo encontramos, aunque el índice matemático (al revés desde arriba) recuperamos el nodo ... muy rápido y eficiente, resistente, nuestro árbol rara vez tenía nodos vacíos, pero podíamos buscar gigabytes de datos en un santiamén.

Newtopian
fuente
0

Piense en usar herramientas nosql como neo4j para estructuras jerárquicas. por ejemplo, una aplicación en red como linkedin usa couchbase (otra solución nosql)

Pero use nosql solo para consultas de nivel de data-mart y no para almacenar / mantener transacciones

sreenivasulu kandakuru
fuente
Después de leer sobre las complejidades y el rendimiento de SQL y las estructuras "no de tabla", este fue mi primer pensamiento también, nosql. Por supuesto, hay muchos problemas para exportar, etc. Además, el OP solo menciona tablas. Oh bien. No soy un experto en DB, como es obvio.
Josef.B