¿Qué son los modelos para almacenar estructuras de árboles y cuáles son sus características?

Question

Hasta ahora he encontrado listas de adyacencia, conjuntos anidados e intervalos anidados como modelos para almacenar estructuras de árbol en una base de datos.Los conozco bastante bien y he migrado árboles de uno a otro.

¿Cuáles son otros modelos populares?¿Cuáles son sus características?¿Cuáles son buenos recursos (libros, web, etc.) sobre este tema?

No solo busco almacenamiento de bases de datos, sino que me gustaría ampliar mis conocimientos sobre árboles en general.Por ejemplo, entiendo que los conjuntos/intervalos anidados son especialmente favorables para el almacenamiento de bases de datos relacionales y me he preguntado: ¿son realmente un malo elección en otros contextos?

Answer 1

El recurso fundamental para esto son los capítulos 28-30 de SQL para sabelotodos.

(¡He recomendado tanto este libro que creo que Celko ya me debe regalías!)

Answer 2

Una variación es cuando se utiliza una representación jerárquica directa (es decir,enlace principal en el nodo), pero también almacena un valor de ruta.

es decir.para un árbol de directorios que consta de lo siguiente:

C:\
   Temp
   Windows
       System32

Tendrías los siguientes nodos

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

La ruta está indexada y le permitirá realizar rápidamente una consulta que seleccione un nodo y todos sus hijos, sin tener que manipular rangos.

es decir.para encontrar C: emp y todos sus hijos:

WHERE Path LIKE '*1*2*%'

Esta representación es el único lugar que se me ocurre donde almacenar identificaciones en una cadena como esta está bien.

Answer 3

@lassevk: Este artículo habla sobre su enfoque con más detalle y proporciona fragmentos de código.

Espero que esto ayude.