¿Cuáles son las formas conocidas de almacenar una estructura de árbol en una base de datos relacional?

Existe el método “poner un FK a su padre” , es decir, cada uno registra puntos a su padre.
Que es una acción difícil de leer, pero muy fácil de mantener.

Y luego hay un método de “clave de estructura de directorio”:

0001.0000.0000.0000 main branch 1 0001.0001.0000.0000 child of main branch one etc 

Que es súper fácil de leer, pero difícil de mantener.
¿Cuáles son las otras formas y sus contras / pros?

Como siempre: no hay una mejor solución. Cada solución hace diferentes cosas más fáciles o más difíciles. La solución adecuada para usted depende de qué operación hará más.

Enfoque ingenuo con ID de padres:

Pros:

  • fácil de implementar

  • fácil de mover un subárbol grande a otro padre

  • insertar es barato

  • Campos necesarios directamente accesibles en SQL

Contras:

  • recuperar un árbol completo es recursivo y, por lo tanto, costoso

  • encontrar todos los padres también es caro (SQL no sabe recursiones …)

Trayectoria modificada del árbol de preorden (guardando un punto inicial y final):

Pros:

  • Recuperar un árbol completo es fácil y barato

  • Encontrar a todos los padres es barato

  • Campos necesarios directamente accesibles en SQL

  • Bonificación: también estás guardando el orden de los nodos secundarios dentro de su nodo principal

Contras:

  • Insertar / actualizar puede ser muy costoso, ya que tal vez tenga que actualizar muchos nodos

Guardando un camino en cada Nodo:

Pros:

  • Encontrar a todos los padres es barato

  • Recuperar un árbol entero es barato

  • Insertar es barato

Contras:

  • Mover un árbol entero es costoso

  • Dependiendo de la forma en que guarde la ruta, no podrá trabajar con ella directamente en SQL, por lo que siempre tendrá que buscarla y analizarla, si desea cambiarla.

Preferiría uno de los dos últimos, según la frecuencia con la que cambien los datos.

Ver también: http://media.pragprog.com/titles/bksqla/trees.pdf

Trayectoria modificada del árbol preordenador

Este es un método que utiliza una función no recursiva (generalmente una sola línea de SQL) para recuperar árboles de la base de datos, a costa de ser un poco más complicado de actualizar.

Diagrama que muestra el árbol jerárquico numerado **

Sección 2 del artículo de Sitepoint Almacenamiento de datos jerárquicos en una base de datos para más detalles.

Yo diría que la “mejor manera” de almacenar una estructura de datos jerárquica es usar una base de datos jerárquica. Como, por ejemplo, HDB. Esa es una base de datos relacional que maneja los árboles bastante bien. Si quieres algo más poderoso, LDAP podría hacer por ti.

Una base de datos SQL no es adecuada para esta topología abstracta.

No creo que sea difícil construir una estructura de árbol con una base de datos relacional.

Sin embargo, una base de datos orientada a objetos funcionaría mucho mejor para este propósito.

Usando una base de datos orientada a objetos:

 parent has a set of child1 child1 has a set of child2 child2 has a set of child3 ... ... 

En una base de datos orientada a objetos puede construir esta estructura con bastante facilidad.

En una base de datos relacional, deberá mantener las claves externas para el padre.

 parent id name child1 parent_fk id name child2 parent_fk id name .. 

Esencialmente, mientras construyes la estructura de tu árbol, deberás unir todas estas tablas, o puedes iterar a través de ellas.

 foreach(parent in parents){ foreach(child1 in parent.child1s) foreach(child2 in child1.child2s) ...