Modèles de données hiérarchique: Liste contiguïté vs. Ensembles emboîtées

Question

J'ai un catalogue de produits. Chaque catégorie se compose d'un nombre différent (en profondeur) des sous-catégories. Le nombre de niveaux (de profondeur) est inconnu, mais je tout à fait sûr qu'il ne sera pas dépasser 5,6 de niveaux. Les changements de données sont beaucoup plus rarement lit alors.

La question est: quel type de modèle de données hiérarchique est plus approprié pour une telle situation. Le projet est basé sur le framework Django et il est des particularités (admin i-face, la manipulation des modèles ...) doivent être pris en compte.

Merci!

Answer 1

Nested sets sont meilleurs pour la performance, si vous n'avez pas besoin mises à jour fréquentes ou ordre hiérarchique.

Si vous avez besoin soit des mises à jour des arbres ou ordre hiérarchique, il est préférable d'utiliser le modèle de données parent-child.

Il est facilement construit Oracle et SQL Server 2005+, et pas si facilement (mais possible) MySQL.

Answer 2

Je voudrais utiliser la mise à jour Précommande Arbre algorithme Traversal, MPTT, pour ce genre de données hiérarchiques. Cela permet à des performances exceptionnelles sur la traversée de l'arbre et de trouver les enfants, si vous ne me dérange pas un peu d'une pénalité sur les modifications de la structure.

Heureusement, Django a une grande bibliothèque disponible pour cela, django-MPTT . Je l'ai utilisé dans un certain nombre de projets avec beaucoup de succès. Il y a aussi django-treebeard qui offre plusieurs algorithmes alternatifs, mais je n'ai pas utilisé (et il ne semble pas aussi populaire que MPTT de toute façon).

Answer 3

Selon ces articles:

http://explainextended.com/ 2009/09/24 / contiguïté-list-vs-emboîtées ensembles-postgresql / http://explainextended.com/2009/09 / 29 / contiguïté-list-vs-imbriqués-ensembles-mysql /

« MySQL est le seul système des quatre grands (MySQL, Oracle, SQL Server, PostgreSQL) pour lesquels le modèle des ensembles imbriqués montre des performances décentes et peut être considéré comme des données hiérarchiques stockées. »

Answer 4

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

Answer 5

La liste contiguïté est beaucoup plus facile à maintenir et à des ensembles imbriqués sont beaucoup plus rapides à interroger.

Le problème a toujours été que la conversion d'une liste de contiguïté structures hiérarchisées a pris beaucoup de longs grâce à une méthode vraiment méchant « stack push » qui est chargé avec RBAR. Donc, les gens finissent par faire un peu d'entretien très difficile dans des jeux ou non emboîtés les utiliser.

Maintenant, vous pouvez avoir votre gâteau et le manger aussi! Vous pouvez faire la conversion sur 100 000 nodesin moins de 4 secondes et un million de lignes en moins d'une minute! Dans T-SQL, par le chemin! S'il vous plaît voir les articles suivants.

Hiérarchies sur Stéroïdes # 1: Convertir une liste de contiguïté Définit Nested

Hiérarchies Stéroïdes # 2: Un remplacement pour emboîtées calculs Sets