Es más fácil de explicar con ejemplos que con unas pocas palabras. Considere el árbol de muestra, almacenando nombres:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Camino Materializado significa que cada nodo almacena su ruta completa codificada. Por ejemplo, puede almacenar su índice utilizando un punto como separador de
Name Path
William 1
Jones 1.1
Blake 1.2
Adams 1.2.1
Tyler 1.3
Joseph 2
Miller 2.1
Flint 2.2
Así, Adams sabe su nombre completo es William Blake Adams, ya que tiene la ruta 1.2.1, que apunta al nodo 1 en el primer nivel - William - al nodo 1.2 en el nivel 2 - Blake - y al nodo 1.2.1 en el nivel 3 - Adams.
Lista de adyacencia significa que el árbol se almacena manteniendo un enlace a algunos nodos adyacentes. Por ejemplo, puede almacenar quién es el padre y quién es el próximo hermano.
Name Parent Next
William null Joseph
Jones William Blake
Blake William Tyler
Adams Blake null
Tyler William null
Joseph null null
Miller Joseph Flint
Flint Joseph null
en cuenta que podría ser tan simple como el almacenamiento de los padres, si es que no necesitamos para mantener a los hijos de un nodo ordenada. Ahora Adams puede obtener todos sus antepasados recursivamente hasta que sea nulo para encontrar su nombre completo.
Conjuntos anidados significa que almacena cada nodo con algún índice, generalmente un valor izquierdo y derecho, asignado a cada uno mientras recorre el árbol en orden DFS, para que sepa que sus descendientes están dentro de esos valores. He aquí cómo se asignan los números para el ejemplo del árbol:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
y sería almacenada como:
Name left right
William 1 10
Jones 2 3
Blake 4 7
Adams 5 6
Tyler 8 9
Joseph 11 16
Miller 12 13
Flint 14 15
lo tanto, ahora Adams puede encontrar sus antepasados por la consulta que tiene una parte inferior izquierda y una valor más alto a la derecha, y ordenarlos por el valor de la izquierda.
Cada modelo tiene sus fortalezas y debilidades. Elegir cuál usar realmente depende de su aplicación, la base de datos que está usando y qué tipo de operaciones hará con más frecuencia. Puede encontrar una buena comparación here.
La comparación menciona un cuarto modelo que no es muy común (no conozco ninguna otra implementación más que la mía) y muy complicado de explicar en pocas palabras: Intervalo anidado a través de Matrix Encoding.
Cuando inserta un nuevo nodo en un conjunto anidado, debe volver a enumerar a todos los que se encuentren por delante en el cruce. La idea detrás de los intervalos anidados es que hay un número infinito de números racionales entre dos enteros, por lo que podría almacenar el nuevo nodo como una fracción de sus nodos anterior y siguiente.Almacenar y consultar fracciones puede ser problemático, y esto lleva a la técnica de codificación de la matriz, que transforma esas fracciones en una matriz de 2x2 y la mayoría de las operaciones se pueden realizar con álgebra matricial que no es obvia a primera vista pero puede ser muy eficiente.
Treebeard tiene implementaciones muy sencillas de cada una de las rutas materializadas, conjuntos anidados y listas de adyacencia, sin redundancia. django-mptt en realidad usa una combinación de Conjuntos anidados y Listas de adyacencia, ya que también mantiene un enlace con el padre y puede usarlo para consultar a los niños de manera más eficiente y para reconstruir el árbol en caso de que lo arruine alguien.