Ordonnancement d'arbres hiérarchiques en base de données

Plusieurs possibilités existent pour ordonner un arbre hiérarchique en base de données. Nous survolons ici quelques méthodes, avec des liens pour approfondissement.

• Cas le plus simple, l'adjcency model list :

On crée un table a 2 colonnes, avec l'id de la catégorie, et l'id du père de la catégorie. C'est la méthode de base actuellement implémenté dans drupal.

CREATE TABLE category(
id INT AUTO_INCREMENT PRIMARY KEY,
parent INT DEFAULT NULL);

L'algorithme de parcours est relativement trivial, mais il fait appel la plupart du temps à des fonctions récursives qui sont gourmandes en utilisation de mémoire. A noter qu'ici l'id est clé primaire, mais pour de la hiérarchie multiple, nous aurions choisi le couple (id, parent) comme clé.

• Second cas, Nested sets :

il s'agit de numéroter les éléments avec une valeur a droite et une a gauche, en parcourant l'arbre par la gauche.

crédit phpclub.ru

Si les calculs sont relativement moins gourmand, il est plus compliqué de reorganiser un arbre, et la recherche des ancêtres à partir d'un noeud n'est pas très efficace. Cette méthode est disponible dans drupal via le module leftright

• troisième cas, Materialized path :

Nous stockons dans ce cas précis le chemin complet du père au fils. Ceci ressemblera a  :

Root 1 , Fils 1.1, Fils2 1.2, Fils3 1.1.1, Fils4 1.2.1 etc...

Le problème ici sera de trouver tous les descendants d'un noeud au niveau 2 par exemple, mais la réorganisation d'un arbre est facile.

• quatrième cas, Nested intervals with Matrix

il s'agit ici de calculer des quotients à partir de suites mathématiques itérées entre les membres. Plusieurs méthodes et formules sont possibles. On retombe alors sur du calcul matriciel et de la division euclidienne pour remonter ou descendre dans l'arbre. Nous renvoyons le lecteur directement a l'article de vladim tropashko sur le sujet. Ceux ci sont particulièrement utiles avec de très gros arbres.

Il existe encore beaucoup d'autres méthodes, notamment à partir de calcul de nombres premiers.