Technique | Modéliser un arbre simplement dans PostgreSQL

Par Jean-Paul Argudo le 08/02/2005 - 14:54

Bonjour,

Parmis les problèmes récurrents auxquels on est confrontés lorsqu'on fait un schéma de données, il y a la modélisation des arbres.

Il s'agit de bien conceptualiser une structure hiérarchique dans une base de données. Je vous propose une méthode éprouvée pour le faire simplement! (attention, ne pas confondre avec un graphe...).

Deux méthodes "anciennes":

• id / parent_id: Tout d'abord, on trouve la méthode id / parent_id. C'est à dire qu'on boucle sur la même table, en ajoutant une colonne du même type que l'identifiant et en bouclant sur cette même colonne, avec un lien père / fils.

  Il n'y a pas grand chose à dire sur cette méthode si ce n'est qu'elle montre un peu ses limites en matière de performances lorsqu'on a un arbre conséquent... De plus les mises à jour de l'arbre (suppression ou déplacement d'un noeud) sont assez hardues et nécessitent un code particulier.
  

• nested loops (ou "boucles imbriquées): Il s'agit de modéliser un arbre en sachant à l'avance quelle sera la "largeur" de celui-ci. C'est à dire que pour un arbre donné, la racine ira de 1 à n, le premier fils de la racine, de 1 à m. Le second fils de la racine, de m+1 à n et ainsi dessuite pour les descendants. Je vous laisse le soin de découvrir cette méthode en lisant http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=145525]

Il existe bien mieux que ces deux méthodes !
Miguel Sofer, dans le travail de recherche qu'il a effectué présente une méthode novatrice. Il s'agit d'ajouter une colonne à toute table stockant les noeuds de l'arbre. Grâce à un encodage particulier, on arrive ainsi à savoir très rapidement :

• quel est le niveau du noeud dans l'arbre ;
• quel est le père d'un noeud dans l'arbre ;
• quel est la lignée d'un noeud de l'arbre ;
• etc.

Pour avoir un apperçu rapide de cette méthode, vous pourrez consulter l'article du projet OpenACS correspondant. Pour la petite histoire, ACS est un système de gestion du contenu qui ne tournait que sous Oracle. Lorsque son portage sous PostgreSQL fut réalisé, il a fallu trouver un moyen pour :

• modéliser un arbre correctement dans une base de données, en privilégiant la
  souplesse d'utilisation et les performances ;
• remplacer l'écriture de la syntaxe Oracle "CONNECT BY".

Je vous recommande très vivement de lire l'article original de Miguel Sofer sur cette méthode. Il démontre son efficacité de manière mathématique, et propose des exemples de code d'implémentation en PostgreSQL !

Vous pouvez tout aussi bien utiliser la contrib PostgreSQL qui s'appelle « ltree Â», qui utilise la même méthode que celle de Miguel Sofer, mais dont l'implémentation a été réalisée par Oleg et Teodor, deux contributeurs majeurs à PostgreSQL (index GiST, recherche plein texte tsearch2, etc.). Plus d'infos sur cette page.

Sachez enfin que l'implémentation du CONNECT BY nativement dans PostgreSQL est un sujet au goût du jour et ne serait tarder, comme on peut le lire sur ce thread(google groups).

En espérant que cet article puisse vous aider!

--
Jean-Paul Argudo
www.dalibo.com