Boas visões gerais

De um modo geral, você está tomando uma decisão entre tempos de leitura rápidos (por exemplo, conjunto aninhado) ou tempos de gravação rápidos (lista de adjacências). Normalmente, você acaba combinando as opções abaixo que melhor atendem às suas necessidades. A seguir, é apresentada uma leitura aprofundada:

Mais uma comparação de intervalos aninhados vs. lista de adjacências: a melhor comparação da lista de adjacências, caminho materializado, conjunto aninhado e intervalo aninhado que encontrei.Modelos para dados hierárquicos: slides com boas explicações sobre tradeoffs e exemplos de usoRepresentando hierarquias no MySQL: muito boa visão geral do conjunto aninhadoDados hierárquicos em RDBMSs: conjunto de links mais abrangente e bem organizado que eu já vi, mas não muito na explicação

Opções

Conheço e tenho características gerais:

Lista de adjacências:Colunas: ID, ParentIDFácil de implementar.O nó barato move, insere e exclui.Caro para encontrar o nível, ascendência e descendentes, caminhoEvite N + 1 viaExpressões de tabela comuns em bancos de dados que os suportamConjunto aninhado (também conhecido comoÁrvore modificada de pedido antecipado)Colunas: Esquerda, DireitaAscendência barata, descendentesMuito caroO(n/2) move, insere, exclui devido a codificação volátilBridge Table (a.k.a.Tabela de fechamento / w gatilhos)Usa tabela de junção separada com: ancestral, descendente, profundidade (opcional)Ascendência e descendentes baratosEscreve custosO(log n) (tamanho da subárvore) para inserção, atualizações e exclusõesCodificação normalizada: boa para estatísticas RDBMS e planejador de consultas em junçõesRequer várias linhas por nóColuna de linhagem (a.k.a.Caminho materializado, Enumeração de caminhos)Coluna: linhagem (por exemplo, / pai / filho / neto / etc ...)Descendentes baratos por meio de consulta de prefixo (por exemplo,LEFT(lineage, #) = '/enumerated/path')Escreve custosO(log n) (tamanho da subárvore) para inserção, atualizações e exclusõesNão relacional: depende do tipo de dados Array ou formato de seqüência de caracteres serializadaIntervalos aninhadosComo o conjunto aninhado, mas com real / float / decimal para que a codificação não seja volátil (movimentação / inserção / exclusão de baixo custo)Tem problemas reais / de flutuação / representação decimal / precisãoVariante de codificação de matriz adiciona codificação ancestral (caminho materializado) para "livre", mas com mais dificuldade de álgebra linear.Mesa planaUma lista de adjacências modificada que adiciona uma coluna de nível e classificação (por exemplo, pedido) a cada registro.Barato para iterar / paginarMovimentação e exclusão carasBom uso: discussão por tópicos - fóruns / comentários do blogVárias colunas de linhagemColunas: uma para cada nível de linhagem, refere-se a todos os pais até a raiz, os níveis inferiores ao nível do item são definidos como NULLAncestrais baratos, descendentes, nívelInserção barata, excluir, mover das folhasInserção cara, exclusão, movimentação dos nós internosLimite rígido para a profundidade da hierarquia

Notas específicas do banco de dados

MySQL

Use variáveis de sessão para a lista de adjacências

Oráculo

UsarCONECTE POR percorrer Listas de Adjacência

PostgreSQL

tipo de dados ltree para caminho materializado

servidor SQL

Resumo geral2008 ofertasHierarchyId o tipo de dados parece ajudar na abordagem da coluna Lineage e expandir a profundidade que pode ser representada.