Parcours en profondeur préfixe d’une arborescence

L’une des caractéristiques exclusives de notre base de données worldCities est l’utilisation du parcours en profondeur de l’arborescence dans la table features_hierachy (hiérarchie). Voici une description rapide de son fonctionnement et de ses avantages.
(Si vous ne possédez pas de copie de worldCities pour le moment mais voulez voir comment cela fonctionne dans la pratique, vous pouvez télécharger gratuitement la démo de worldCities et utiliser les requêtes inclues à la fin de cette article)

Relation père-fils

Avant de passer au parcours en profondeur de l’arborescence, jetons un coup d’oeil à la classique relation père-fils, que la plupart des développeurs connaissent. Une liste des continents et macro-régions d’après l’Organisation des Nations Unies pourrait se présenter sous cette forme, où feature_id représente les fils et parent_id les pères :

feature_idparent_idnom
10Monde
21Afrique
32Afrique occidentale
42Afrique orientale
52Afrique septentrionale
62Afrique centrale
72Afrique australe
81Amériques
98Amérique du Nord
108Amérique latine et Caraïbes
1110Amérique du Sud
1210Amérique centrale
1310Caraïbes
141Asie
.........

C’est assez facile d’obtenir la liste des continents, par exemple. Il suffit de rechercher tous les registres avec parent_id=1 (Monde), and vous obtiendrez Afrique, Amériques, Asie, etc… Si vous voulez aussi les macro-régions, il faut écrire une autre requête (ou utiliser LEFT JOIN si vous préférez n’en avoir qu’une). Cependant, dès qu’il y a plusieurs ou un nombre différent de niveaux, utiliser LEFT JOIN devient vite compliqué. Avoir de multiples requêtes n’est pas non plus particulièrement efficace.

Parcours en profondeur préfixe d’une arborescence

Avec le parcours en profondeur préfixe de l’arborescence, on ajoute deux valeurs (gauche et droite) à chaque registre. Il suffit de donner la valeur gauche à chaque registre, en suivant la hiérarchie jusqu’à ce qu’on arrive à la fin d’une branche, auquel cas on assigne la valeur de droite avant de passer à la branche suivante. Cela peut paraître un peu confus au début, mais il est plus facile de comprendre le principe en le voyant, comme sur le schéma suivant, qui montre comment les valeurs de gauche et de droite sont assignées.

parcours en profondeur d'une arborescence

Dans cet exemple, nous commencer avec la valeur de gauche de Monde, puis Afrique et Afrique occidentale. Ce dernier registre est la fin de cette branche et nous lui donnons donc la valeur de droite, avant de passer à Afrique orientale, etc… Après avoir assigné les valeurs de droite d’Afrique australe et Afrique, on passe au continent suivant, et ainsi de suite. Lorsque tous les continents et régions ont leurs valeurs de gauche et de droite, il ne reste plus que la valeur de droite de Monde (58).

Notre table de continents et régions ressemble maintenant à ceci, où left contient les valeurs de gauche et right celles de droite :

feature_idparent_idleftrightnom
10158Monde
21213Afrique
3234Afrique occidentale
4256Afrique orientale
5278Afrique septentrionale
62910Afrique centrale
721112Afrique australe
811425Amériques
981516Amérique du Nord
1081724Amérique latine et Caraïbes
11101819Amérique du Sud
12102021Amérique centrale
13102223Caraïbes
1412637Asie
...............

Pourquoi est-ce utile dans la pratique ? Pour moi, la raison principale est qu’il est très facile d’obtenir plusieurs niveaux de données avec une seule requête, ce qui permet de réduire la charge sur le serveur de la base de données et donc d’accélérer le traitement, ainsi que d’écrire du code plus simple.

Obtenir un noeud et tout ce qui ce trouve en-dessous

En examinant les valeurs de gauche et droite, on se rend vite compte que :

  1. tous les registres en-dessous d’un noeud ont des valeurs de gauche (et de droite) supérieures à la valeur de gauche de ce noeud ;
  2. tous les registres en-dessous d’un noeud ont des valeurs de gauche (et de droite) inférieures à la valeur de droite de ce noeud.

Donc, si par exemple vous voulez obtenir Amériques et tous ses descendants, il suffit de chercher les registres ayant une valeur de gauche entre 14 et 25 (left between 14 and 25).
Pour n’obtenir que les descendants, on recherche les registres avec la valeur de gauche entre 15 et 25 (left between 15 and 25).

Obtenir l’ascendance d’un noeud

De la même façon, pour trouver l’ascendance d’un noeud, il suffit de trouver les registres avec :

  1. une valeur de gauche qui inférieure ou égale à la valeur de gauche de ce noeud ;
  2. une valeur de droite qui est supérieure ou égale à la valeur de droite de ce noeud.

Pour obtenir l’ascendance des Caraïbes, on recherche donc les registres où gauche<=22 et droite>=23 (where left<=22 and right>=23).
Pour avoir seulement l’ascendance et pas le registre même des Caraïbes, on enlève l’égalité et on recherche les données où gauche<22 et droite>23 (where left<22 and right>23).

Combien de descendants a un certain noeud ?

Pour le dernier exemple de cette introduction rapide au parcours en profondeur de l’arborescence, comptons !
Trouver le nombre de descendants d’un certain node est très facile avec cette simple formule:
(droite – gauche – 1) / 2

Conclusion

Le parcours en profondeur de l’arborescence est un moyen tès facile et puissant de travailler avec plusieurs de niveaux de données hiérarchisées. Et comme vous l’avez sans doute remarqué, qu’on travaille avec les données d’Afrique ou des Amériques, qui ont un niveau supplémentaire, les requêtes sont absolument identiques ! Il n’y a pas besoin de changer les requêtes en fonction de la profondeur des donnnés ni même de point de départ dans la hiérarchie. Il est malgré tout parfois plus facile d’utiliser la classique relation père-fils, par exemple lorsque l’on recherche simplement les pères ou fils d’un registre, au lieu de son ascendance ou descendance complète. C’est pourquoi les deux méthodes sont disponibles dans notre base de données worldCities.

Dans worldCities

Pour voir comment on utilise les données hiérarchiques dans la pratique, jetez un oeil aux exemples de requêtes pour worldCities. Certaines utilisent la relation classique père-fils, alors que d’autres utilisent le parcours en profondeur préfixe d’une arborescence.