Qual é a maneira mais eficiente / elegante de analisar uma mesa plana em uma árvore?

Suponha que você tenha uma tabela plana que armazene uma hierarquia de árvore 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

Aqui está um diagrama, onde temos [id] Name. O nó raiz 0 é fictício.

                       [0] RAIZ
                          / \ 
              [1] Nó 1 [3] Nó 2
              / \ \
    [2] Nó 1,1 [6] Nó 1,2 [5] Nó 2,1
          /          
 [4] Nó 1.1.1.

Que abordagem minimalista você usaria para produzir isso em HTML (ou texto, por sinal) como uma árvore recortada e ordenada corretamente?

Suponha ainda que você tenha apenas estruturas básicas de dados (matrizes e hashmaps), sem objetos sofisticados com referências de pai / filho, sem ORM, sem estrutura, apenas com as duas mãos. A tabela é representada como um conjunto de resultados, que pode ser acessado aleatoriamente.

Pseudo-código ou inglês comum é bom, essa é uma questão puramente conceitual.

Pergunta de bônus: Existe uma maneira fundamentalmente melhor de armazenar uma estrutura de árvore como esta em um RDBMS?

EDITAS E ADIÇÕES

Para responder à pergunta de um comentarista ( Mark Bessey ): Um nó raiz não é necessário, porque nunca será exibido de qualquer maneira. ParentId = 0 é a convenção para expressar "estes são de nível superior". A coluna Ordem define como os nós com o mesmo pai serão classificados.

O "conjunto de resultados" de que falei pode ser representado como uma matriz de hashmaps (para permanecer nessa terminologia). Para o meu exemplo era para já estar lá. Algumas respostas vão além e constroem primeiro, mas tudo bem.

A árvore pode ser arbitrariamente profunda. Cada nó pode ter N filhos. Eu não tinha exatamente uma árvore "milhões de entradas" em mente.

Não confunda minha escolha de nomeação de nó ('Nó 1.1.1') com algo em que confiar. Os nós poderiam igualmente ser chamados de 'Frank' ou 'Bob', nenhuma estrutura de nomenclatura está implícita, isso era apenas para torná-la legível.

Eu publiquei minha própria solução para que vocês possam fazer isso em pedaços.

Agora que o MySQL 8.0 suporta consultas recursivas , podemos dizer que todos os bancos de dados SQL populares suportam consultas recursivas na sintaxe padrão.

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;

Testei consultas recursivas no MySQL 8.0 na minha apresentação Recursive Query Throwdown em 2017.

Abaixo está a minha resposta original de 2008:

Existem várias maneiras de armazenar dados estruturados em árvore em um banco de dados relacional. O que você mostra no seu exemplo usa dois métodos:

• Lista de adjacências (a coluna "principal") e
• Enumeração de caminho (os números pontilhados na coluna do seu nome).

Outra solução é chamada Conjuntos Aninhados e também pode ser armazenada na mesma tabela. Leia " Árvores e hierarquias no SQL for Smarties ", de Joe Celko, para obter mais informações sobre esses designs.

Normalmente, eu prefiro um design chamado Closure Table (também conhecido como "Adjacency Relation") para armazenar dados estruturados em árvore. Requer outra tabela, mas é fácil consultar árvores.

Abordo a tabela de fechamento em minha apresentação Modelos para dados hierárquicos com SQL e PHP e em meu livro Antipatterns SQL: Evitando as armadilhas da programação de banco de dados .

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

Armazene todos os caminhos na tabela de fechamento, onde há uma ascendência direta de um nó para outro. Inclua uma linha para cada nó para fazer referência a si próprio. Por exemplo, usando o conjunto de dados que você mostrou na sua pergunta:

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

Agora você pode obter uma árvore começando no nó 1 como este:

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

A saída (no cliente MySQL) é semelhante à seguinte:

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

Em outras palavras, os nós 3 e 5 são excluídos porque fazem parte de uma hierarquia separada, não descendo do nó 1.

Re: comentário de e-satis sobre filhos imediatos (ou pais imediatos). Você pode adicionar uma path_lengthcoluna ao " " para ClosureTablefacilitar a consulta específica de um filho ou pai imediato (ou qualquer outra distância).

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

Em seguida, você pode adicionar um termo na sua pesquisa para consultar os filhos imediatos de um determinado nó. Estes são descendentes cujo path_lengthé 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 | 
+----+

Comentário de @ashraf: "Que tal classificar a árvore inteira [por nome]?"

Aqui está um exemplo de consulta para retornar todos os nós descendentes do nó 1, associá-los à FlatTable que contém outros atributos do nó, como name, e classificar pelo nome.

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         |
+------------+-------------+

Um usuário sugeriu uma edição hoje. Os moderadores da SO aprovaram a edição, mas estou revertendo.

A edição sugeriu que ORDER BY na última consulta acima deveria ser ORDER BY b.path_length, f.name, presumivelmente para garantir que a ordem corresponda à hierarquia. Mas isso não funciona, porque ordenaria "Nó 1.1.1" após "Nó 1.2".

Se você deseja que a ordem corresponda à hierarquia de maneira sensata, isso é possível, mas não simplesmente ordenando pelo comprimento do caminho. Por exemplo, veja minha resposta ao banco de dados hierárquico da Tabela de fechamento do MySQL - Como extrair informações na ordem correta .

Se você usar conjuntos aninhados (às vezes chamados de Traversal de Árvore de Pré-encomenda Modificado), poderá extrair toda a estrutura de árvore ou qualquer subárvore dentro dela em ordem de árvore com uma única consulta, com o custo de inserções mais caras, conforme necessário. gerenciar colunas que descrevem um caminho em ordem através da estrutura da árvore.

Para django-mptt , usei uma estrutura como esta:

id parent_id nível tree_id lft rght
- --------- ------- ----- --- ----
 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 descreve uma árvore que se parece com isso (com a idrepresentação de cada item):

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

Ou, como um diagrama de conjuntos aninhados, que torna mais óbvio como os valores lfte rghtfuncionam:

 __________________________________________________________________________
| Raiz 1 |
| ________________________________ ________________________________ |
| | Criança 1.1 | | Criança 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | C 1.1.2 | | | C 1.2.1 | C 1.2.2 | |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
| | ________________________________ | | ________________________________ | |
| __________________________________________________________________________ |

Como você pode ver, para obter toda a subárvore para um determinado nó, na ordem de árvore, você simplesmente tem que selecionar todas as linhas que têm lfte rghtvalores entre os seus lfte rghtvalores. Também é simples recuperar a árvore dos antepassados ​​para um determinado nó.

A levelcoluna é um pouco de desnormalização por conveniência, mais do que tudo, e tree_idpermite que você reinicie a numeração lfte rghtcada nó de nível superior, o que reduz o número de colunas afetadas por inserções, movimentos e exclusões, pois as colunas lfte rghtdevem ser ajustado de acordo quando essas operações ocorrem, a fim de criar ou fechar lacunas. Fiz algumas anotações de desenvolvimento no momento em que estava tentando entender as consultas necessárias para cada operação.

Em termos de realmente trabalhar com esses dados para exibir uma árvore, criei uma tree_item_iteratorfunção de utilitário que, para cada nó, deveria fornecer informações suficientes para gerar o tipo de exibição desejado.

Mais informações sobre MPTT:

• Árvores no SQL
• Armazenando dados hierárquicos em um banco de dados
• Gerenciando dados hierárquicos no MySQL

É uma pergunta bastante antiga, mas, como tem muitas visões, acho que vale a pena apresentar uma alternativa e, na minha opinião, uma solução muito elegante.

Para ler uma estrutura em árvore, você pode usar CTEs (Common Table Expressions ) recursivas . Ele oferece a possibilidade de buscar toda a estrutura da árvore de uma só vez, ter informações sobre o nível do nó, seu nó pai e a ordem dentro dos filhos do nó pai.

Deixe-me mostrar como isso funcionaria no PostgreSQL 9.1.

1. Crie uma estrutura

   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. Escreva uma 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;

   Aqui estão os 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)

   Os nós da árvore são ordenados por um nível de profundidade. No resultado final, apresentá-los-emos nas linhas subseqüentes.

   Para cada nível, eles são ordenados por parent_id e node_order no pai. Isso nos diz como apresentá-los no nó do link de saída ao pai nesta ordem.

   Tendo essa estrutura, não seria difícil fazer uma apresentação muito boa em HTML.

   CTEs recursivos estão disponíveis no PostgreSQL, IBM DB2, MS SQL Server e Oracle .

   Se você quiser ler mais sobre consultas SQL recursivas, verifique a documentação do seu DBMS favorito ou leia meus dois artigos que abordam este tópico:

   • Faça isso no SQL: Traversal de árvore recursiva
   • Conheça o poder das consultas recursivas SQL

No Oracle 9i, você pode 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)

No SQL Server 2005, você pode usar uma expressão de tabela comum 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 produzirão os seguintes resultados.

Nome
'Nó 1'
'Nó 1.1'
'Nó 1.1.1'
'Nó 1.2'
'Nó 2'
'Nó 2.1'

A resposta de Bill é muito boa, essa resposta adiciona algumas coisas que me fazem desejar respostas encadeadas com suporte.

Enfim, eu queria apoiar a estrutura em árvore e a propriedade Order. Incluí uma única propriedade em cada Nó chamado leftSiblingque faz o mesmo Orderna pergunta original (manter a ordem da esquerda para a direita).

nós mysql> desc;
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| Campo Tipo | Nulo Chave Padrão | Extra |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| id | int (11) | NÃO PRI NULL auto_increment |
| nome | varchar (255) | Sim | NULL |
| leftSibling | int (11) | NÃO | 0 |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
3 linhas em conjunto (0,00 s)

mysql> desc adjacências;
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| Campo Tipo | Nulo Chave Padrão | Extra |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| relação | int (11) | NÃO PRI NULL auto_increment |
| pai | int (11) | NÃO | NULL |
| criança int (11) | NÃO | NULL |
| pathLen | int (11) | NÃO | NULL |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
4 linhas em conjunto (0,00 s)

Mais detalhes e código SQL no meu blog .

Obrigado Bill, sua resposta foi útil para começar!

Bem, dada a escolha, eu estaria usando objetos. Eu criaria um objeto para cada registro em que cada objeto tem uma childrencoleção e os armazenaria todos em uma matriz assoc (/ hashtable) em que o ID é a chave. E percorra a coleção uma vez, adicionando os filhos aos campos filhos relevantes. Simples.

Mas como você não está se divertindo ao restringir o uso de uma boa OOP, eu provavelmente iteraria com base em:

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

PrintLine(0, 0)

Edit: isso é semelhante a algumas outras entradas, mas acho que é um pouco mais limpo. Uma coisa que vou acrescentar: isso é extremamente intensivo em SQL. É desagradável . Se você tiver escolha, siga a rota OOP.

Isso foi escrito rapidamente, e não é bonito nem eficiente (além disso, ele autoboxe muito, convertendo entre inte Integeré chato!), Mas funciona.

Provavelmente quebra as regras, já que estou criando meus próprios objetos, mas ei, estou fazendo isso como uma diversão do trabalho real :)

Isso também pressupõe que o resultSet / table seja completamente lido em algum tipo de estrutura antes de você começar a construir Nós, o que não seria a melhor solução se você tivesse centenas de milhares de linhas.

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

Existem realmente boas soluções que exploram a representação btree interna dos índices sql. Isso se baseia em algumas ótimas pesquisas feitas por volta de 1998.

Aqui está uma tabela de exemplo (no 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
)

Os únicos campos necessários para a representação em árvore são:

• tw: O índice de pré-encomenda do DFS da esquerda para a direita, em que root = 1.
• pa: A referência (usando tw) ao nó pai, raiz tem nulo.
• sz: o tamanho da ramificação do nó, incluindo ele próprio.
• nc: é usado como açúcar sintático. é tw + nc e representa o tw do "próximo filho" do nó.

Aqui está um exemplo de população de 24 nós, ordenada 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 |
+-----+---------+----+------+------+------+

Todo resultado da árvore pode ser feito de forma não recursiva. Por exemplo, para obter uma lista de ancestrais do nó em tw = '22 '

Antepassados

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 |
+-----+---------+----+------+------+------+

Irmãos e filhos são triviais - basta usar a ordenação do campo pa por dois.

Descendentes

Por exemplo, o conjunto (ramificação) de nós com raiz em 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 Adicionais

Essa metodologia é extremamente útil para quando há um número muito maior de leituras do que inserções ou atualizações.

Como a inserção, movimento ou atualização de um nó na árvore requer que a árvore seja ajustada, é necessário bloquear a tabela antes de iniciar a ação.

O custo de inserção / exclusão é alto porque os valores de índice tw e sz (tamanho da ramificação) precisam ser atualizados em todos os nós após o ponto de inserção e para todos os ancestrais, respectivamente.

A movimentação de ramificação envolve mover o valor tw da ramificação para fora do intervalo, portanto, também é necessário desativar as restrições de chave estrangeira ao mover uma ramificação. Existem basicamente quatro consultas necessárias para mover uma ramificação:

• Mova a ramificação para fora do alcance.
• Feche o espaço que ele deixou. (a árvore restante agora está normalizada).
• Abra a lacuna para onde ela irá.
• Mova o ramo para sua nova posição.

Ajustar consultas em árvore

A abertura / fechamento de lacunas na árvore é uma subfunção importante usada pelos métodos de criação / atualização / exclusão, por isso a incluo aqui.

Precisamos de dois parâmetros - um sinalizador representando se estamos diminuindo ou diminuindo o tamanho e o índice tw do nó. Portanto, por exemplo tw = 18 (que tem um tamanho de ramificação de 5). Vamos supor que estamos reduzindo o tamanho (removendo tw) - isso significa que estamos usando '-' em vez de '+' nas atualizações do exemplo a seguir.

Primeiro usamos uma função ancestral (ligeiramente alterada) para atualizar o 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));

Então precisamos ajustar o tw para aqueles cujo tw é maior que o ramo a ser removido.

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;

Em seguida, precisamos ajustar o pai para aqueles cujo tw do pa é maior que o ramo a ser removido.

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;

Supondo que você saiba que os elementos raiz são zero, eis o pseudocódigo para saída em 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)

Você pode emular qualquer outra estrutura de dados com um hashmap, para que essa não seja uma limitação terrível. Digitalizando de cima para baixo, você cria um mapa de hash para cada linha do banco de dados, com uma entrada para cada coluna. Adicione cada um desses hashmaps a um hashmap "mestre", digitado no ID. Se algum nó tiver um "pai" que você ainda não viu, crie uma entrada de espaço reservado para ele no hashmap mestre e preencha-o quando vir o nó real.

Para imprimi-lo, faça uma simples passagem pela profundidade dos dados, acompanhando o nível do recuo ao longo do caminho. Você pode facilitar isso mantendo uma entrada "filhos" para cada linha e preenchendo-a à medida que você verifica os dados.

Quanto à existência de uma maneira "melhor" de armazenar uma árvore em um banco de dados, isso depende de como você usará os dados. Vi sistemas que possuíam uma profundidade máxima conhecida que usava uma tabela diferente para cada nível na hierarquia. Isso faz muito sentido se os níveis na árvore não forem muito equivalentes, afinal (as categorias de nível superior são diferentes das folhas).

Se mapas de hash ou matrizes aninhados puderem ser criados, eu posso simplesmente descer a tabela desde o início e adicionar cada item à matriz aninhada. Devo rastrear cada linha para o nó raiz para saber em que nível da matriz aninhada inserir. Posso empregar memorização para não precisar procurar o mesmo pai repetidamente.

Editar: eu leria a tabela inteira em uma matriz primeiro, para que não consultasse o banco de dados repetidamente. Claro que isso não será prático se sua mesa for muito grande.

Depois que a estrutura é construída, preciso fazer uma profunda profundidade através dela e imprimir o HTML.

Não há melhor maneira fundamental de armazenar essas informações usando uma tabela (embora eu possa estar errado;) e adoraria ver uma solução melhor. No entanto, se você criar um esquema para empregar tabelas db criadas dinamicamente, abrirá um mundo totalmente novo com o sacrifício da simplicidade e o risco do inferno do SQL;).

Se os elementos estiverem em ordem de árvore, como mostrado no seu exemplo, você pode usar algo como o seguinte exemplo 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)

O que isso faz é manter uma pilha representando a posição atual na árvore. Para cada elemento da tabela, ele exibe os elementos da pilha (fechando as divs correspondentes) até encontrar o pai do item atual. Em seguida, ele gera o início desse nó e o envia para a pilha.

Se você deseja gerar a árvore usando recuos, em vez de elementos aninhados, basta pular as instruções print para imprimir as divs e imprimir um número de espaços iguais a alguns múltiplos do tamanho da pilha antes de cada item. Por exemplo, em Python:

print "  " * len(stack)

Você também pode usar esse método facilmente para construir um conjunto de listas ou dicionários aninhados.

Edit: Vejo pelo seu esclarecimento que os nomes não pretendiam ser caminhos de nós. Isso sugere uma abordagem alternativa:

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

Isso constrói uma árvore de matrizes de tuplas (!). idx [0] representa a (s) raiz (s) da árvore. Cada elemento de uma matriz é uma tupla de 2 tuplas, que consiste no próprio nó e em uma lista de todos os seus filhos. Uma vez construído, você pode manter o idx [0] e descartar o idx, a menos que queira acessar os nós por seu ID.

Para estender a solução SQL de Bill, você pode basicamente fazer o mesmo usando uma matriz plana. Além disso, se todas as suas strings tiverem o mesmo comprimento e seu número máximo de filhos for conhecido (digamos em uma árvore binária), você poderá fazer isso usando uma única string (matriz de caracteres). Se você tem um número arbitrário de filhos, isso complica um pouco as coisas ... eu precisaria verificar minhas anotações antigas para ver o que pode ser feito.

Então, sacrificando um pouco de memória, especialmente se sua árvore for escassa e / ou desequilibrada, você pode, com um pouco de matemática de índice, acessar todas as seqüências aleatoriamente armazenando sua árvore, largura primeiro na matriz da seguinte maneira (para um binário árvore):

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

você sabe o comprimento da corda, você sabe

Estou no trabalho agora, então não posso gastar muito tempo nisso, mas com interesse posso buscar um pouco de código para fazer isso.

Costumávamos fazer isso para pesquisar em árvores binárias feitas de códons de DNA, um processo construiu a árvore, depois a aplainamos para pesquisar padrões de texto e, quando encontrados, embora a matemática do índice (inversão de cima) recupere o nó ... muito rápido e eficiente, resistente, nossa árvore raramente tinha nós vazios, mas poderíamos coletar gigabytes de dados em um instante.

Pense em usar ferramentas nosql como neo4j para estruturas hierárquicas. por exemplo, um aplicativo em rede como o linkedin usa couchbase (outra solução nosql)

Mas use o nosql apenas para consultas no nível do data mart e não para armazenar / manter transações