Mes impressions sur le web, les standards et autres…


SQL et structure arborescente

Dans le cadre d’un projet que je développe en ce moment, j’ai besoin de stocker un arbre dans une base de données, c’est à dire un groupe d’éléments reliés par une relation de type parent-enfant. Plusieurs solutions existent :

Les listes adjacentes

C’est la méthode la plus naturelle et celle à laquelle j’ai d’abord penser. Le principe est tout simplement d’associer à chaque nœud l’identifiant du nœud parent. On peut ensuite extraire nos données de différentes façons avec des auto-jointures (voir le lien vers mysql en fin de billet).

Le problème est que cela n’est pas applicable si la profondeur de l’arbre n’est pas fixée. Il faut alors en passer par une routine récursive (en PHP dans mon cas) pour construire l’arbre et travailler dessus. C’est bourrin, c’est coûteux…

Les ensembles imbriquées ou représentation intervallaire

Moins facile à appréhender, cette technique offre en revanche une bien plus grande facilité pour lire tout ou partie de l’arbre. La plupart des opérations de lecture ne nécessitent qu’une requête SQL !

Le principe est d’assigner à chaque élément deux bornes, les descendants de cet élément étant englobés dans l’interval créé par ces deux bornes. Je me permets de copier ici la représentation visuelle en tranche donnée dans l’article de SQLpro, ça permet de tout de suite se faire une bonne idée du mécanisme :

Représentation sous forme de tranches englobantes du mécanisme des ensembles imbriqués

Je ne m’attarde pas sur les requêtes SQL à utiliser pour consulter un tel arbre, consultez l’excellent article Gestion d'arbres par représentation intervallaire pour en savoir plus.

Ici, donc, pas besoin de récursivité, la lecture est simple et claire. Mais les choses se gâtent dès qu’on souhaite effectuer des changements sur notre arbre. Souhaite t-on ajouter un élément dans notre arbre ? Paf, trois requêtes ! Une pour décaler les bornes droite, une autre pour décaler les bornes gauches, et enfin, la requête pour insérer le nouvel élément. Et si plusieurs modifications peuvent potentiellement survenir quasiment au même moment, ne pas utiliser les transactions, et donc, dans le cas de MySQL, les tables innoDB, serait plutôt hasardeux.

Autres idées

Comme autre technique, il y en a une qui consiste à stocker carrément le chemin canonisé d’un élément à la racine. Pas super élégant et viable seulement pour des petits arbrisseaux ;¬)

J’ai vaguement pensé à stocker la structure de l’arbre sous forme XML, elle-même stockée dans la base de données, mais là comme ça, sans creuser l’idée, je me dis que les performances ne seront pas vraiment au rendez-vous. Qu’en penses-tu toi, visiteur perdu sur mon journal ? Et si tu as d’autres idées pour gérer un arbre, n’hésite pas ;¬)

Vos réactions, opinions, insultes…

Rétroliens

Faire un rétrolien sur ce billet : [trackback]

Commentaires

1. De Vincent {CiD}

J'attendais que quelqu'un commente avant moi, mais bon… Je m'y colle :)

Donc, moi aussi j'utilise cette méthode qui s'avère nettement plus pratique à mettre en oeuvre niveau écriture du code que les autres solutions. C'est simple et élégant.

Par contre, là où ça pourrait être interressant, c'est effectivement un retour d'experience au niveau de la mise en production… Je ne suis qu'au stade du développement et je nai pas encore ''stresser'' mon application.

Je suis donc au même stade que toi, m'intérogeant comment peuvent bien faire les autres…

Là où je n'ai aucun doute, par contre, c'est au niveau des performances en ''lecture'' des données. Une requête suffit pour récuperer une branche, pas de récursivité et c'est vraiment ça qui fait la différence pour moi.

2. De Bobe

En fait, tout dépend de ce qu’on fait de l’arbre en question.

Avec le modèle des ensembles imbriqués, je devrais vraiment utiliser les transactions, mais les requêtes sur des tables innoDB sont plus lentes que sur des tables MyIsam, et je devrai quand même utiliser la récursivité pour gérer l’affichage…

Pour l’instant, je gère les deux modèles en parallèle en définissant l’identifiant du parent et les deux bornes (+ les deux update de décalage des bornes bien sûr) et en faisant l’affichage avec une fonction récursive.

3. De loufoque

C'est moi qui avait le premier parlé de cela pour Stacox, et j'avais d'ailleurs écrit des informations sur le premier wiki.
Le mieux me semble d'utiliser les ensembles imbriqués pour les messages et la technique du chemin pour les forums.
On peut aussi essayer de faire les intervalles imbriqués si le SGBD le permet.

Attention néanmoins, l'article français de SQLpro est incomplet.
En fait, il n'y a pas besoin d'un champ "niveau", on peut calculer ça avec une auto-jointure, ce qui est mieux au niveau maintien de l'intégrité des données mais moins bien en performance.

Dans le cas où tu ne peux pas avoir de transactions, tu peux au pire bloquer les tables (ce que permet MyISAM).

4. De Bobe

Je suis plutôt parti pour utiliser les ensembles imbriqués pour les forums. En effet, ça permet plus facilement de gérer la position exacte d’un forum.

Et comme les modifications sur cet arbre (ajout, retrait de forum, …) sont rares, c’est tout à fait adapté.

Pour les messages, je suis toujours avec le mécanisme de stockage de l’ID parent, même si je définis les bornes à l’insertion.

J'ai besoin de sélectionner une branche avec les 3 premiers subordonnés immediats.

Exactement comme sur le site http://www.dmoz.org/ ou l'on voit donc la catégorie principale et les 3 premières sous-catégories avec "…"

Je dois utiliser "mysql 5".

Ma tables "categories" contient les champs suivants.

id
borne_gauche
borne_droite
niveau
label

Une idée ou une solution ?
Peut être faut il utiliser des sous-requêtes …

6. De bobe

Utiliser un LIMIT dans ta requête n’irait pas ?

SELECT * FROM categories WHERE borne_gauche = X LIMIT 4.

À moins que je ne sois complètement à la ramasse car j’ai eu une longue journée.

7. De SQLproSite

Depuis l'arrivée de la norme SQL:1999 (soit 9 ans) les SGBDR sont apte à faire directement des requêtes récursive afin de traiter des abres et des graphes. Voyez l'étude complémentaire que j'ai écrit à ce sujet :
http://sqlpro.developpez.com/cours/sq(…)

Ce qui complète l'article que que vous avez cité et dont je suis l'auteur !

A +

L’ajout de commentaires sur ce billet n’est pas/plus autorisé.