Modelos de datos jerárquicos: Lista de adyacencia frente a conjuntos anidados

Question

Tengo un catálogo de productos. Cada categoría consta de diferentes números (en profundidad) de subcategorías. Se desconoce el número de niveles (profundos), pero estoy bastante seguro de que no superará los 5,6 niveles. Los cambios en los datos son mucho más raros que las lecturas.

La pregunta es: qué tipo de modelo de datos jerárquico es más adecuado para esa situación. El proyecto se basa en el framework Django y sus peculiaridades (admin i-face, manejo de modelos ...) deben ser consideradas.

¡Muchas gracias!

Answer 1

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

Si necesita actualizaciones de árbol u ordenamiento 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

Utilizaría el algoritmo Modified Preorder Tree Traversal, MPTT, para este tipo de datos jerárquicos. Esto permite un gran rendimiento al atravesar el árbol y encontrar niños, si no te importa un poco de penalización por los cambios en la estructura.

Afortunadamente Django tiene una gran biblioteca disponible para esto, django-mptt. Lo he usado en una serie de proyectos con mucho éxito. También hay django-treebeard que ofrece varios algoritmos alternativos, pero no lo he usado (y de todos modos no parece tan popular como mptt).

Answer 3

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

Answer 4

De acuerdo con estos artículos:

http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/

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

Answer 5

La lista de adyacencia es mucho más fácil de mantener y los conjuntos anidados son mucho más rápidos de consultar.

El problema siempre ha sido que la conversión de una Lista de adyacencia a conjuntos anidados ha tomado mucho tiempo gracias a un método realmente desagradable de "pila de inserción" que está cargado con RBAR. Entonces la gente termina haciendo un mantenimiento realmente difícil en los Juegos Anidados o no los usa.

¡Ahora, puedes tener tu pastel y comértelo también! ¡Puedes hacer la conversión en 100.000 nodos en menos de 4 segundos y en un millón de filas en menos de un minuto! ¡Todo en T-SQL, por cierto! Por favor mira los siguientes artículos.

Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations