Gestion des arborescences
Il existe des techniques permettant d'améliorer sensiblement la manipulation d'arborescences...
Les réflexions menées sur l'amélioration de la carte du site (voir réflexion "carte du site") m'ont incité à me pencher sur le problème posé par le calcul d'une arborescence d'objets.
Dans Yacs, il y a des "objets" qui ont des liens "parent-enfant" entre eux : sections, commentaires, catégories,...
On est alors amené, à un moment donné, à vouloir représenter l'arborescence hiérarchique constitués par ces objets (le père, ses enfants, les enfants de ses enfants, etc).
La méthode récursive
Actuellement, Yacs utilise principalement une technique récursive. Chaque objet mémorise l'identifiant de son parent.
Pour reconstituer l'arbre généalogique, on effectue un calcul récursif : on cherche les enfants puis pour chaque enfant trouvé, on cherche les enfants. Puis pour chaque enfant trouvé, on cherche les enfants... et ainsi de suite.
Lorsque l'arborescence contient des milliers d'enfants, le calcul peut prendre plusieurs dizaines de secondes.
Pour améliorer cela, j'ai trouvé différentes méthodes sur Internet.
La représentation intervallaire
Avec cette technique, on ne mémorise plus les liens "parent-enfant" mais les liens "droite-gauche". On trouve un excellent article de Frédéric Brouard sur le sujet à l'adresse http://sqlpro.developpez.com/cours/arborescence/ et dont voici un extrait :
Peu connue, la représentation intervallaire des arbres est une technique très performante.
Traditionnellement les représentations hiérarchiques font appel à des arborescenses modélisées par une table avec une autojointure entre la clef primaire des données mère et une clef secondaire relative aux données de la ligne fille. Cette simplicité a un coût élevé puisque la plupart des requêtes de recherche dans un tel arbre nécessitent un processus récursif, donc de la programmation [...]
Avec la représentation intervallaire, toutes les recherches deviennent de simples requêtes basiques et les performances sont sans commune mesure avec le modèle en autojointure.Il existe une variante qui consiste à mémoriser, en plus, le niveau où chaque élément se situe dans l'arbre.
Le fil d'ariane
Il existe une variante de la méthode récursive qui consiste à mémoriser, en plus de l'identifiant du père, la lignée complète des aieux (identifiant du grand-père, identifiant de l'arrière grand père, etc). La lignée complète (le fil d'ariane) est stockée dans un champ unique en séparant les identifiants par une virgule (par exemple).
On peut alors retrouver tous les éléments d'une branche, classé dans l'ordre adéquat, grâce à une seule requête !
Comparaison des méthodes
J'ai rapidement calculé le nombre de requêtes et/ou d'écriture en base de données nécessités par différentes opérations sur une arborescence (j'ai procédé parfois à des simplification de calcul donc le résultat n'est pas parfaitement exact mais cela donne l'ordre de grandeur).
La simulation est réalisée sur une arborescence de 7 niveaux de profondeur et où chaque section (nœud) comporte 4 sous-sections, ce qui donne un total de 5461 nœuds.
On se positionne alors sur le 4ème noeud du 4ème niveau... et voilà ce que cela donne :
|
|
Nombre de requête et d'écriture en base |
|
||
|
|
Traitement récursif actuel |
Représentation intervallaire |
Représentation intervallaire + niveaux |
Traitement récursif actuel + fil d'ariane |
|
construire le fil d'ariane |
3 |
1 |
1 |
1 |
|
Trouver les sœurs "directes" (la grande sœur suivante et la petite sœur suivante) |
2 |
2 |
2 |
2 |
|
Trouver toutes les sœurs |
1 |
1 |
1 |
1 |
|
Trouver toutes les filles |
1 |
4 |
1 |
1 |
|
Reconstituer le branche supérieure complète |
21 |
1 |
1 |
1 |
|
reconstituer la branche inférieure "simplifiée" (les parents, grand parents,etc et les oncles, grands-oncles etc) |
4 |
? |
2 |
2 |
|
Construire l'arborescence complete |
1365 |
1 |
1 |
1 |
|
création d'un nouveau nœud |
0 |
2048 |
2048 |
0 |
|
suppression du nœud (et de ses enfants, petits enfants, etc) |
42 |
2048 |
2048 |
21 |
|
déplacement du nœud (et de ses enfants, petits enfants, etc) |
1 |
4096 |
4096 |
21 |
Si l'on passe à 5 sous-sections dans chaque section, on obtient une arborescence de 19000 nœuds et voici ce que cela donnerait :
|
|
Nombre de requète et d'écriture en base |
|
||
|
|
Traitement récursif actuel |
Représentation intervallaire |
Représentation intervallaire + niveaux |
Traitement récursif actuel + fil d'ariane |
|
construire le fil d'ariane |
3 |
1 |
1 |
1 |
|
Trouver les sœurs "directes" (la grande sœur suivante et la petite sœur suivante) |
2 |
2 |
2 |
2 |
|
Trouver toutes les sœurs |
1 |
1 |
1 |
1 |
|
Trouver toutes les filles |
1 |
5 |
1 |
1 |
|
Reconstituer le branche supérieure complète |
31 |
1 |
1 |
1 |
|
reconstituer la branche inférieure "simplifiée" (les parents, grand parents,etc et les oncles, grands-oncles etc) |
4 |
? |
2 |
2 |
|
Construire l'arborescence complete |
3906 |
1 |
1 |
1 |
|
création d'un nouveau nœud |
0 |
7813 |
7813 |
0 |
|
suppression du nœud (et de ses enfants, petits enfants, etc) |
62 |
7813 |
7813 |
31 |
|
déplacement du nœud (et de ses enfants, petits enfants, etc) |
1 |
15625 |
15625 |
31 |
Conclusion
En gras, ce sont les pires scores...
La technique de classement récursif avec gestion du fil d'ariane est la seule qui n'a pas de cellule en gras. Elle obtient même les meilleurs performances dans tous les cas de figure étudiés sauf un : lorsqu'il s'agit de déplacer une branche.
Un déplacement de branche oblige à modifier tous les enregistrements de la branche au lieu de ne modifier que la "tête de branche" (dans le cas actuel).
En terme de performance, cela peut s'avérer un peu long si la branche est longue (beaucoup de rameaux et feuilles). Cependant, le déplacement de branche reste une opération bien moins fréquente que celle qui consiste à construire l'arborescence d'une branche.
Le risque, en cas d'interruption pendant l'opération, est de se retrouver avec une classification bancale. Il faut alors régénérer tous les fils d'ariane pour tout remettre en place. Ce n'est techniquement pas difficile mais comment se rendre compte automatiquement qu'il y a un problème pour lancer la réparation également automatiquement (via une transaction pour annuler le déplacement si problème ?).
Je pense que l'on aurait tout intérêt à introduire cette technique du fil d'ariane dans yacs. Cela permet d'accroitre les performances et de simplifier le code à chaque fois qu'il faut manipuler une arborescence.
Par exemple, imaginez que l'on veuille afficher l'arborescence des sections dont on est le propriétaire. Cela revient à appliquer un filtre sur l'arborescence du site pour ne faire apparaître que les sections que je possède.
Actuellement, cela nécessite autant de requêtes que ce qui est nécessaire pour construire l'arborescence complète. Avec la technique de mémorisation du fil d'ariane, une seule requete suffit 
Idem si l'on veut reconstituer l'arborescence des pages du site qui ont été créés ces 6 derniers mois (sympa comme vu synthétique des nouveautés...)
Un autre exemple : vous voulez savoir si une page fait partie de la branche "untel". Là encore, une seule requête suffit au lieu de devoir écrire un traitement récursif.
A noter...
Que Bernard utilise déjà cette technique à base de fil d'ariane avec les catégories. Avez-vous remarqué à qu'elle vitesse s'affiche la page avec la liste déroulante de toutes les catégories ?
Par contre, ce ne sont pas les identifiant qui ont été mémorisés mais directement leur libellé. C'est bien pour les performances mais bonjour le boulot de mise à jour de la base de données lorsqu'une catégorie "mère" est renommée 
Alors ?
D'autres sont-ils intéressés pour étudier de plus près l'implémentation de cette technique dans Yacs ? (il y a peut être des difficultés auxquelles je n'ai pas pensé...)