fields - django forms widgets

Django treebeard cuáles son las diferencias entre AL, NS, MP

Question

Estoy tratando de hacer un modelo para categorizar algunos objetos.

Ya intenté usar django-mptt para recuperar fácilmente categorías relacionadas, y ahora estoy buscando diferentes soluciones para encontrar la mejor.

No puedo descubrir cuáles son las principales diferencias entre la ruta materializada, la lista de adyacencia y el conjunto anidado. Wikipedia no me dio una respuesta breve, todo lo que sé es que mptt es probablemente un conjunto anidado ...

¿Puede alguien explicármelo en pocas palabras?

Answer 1

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

Ruta materializada significa que cada nodo almacena su ruta completa codificada. Por ejemplo, puede almacenar su índice usando un punto como delimitador

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

Entonces, Adams sabe que su nombre completo es Wiliam Blake Adams, porque 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 el 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

Tenga en cuenta que podría ser tan simple como simplemente almacenar el padre, si no necesitamos mantener ordenados los hijos de un nodo. Ahora Adams puede obtener todos sus antepasados ​​de forma recursiva hasta que sea nulo para encontrar su nombre completo.

Los conjuntos anidados significan que almacena cada nodo con algún índice, generalmente un valor izquierdo y derecho, asignado a cada uno a medida que atraviesa el árbol en el orden DFS, para que sepa que sus descendientes están dentro de esos valores. Así es como los números se asignarían al árbol de ejemplo:

 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 se almacenaría 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

Entonces, ahora Adams puede encontrar a sus antepasados ​​preguntando quién tiene un valor inferior izquierdo Y superior derecho, y ordenarlos por el valor izquierdo.

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 realizará con más frecuencia. Puedes 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 que no sea la mía) y es muy complicado de explicar en pocas palabras: Intervalo anidado a través de codificación de matriz.

Cuando inserta un nuevo nodo en un conjunto anidado, tiene que volver a enumerar a todos los que están delante de él en el recorrido. La idea detrás de los intervalos anidados es que hay un número infinito de números racionales entre dos enteros cualquiera, por lo que podría almacenar el nuevo nodo como una fracción de sus nodos anteriores y siguientes. El almacenamiento y la consulta de las fracciones pueden ser problemáticos, y esto conduce a la técnica de codificación matricial, que transforma esas fracciones en una matriz de 2x2 y la mayoría de las operaciones se pueden realizar con un álgebra matricial que no es evidente a primera vista pero que puede ser muy eficiente.

Treebeard tiene implementaciones muy sencillas de cada una de las rutas de acceso 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 al padre y puede usarlo para consultar a los niños de manera más eficiente, y para reconstruir el árbol en caso de que alguien lo arruine.