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.