Il est plus facile d'expliquer avec des exemples qu'avec quelques mots. Considérons l'arbre de l'échantillon, le stockage des noms:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Matérialisé chemin signifie que chaque nœud stocke son chemin complet codé. Par exemple, vous pouvez stocker son index à l'aide d'un point comme séparateur
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
Ainsi, Adams connaît son nom complet est Wiliam Blake Adams, parce qu'il a le chemin 1.2.1, pointant vers le noeud 1 au premier niveau - William - au nœud 1.2 au niveau 2 - Blake - et au nœud 1.2.1 au niveau 3 - Adams.
Liste d'adjacence signifie que l'arbre est stocké en gardant un lien vers certains nœuds adjacents. Par exemple, vous pouvez stocker qui est le parent et qui est le prochain frère.
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
avis qu'il pourrait être aussi simple que le stockage du parent, si l'on n'a pas besoin de garder les enfants d'un noeud ordonné. Maintenant Adams peut obtenir tous ses ancêtres récursivement jusqu'à null pour trouver son nom complet.
Ensembles imbriqués signifie que vous stockez chaque noeud avec un index, généralement une valeur gauche et droite, attribué à chacun lorsque vous traversez l'arborescence dans l'ordre DFS, de sorte que vous savez que ses descendants sont dans ces valeurs. Voici comment les chiffres seraient affectés à l'arbre exemple:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
Et il serait stocké comme:
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
Donc, maintenant Adams peut trouver ses ancêtres en questionnant qui a une partie inférieure gauche et un valeur supérieure droite et les trier par la valeur de gauche.
Chaque modèle a ses forces et ses faiblesses. Le choix de celui à utiliser dépend vraiment de votre application, de la base de données que vous utilisez et du type d'opérations que vous ferez le plus souvent. Vous pouvez trouver une bonne comparaison here. La comparaison mentionne un quatrième modèle qui n'est pas très commun (je ne connais pas d'autre implémentation que la mienne) et très compliqué à expliquer en quelques mots: Intervalle imbriqué via l'encodage matriciel. Lorsque vous insérez un nouveau nœud dans un ensemble imbriqué, vous devez énumérer de nouveau tous ceux qui le devancent dans la traversée. L'idée derrière les intervalles imbriqués est qu'il y a un nombre infini de nombres rationnels entre deux entiers, de sorte que vous pouvez stocker le nouveau nœud comme une fraction de ses nœuds précédents et suivants.Le stockage et l'interrogation des fractions peuvent être gênants, ce qui conduit à la technique de codage matriciel, qui transforme ces fractions en une matrice 2x2 et la plupart des opérations peuvent être effectuées par une algèbre matricielle non évidente à première vue mais très efficace. Treebeard a des implémentations très simples de chacun des chemins matérialisés, des ensembles imbriqués et des listes d'adjacence, sans redondance. django-mptt utilise en fait un mélange d'ensembles imbriqués et de listes d'adjacence, car il conserve également un lien vers le parent et peut l'utiliser pour interroger les enfants plus efficacement et reconstruire l'arbre au cas où quelqu'un le bousillerait.