Lorsqu'on veut représenter une hiérarchie (une arborescence), la méthode la plus couramment utilisée est la structure par auto-jointure, c'est à dire avec une relation parent/enfant.

Représentation graphique de l'arborescence

S'il est facile de trouver le parent d'un élément ou les élements enfants de premier niveau avec des requètes simples, ça se complique énormément sitôt que l'on veut aller à des niveaux plus bas, il faut utiliser des requètes récursives qui ne peuvent pas être mises en place partout.
Ce système de classification est donc à proscrire si au moins l'une des conditions ci-dessous est vérifiée:

• l'arbre est profond (plus de 5 niveaux)
• l'arbre est large (plus de 100 éléments sur un même niveau)
• l'arbre contient beaucoup de valeurs (à partir de 200 à 300 éléments)
• la majorité des requêtes sont des requêtes d'interrogation - SELECT (au moins 50% des requêtes)

Il existe une seconde méthode qui nécessite un peu plus de travail pour la modélisation mais qui s'avère payante sitôt qu'on en a pris l'habitude: la représentation intervallaire.

Le principe est de donner à chaque élément ses bornes "gauche" et "droite". L'attribution des valeurs de ces bornes se fait en parcourant l'arbre comme si l'on traçait une ligne pour l'entourer au plus près sans jamais croiser cette ligne avec une branche et en numérotant séquentiellement chaque feuille ou nœud une première fois par le bord gauche et une seconde fois par le bord droit.

Représentation graphique de l'arborescence

On peut aussi représenter cette nouvelle arborescence sous forme de "tranches":

Représentation par tranches

Voici la requète de création (et de remplissage) de la table représentant cette structure:


Recherches dans l'arbre
Les requètes de recherche sont maintenant très simplifiées:
Recherche des "feuilles"
Une feuille est un élément final, donc l'écart entre sa borne gauche et sa borne droite est de 1:

Recherche des feuilles d'une branche
Les bornes d'une branche indiquent les éléments précédents et suivant, il nous suffit donc de lister tous les éléments dont les bornes sont strictement comprises entre BG et BD de la branche pour avoir l'intégralité des sous-éléments.
Par exemple pour la famille "terrestre" donc BG=22 et BD=35:

Recherche des noeuds
Un noeud se caractérise par le fait que BD-BG est supérieur à 1:


Insertions
L'insertion d'un élément oblige bien évidemment à faire plusieurs requètes:
La première pour décaler les bornes droites des éléments suivants ainsi que du parent, la seconde pour décaler les bornes gauches des éléments suivants et enfin la dernière pour insérer le nouvel élément.

Ainsi, si l'on veut ajouter un élément "Roller" dans la famille terrestre, il va falloir:

1. Augmenter de 2 la valeur de toutes les bornes droites dont la valeur initiale est supérieur ou égale à 35 (ce qui inclut le parent),
2. Augnemter de 2 la valeur des toutes les bornes gauches dont la valeur initiale est supérieure ou égale à 35 (ce qui exclut le parent),
3. Insérer le nouvel élément.

Suppression d'un noeud
La suppression d'un élément se fait avec une requète sur sa borne gauche.

Mais ceci nous laisse un trou dans l'arborescence et les comptes risquent d'être faussés.
Il faut donc réordonner les éléments qui se trouvent à droite, en décrémentant leur borne gauche et leur borne droite de 2:


On peut presque aussi simplement supprimer un noeud et tout ses contenus, il suffit de supprimer tous les éléments dont la borne gauche est supérieure ou égale à la borne gauche du noeud considéré et dont la borne droite est inférieure ou égale à la borne droite du noeud:

Pour renuméroter les éléments qui se trouvent à droite, il faut décrémenter les bornes gauches et droites d'une valeur simplement calculable: (BD - BG + 1), ce qui dans notre cas donne 14.


L'insertion d'un noeud complet serait aussi simple, à la différence qu'il faut bien entendu effectuer les décalages avant d'insérer les enregistrements.

Avec une base de données acceptant les procédures stockées, on peut très facilement automatiser les différentes opérations.

Voici un article fort intéressant de Patrick Haederli, qui en plus propose une classe PHP pour la gestion de de ce type de hiérarchies.