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

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.

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 .

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:

• Árboles en SQL
• Almacenar datos jerárquicos en una base de datos
• Administrar datos jerárquicos en MySQL

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:

   • Hágalo en SQL: transversal del árbol recursivo
   • Conozca el poder de las consultas recursivas de SQL

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'

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.

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.

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;
    }
}

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;

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)

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).

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;).

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.

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.

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