Code Tips and Snippets


Pas encore membre ?
Cliquez ici pour vous inscrire.
Vous pourrez poster des commentaires.
Parcours rapide d'arbres stockés en bases de données
Posté par pk le Dimanche 14 Septembre 2014 à 15:23:22
Niveau 5 étoilesLangage phpMySQL

La méthode la plus simple pour stocker une arborescence en base de données est évidemment la structure de table ou chaque enregistrement représente un nœud, et où une colonne sert à préciser la clé du nœud parent.

C’est de loin la plus pratique pour toute manipulation sur l’arbre ( insérer, supprimer un nœud, etc.).
Le parcours de l’arbre se fait très facilement par une simple micro-fonction récursive.

L’inconvénient de son avantage ( et oui, c’est bien connu : chaque avantage possède 1 ou n inconvénients. ),
réside dans le fait que le parcours récursif en question nécessite à chaque appel l’exécution d’une requête SQL.

Heureusement, il existe une structure de base de données améliorée, qui permet un parcours ultra rapide de l’arborescence :
Une seule requête SQL suffit !

L’inconvénient de son avantage ( et oui, c’est bien connu : chaque avantage possède 1 ou n inconvénients. ),
réside dans le fait qu’une simple mise à jour de l’arborescence nécessite un re-calcul total de la structure.

Cette structure sera donc particulièrement adaptée lorsque les mises à jour sont peu fréquentes et que les accès doivent se faire très rapidement.

  • très indiqué : arborescence d’un site web ( on espère qu’il y a plus de lectures que de maj de la structure ).
  • pas indiqué : forum. (j’espère que vous comprendrez pourquoi...)

 

Le nom de cette structure est  Modified Preorder Tree Traversal que l’on peut traduire par Parcours préordonné modifié d'arbre.

Je ne vais pas ici ré-inventer le fil à couper le beurre, il vous suffira de googolifier pour trouver tout un tas de littérature sur le sujet.

Je peux citer ici l’article Storing Hierarchical Data in a Database qui traite particulièrement bien du sujet.

yakpro rulez!

Ce Site a été mis à jour le Mercredi 19 Janvier 2022 à 09:43:57