O que são modelos de armazenamento de estruturas de árvores e quais são suas características?

Question

Até agora encontrei listas de adjacências, conjuntos aninhados e intervalos aninhados como modelos para armazenar estruturas de árvore em um banco de dados.Eu os conheço bem e migrei árvores de uma para outra.

Quais são outros modelos populares?Quais são suas características?Quais são os bons recursos (livros, web, etc.) sobre este assunto?

Não estou apenas procurando armazenamento de banco de dados, mas gostaria de expandir meu conhecimento sobre árvores em geral.Por exemplo, eu entendo que conjuntos/intervalos aninhados são especialmente favoráveis ​​para armazenamento de banco de dados relacional e me perguntei se eles são realmente um ruim escolha em outros contextos?

Answer 1

O recurso seminal para isso são os capítulos 28-30 do SQL para espertos.

(Recomendei tanto este livro que acho que Celko já me deve royalties!)

Answer 2

Uma variação é onde você usa uma representação hierárquica direta (ou seja,link pai no nó), mas também armazena um valor de caminho.

ou seja.para uma árvore de diretórios que consiste no seguinte:

C:\
   Temp
   Windows
       System32

Você teria os seguintes nós

Key     Name     Parent     Path
1       C:                  *1*
2       Temp       1        *1*2*
3       Windows    1        *1*3*
4       System32   3        *1*3*4*

O caminho é indexado e permitirá que você faça rapidamente uma consulta que selecione um nó e todos os seus filhos, sem precisar manipular intervalos.

ou seja.para encontrar C: emp e todos os seus filhos:

WHERE Path LIKE '*1*2*%'

Esta representação é o único lugar em que consigo pensar onde armazenar identificação em uma string como esta está ok.

Answer 3

@lassevk: Este artigo fala sobre sua abordagem com mais detalhes e fornece trechos de código.

Espero que isto ajude.