[SQL] La meilleure méthode pour stocker une arborescence ?

Un chemin canonisé, ça peut être une chaîne de caractères qui donne le chemin d’un noeud, mais chaque morceau du chemin a la même longueur.
Exemple:
Voici ton arbre (identifiants entiers entre parenthèses):
(1) Root
  (2) Enfant 1
  (4) Enfant 1.1
  (3) Enfant 2

Le chemin de Enfant 1.1 est 1/2/4, ok? Bon, tu formattes chaque nombre par exemple en hexadécimal de largeur fixe (si tes identifiants sont 32 bits, ça fait 8 caractères), et le chemin canonisé est:
000000010000000200000004

Ca te permet par exemple de récupérer tout les enfants de Enfant 1 quelle que soit la profondeur en faisant Chemin like ‘0000000100000002%’.
Bon, c’est sûr que les like, c’est pas le pied en termes de perf, mais ça sera toujours mieux que d’explorer l’arbre récursivement.

Mais une fois de plus, ça vaut pas les arbres par intervalles en lecture. En revanche, en écriture, c’est plus rapide (c’est du O(1) au lieu de O(log n)) puisqu’il suffit de connaître l’identifiant du noeud et le chemin du parent pour créer le nouveau chemin.

ET hop je boucle en vous racontant comment les intervallaires c’est trop bien et comment je les ai utilisés. Bon, vous avez eu le détail de mon problème, mais je résume quand même :
 - on a des groupes qui contiennent des catégories
 - les catégories mènent à un ou plusieurs groupes
 - je veux afficher en HTML/CSS la totalité de mon arbres avec un parcours bien précis.
 - le parcours, en l’occurence, est celui obtenu par la récursivité : je commence d’un groupe top-level, puis pour chaque catégorie de ce groupe je vais au(x) groupe(s) destination(s) et recurse power…

Le premier modèle qui vient à l’esprit est une bête liaison “parent-enfant” ou seul l’enfant connait son parent. C’est facile à manipuler, et puis venant du C/C++ c’est assez naturel (pointeurs, chainage, etc.). Mais en PHP/SQL la donne change à cause du coût des requêtes niveau CPU/RAM. A ce stade j’en étais à deux requêtes par groupe et comme l’arbre doit être parcouru à chaque utilisation du moteur par un visiteur du site : pas bien, nul, sale, 02/20…

Arrive alors le 2e modèle, à savoir les arbres intervallaires. C’est beau, c’est propre, c’est rapide et facile… bref, mangézan.
Mais survient vite un gros problème : le parcours d’un arbre intervallaire n’est pas du tout celui qu’il me faut (contraintes du HTML/CSS). Je peux effectivement parcourir mon arbre en une seule requête mais je ne peux rien faire du résultat. Pleurs, cris et grincement de dents. En plus de ça, si l’insertion et la suppression d’éléments de l’arbre est facile, c’est beaucoup moins drôle quand on commence à faire des déplacements de branches. Tout remettre en place à la volée demande beaucoup de code lourd et je vois mon back-office devenir une usine à gaz.

La solution trouvée est simple et aussi efficace qu’un bulldozer : toutes les opérations en écriture sur l’arbre sont gérées selon le premier modèle (lien enfant vers parent). A la fin de chaque opération, je reconstruis intégralement mon arbre selon le 2e modèle en utilisant les informations du 1er modèle. Autrement dit, je parse mon arbre en récursif et insère en intervallaire chaque donnée. J’en profite pour noter l’ordre de passage et ainsi garder au chaud l’ordre de parcours dont j’ai besoin.
Mais alors, si j’ai mon ordre de parcours, quel est l’intérêt d’avoir de l’intervallaire me direz vous ? Ne suffirait t’il pas de fait un simple : SELECT * FROM categories ORDER BY parse_order ?
Oui je pourrais, mais avec les intervallaires je peux parcourir mon arbre à partir de n’importe quel noeud tout en gardant le parcours dont j’ai besoin. L’est trop belle la vie. Trop merci.

Valaaaaa, c’est tout. Je sais pas si ça été très clair et si pourra servir à quelqu’un, mais en tous cas je l’espère.

Antoine

[quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre: http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]D’ailleurs sur cet article , l’auteur met une colonne CatID, alors que dans l’article  il met la clé primaire sur la Bordure Gauche…
Ce message a été édité par EzecKiel le 17/03/2004

[quote]D’ailleurs sur cet article , l’auteur met une colonne CatID, alors que dans l’article  il met la clé primaire sur la Bordure Gauche…[/quote]C’est la théorie dans le cas du site SQL Pro.

Par la suite (regarde en bas), il crée des exemples de procédures stockées pour SQL Server et précises une colonne de type identity (auto-incrémentable) dans le schéma.

Donc tu retrouves le même schéma physique que celui de Labo .NET

[quote][quote]Voici un article génial qui donne LA structure la plus optimisée que je connaisse pour stocker un arbre:
http://www.labo-dotnet.com/labo-dotnet/?ta…ticle&ID=14[/quote]un autre qui y ressemble étrangement : SQL Pro
[/quote]
Excellent ce concept décidement!

Je me suis repenché dessus à la suite d’un besoin issu d’un cas concret il y a quelques jours. Il y a de grandes chances que les arbres par representation intervallaire soient la solution à mon problème.
Merci boudin et mccricri. En plus c’est une solution saine orientée base de données comme je les aime.

Ce message a été édité par phili_b le 26/03/2004