Modelos jerárquicos de datos: lista de adyacencia vs. conjuntos anidados

Question

Tengo un catálogo de productos. Cada categoría consiste en número diferente (en profundidad) de subcategorías. El número de niveles (de profundidad) es desconocida, pero muy seguro de que no se exceda de 5,6 niveles. Los cambios de datos son mucho más raramente lee a continuación.

La pregunta es: ¿qué tipo de modelo de datos jerárquico es más adecuado para tal situación. El proyecto se basa en el marco de Django y es peculiaridades de administración (i-cara, el manejo de los modelos ...) deben ser considerados.

Muchas gracias!

Answer 1

Nested sets son mejores para el rendimiento, si no necesita actualizaciones frecuentes o ordenamiento jerárquico.

Si necesita cualquiera de las actualizaciones de árboles u orden jerárquico, es mejor utilizar el modelo de datos parent-child.

Se construye fácilmente en Oracle y SQL Server 2005+, y no tan fácilmente (pero aún es posible) en MySQL.

Answer 2

Me gustaría utilizar el algoritmo de recorrido Preordenes árbol Modificado, MPTT, para este tipo de datos jerárquicos. Esto permite un gran rendimiento en recorrer el árbol y la búsqueda de los niños, si no te importa un poco de una sanción a los cambios en la estructura.

Por suerte Django tiene una gran biblioteca disponible para esto, django-MPTT . He utilizado este en una serie de proyectos con mucho éxito. También hay django-treebeard que ofrece varios algoritmos alternativos, pero no he utilizado (y no parece tan popular como MPTT de todos modos).

Answer 3

De acuerdo con estos artículos:

http://explainextended.com/ 2009/09/24 / adyacencia-list-vs-anidado-sets-postgresql / http://explainextended.com/2009/09 / 29 / adyacencia-list-vs-anidados-conjuntos-mysql /

"MySQL es el único sistema de los cuatro grandes (MySQL, Oracle, SQL Server, PostgreSQL) para la cual el modelo conjuntos anidados muestra un rendimiento decente y se puede considerar a los datos almacenados jerárquicos."

Answer 4

http://www.sqlsummit.com/AdjacencyList.htm

Answer 5

La lista de adyacencia es mucho más fácil de mantener y conjuntos anidados son mucho más rápido que desea consultar.

El problema siempre ha sido que la conversión de una lista de adyacencia a conjuntos anidados ha tomado forma de largos gracias a un método realmente desagradable "empuje pila" que se carga con RBAR. Así que la gente termina haciendo un mantenimiento muy difícil en conjuntos anidados o no usarlos.

Ahora, usted puede tener su pastel y comérselo también! Se puede hacer la conversión de 100.000 nodesin menos de 4 segundos y en un millón de filas en menos de un minuto! En T-SQL, por cierto! Por favor, vea los artículos siguientes.

jerarquías con esteroides # 1: Convertir una lista de adyacencia a anidada Establece

jerarquías con esteroides # 2: Un reemplazo de conjuntos anidados Cálculos