Gestion d’une structure d’arbre sous MySQL


  • Introduction :

Il est très courant d’avoir à stocker une structure d’arbre dans une base de données. Par exemple, pour enregistrer l’organisation hiérarchique d’une entreprise ou bien pour représenter les catégories et sous-catégories des articles d’un site web.

La façon la plus simple de procéder est d’ajouter simplement à la table concernée un champ « identifiant_parent » qui servira à stocker l’identifiant du noeud parent. Ainsi, pour stocker l’arbre suivant :

      A
  ---------
  |       |
  B       C
        -----
        |   |
        D   E
      -----
      |   |
      F   G

nous aurions les enregistrements suivants :

identifiant    identifiant_parent
A                 NULL
B                 A
C                 A
D                 C
E                 C
F                 D
G                 D

Le noeud « A » qui est la racine de l’arbre n’a évidemment aucun parent c’est pourquoi l’identifiant du parent est dans ce cas mis à NULL.

Cette technique de représentation d’un arbre a comme avantage sa très grande simplicité. Elle a par contre l’inconvénient de nécessiter pour certains traitements l’envoi de plusieurs requêtes SQL de manière récursive. En effet, pour retrouver tous les noeuds enfants de « C », il n’est pas possible de le faire directement via une seule requête SQL. Il faut tout d’abord récupérer les enfants de « C » puis, pour chaque enregistrements trouvés, récupérer à leur tour leurs enfants.

Nous allons donc voir une autre méthode plus complexe mais aussi plus performante pour stocker dans une base SQL une structure d’arbre.

  • Le ver sur la branche :

Au lieu d’utiliser la représentation classique d’un arbre, on peut aussi imaginer un arbre comme une imbrication d’ensembles. La racine est l’ensemble le plus grand qui regroupe tous les éléments, puis ses enfants sont des sous-ensembles plus petits qui regroupents leurs enfants, etc…

Graphiquement, l’arbre vu précédemment se représenterait ainsi :

------------------------ A ------------------------
|          B               |                      |
|                          |--------- C ----------|
|                          |                E     |
|                          |--- D ----            |
|                          | F     G |            |
|-------------------------------------------------|

L’ensemble « A » est le plus grand et contient « B » et « C » ainsi que leurs enfants. L’ensemble « C » contient à son tour « D » et « E » et leurs enfants, etc…

Pour représenter ces ensembles, il suffit d’utiliser cette fois deux champs de type entier que nous appellerons « gauche » et « droite ». Ils indiqueront en fait la grandeur de l’ensemble concerné. On peut aussi imaginer un ver qui parcourt l’arbre en partant de la racine et visite chaque noeud deux fois (une fois à gauche et une fois à droite). A chaque visite, il place dans le champ (gauche ou droite) la valeur d’un compteur qui augmente de 1 à chaque fois.

Pour représenter notre arbre, nous aurions donc cette fois-ci les enregistrements suivants :

identifiant    gauche    droite
A                1         14
B                2         3
C                4         13
D                5         10
E                11        12
F                6         7
G                8         9

Et pour revenir à notre précédente illustration graphique de l’arbre, cela donnerait :


         1 A 14
       -----------
       |         |
    2 B 3      4 C 13
            ----------
            |        |
          5 D 10  11 E 12
         --------
         |      |
       6 F 7  8 G 9

N.B. : pour le noeud  » B « , il faut lire  » 2 B 3  » (l’affichage n’est pas forcément correct…).

On voit d’emblée que cette représentation offre des propriétés intéressantes pour nos futures requêtes SQL. Par exemple :

– La racine est toujours le noeud dont l’enregistrement « gauche » est égal à la valeur 1.
– Pour sélectionner tous les enfants d’un noeud donné, il suffit de récupérer tous ceux dont le champ « gauche » est supérieur à la valeur du champ « gauche » de ce noeud et dont le champ « droite » est inférieur à la valeur du champ « droite » de ce noeud.
– Les feuilles (les noeuds sans enfants) sont les éléments dont la valeur du champ « droite » moins la valeur du champ « gauche » est égal à 1.

  • Implémentation sous MySQL :
CREATE TABLE arbre (
  id BIGINT NOT NULL AUTO_INCREMENT,

  gauche BIGINT DEFAULT NULL,
  droite BIGINT DEFAULT NULL,

  ref CHAR(5) DEFAULT NULL,

  id_parent BIGINT NOT NULL DEFAULT 0,

  PRIMARY KEY (id),
  UNIQUE (gauche),
  UNIQUE (droite),
  KEY (ref),
  KEY (id_parent)
);

Nous retrouvons nos champs « gauche » et « droite ». Le champ « ref » contiendra la clef vers les données qui seront stockées dans une autre table. Ici, nous nous contenterons de placer dans ce champ une simple chaîne de caractères afin d’illustrer nos propos. Enfin, le champ « id_parent » indiquera l’identifiant du noeud parent. Ce dernier champ n’est pas obligatoire pour gérer l’arbre mais il permet toutefois d’avoir un lien direct vers le parent ce qui peut simplifier certaines requêtes.

  • Procédure pour l’ajout d’un noeud :
delimiter //

CREATE PROCEDURE ajout (IN id_parent_noeud BIGINT, IN ref_noeud CHAR(5))
MODIFIES SQL DATA
BEGIN
DECLARE gauche_parent, droite_parent BIGINT DEFAULT NULL;

INSERT INTO arbre (ref, id_parent) VALUES (ref_noeud, id_parent_noeud);

SELECT gauche INTO gauche_parent FROM arbre WHERE id = id_parent_noeud;
SELECT droite INTO droite_parent FROM arbre WHERE id = id_parent_noeud;

UPDATE arbre SET gauche = gauche + 2
  WHERE gauche > gauche_parent
  ORDER BY gauche DESC;

UPDATE arbre SET droite = droite + 2
  WHERE droite >= droite_parent OR (droite > gauche_parent + 1 AND droite < droite_parent)
  ORDER BY droite DESC;

UPDATE arbre SET gauche = gauche_parent + 1, droite = gauche_parent + 2 WHERE ref = ref_noeud;
END;

delimiter ;

La procédure prend deux paramètres. « id_parent_noeud » indique l’identifiant du noeud parent pour le noeud qui sera ajouté. « ref_noeud » contient la clef vers les données associées au nouveau noeud.

On insère tout d’abord ce nouveau noeud avec les données passées en paramètres. Puis on décale les valeurs « gauche » et « droite » des autres noeuds de manière à pouvoir placer le nouveau noeud. On met enfin à jour les valeurs « gauche » et « droite » du nouveau noeud. Notez qu’avec la méthode de décalage choisie le noeud le plus récemment ajouté possède les indices « gauche » et « droite » les plus faibles parmi tous ses frères. A l’inverse, le noeud ajouté en premier aura toujours les indices « gauche » et « droite » les plus élevés parmis tous ses frères.

Pour utiliser cette procédure dans une requête SQL :

INSERT INTO arbre (id, gauche, droite, ref, id_parent) VALUES (1,1,2,'A',0);
CALL ajout(1,'B');
CALL ajout(1,'C');

On insère en premier lieu le noeud racine « A ». Puis on lui ajoute deux fils « B » et « C ».

Publicités

17 réflexions sur “Gestion d’une structure d’arbre sous MySQL

  1. Bonjour,

    Voilà un moment que je cherchais une solution de ce genre. Cela m’a l’air très intéressant. Le but étant de gérer les catégorie, sous catégories.
    Joli blog, contenu très bien présenté et bien décrit, je teste et je reviens…

    merci

    Olivier

  2. En fait je me suis un peu emballer je ne comprend strictement rien à ça :

    # A 1 14
    # B 2 3
    # C 4 13
    # D 5 10
    # E 11 12
    # F 6 7
    # G 8 9

    help….

    @+

    olivier

  3. Ah si enfin j’ai compris !!
    En fait on parcoure d’abord à gauche jusqu’au dernier fils,
    et on numérote d’abord les branches gauche du nœud

    Pour la partie gauche ça donne : 1 A X | 2 B x

    Puis on remonte puisque plus de noeud : 1 A X | 2 B 3

    et on passe à droite de la racine : 4 C X | 5 D X | 6 F X

    on remonte sur D, on descend sur G :

    4 C X | 5 D X | 6 F 7 | 8 G X

    Puis on remonte encore de G vers C :

    4 C X | 5 D 10 | 6 F 7 | 8 G 9

    etc….

    Bon c’est déjà ça

  4. Cette article est très intéressant. Je cherche actuellement à développer un blog personnel avec gestion d’articles organisés par catégories.

    J’ai très bien compris la technique utilisé ( le ver sur la branche).
    Par contre, je me galère pour récupéré les informations de la table. Par exemple je souhaite récupérer une catégorie et ses catégories enfants. Une requête récursive serait à mon avis le plus performant et plus « simple » à mettre en ouvre qu’une multitudes de requêtes brouillons.

    Mais en MySQL 5, je l’avoue, je ne vois pas comment.
    pourriez-vous éclairer ma lanterne ?

    Merci

    Marc-antoine

    • Justement avec cette technique (et c’est tout l’intérêt !) vous pouvez récupérer très simplement et avec une seule requête une catégorie donnée et ses enfants. Pour reprendre l’exemple de l’article, pour sélectionner la catégorie « C » et ses enfants, il suffit d’utiliser la requête SQL suivante :

      SELECT * FROM arbre WHERE gauche >= 4 AND droite <= 13
      

      Simple et efficace !

  5. Bonjour,

    j’arrive très longtemps après la bataille, mais ce modèle reste intéressant (y en a-t-il de plus récent / performant ?).

    Je me demande simplement à quoi pourrait ressembler la fonction « suppression » pour supprimer un noeud ?

    Ensuite, à quoi peut ressembler une requête cherchant tous les enfants de la catégorie C par exemple (ne connaissant que le libellé de la catégorie) ?

    En gros comment envisager la gestion d’une telle structure d’arbre ?

    Merci.

    • Bonjour,

      Concernant d’autres modèles, vous pouvez consulter https://communities.bmc.com/communities/docs/DOC-9902 par Vadim Tropashko. D’autres articles par ce même auteur sur ce sujet sont disponibles sur internet. Le modèle décrit paraît extrêmement intéressant. Je n’ai toutefois jamais tenté de le mettre en pratique.

      Pour la suppression d’un élément, vous pouvez consulter http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ (la section « Deleting Nodes »). Cet article donne d’ailleurs une implémentation complète sous MySQL de ce type de structure d’arbre.

      Pour rechercher tous les enfants d’une catégorie C, en résumé :
      1 – Un premier SELECT pour récupérer les champs « gauche » et « droite » de la catégorie C. Dans l’exemple donné, ce sera respectivement 4 et 13.
      2 – Le SELECT suivant :

      SELECT * FROM arbre WHERE gauche > 4 AND droite < 13

      permet de récupérer tous les enfants de la catégorie C.

  6. bonjour ,
    ce code ne fonctionne pas si on veut suivre à la lettre la structure du vert sur la branche .

    Il m’insère les valeurs à l’inverse , c à dire le nœud de valeur gauche et droite (2,3) prend la place du nœud (4,5) , c à dire si on commence à lire à droite on tombe sur le nœud (2,3) au lieu du nœud (4,5) .

    quelque précision ?

    • Bonjour,

      Après les instructions suivantes :

      mysql> INSERT INTO arbre (id, gauche, droite, ref, id_parent) VALUES (1,1,2,'A',0);
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(1,'B');
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(1,'C');
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(2,'D');
      Query OK, 1 row affected (0.01 sec)
      
      mysql> CALL ajout(2,'E');
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(2,'F');
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(3,'G');
      Query OK, 1 row affected (0.00 sec)
      
      mysql> CALL ajout(3,'H');
      Query OK, 1 row affected (0.01 sec)
      

      Voici ce que j’ai dans la table :

      mysql> select * from arbre;
      +----+--------+--------+------+-----------+
      | id | gauche | droite | ref  | id_parent |
      +----+--------+--------+------+-----------+
      |  1 |      1 |     16 | A    |         0 |
      |  2 |      8 |     15 | B    |         1 |
      |  3 |      2 |      7 | C    |         1 |
      |  4 |     13 |     14 | D    |         2 |
      |  5 |     11 |     12 | E    |         2 |
      |  6 |      9 |     10 | F    |         2 |
      |  7 |      5 |      6 | G    |         3 |
      |  8 |      3 |      4 | H    |         3 |
      +----+--------+--------+------+-----------+
      8 rows in set (0.00 sec)
      

      Ici l’insertion se fait toujours à gauche. Donc le noeud le plus récemment ajouté se trouve toujours à gauche. Et l’insertion de ce noeud fait que les valeurs gauche et droite de ses noeuds « frères » sont incrémentées. Cela reste cohérent avec le parcours du ver qui se fait lui aussi toujours à gauche.

      Par ailleurs, je dirais que si l’ordre des noeuds d’un même parent a une importance, il doit s’appuyer sur un autre champ explicite du noeud. L’algo présentée ici n’a pas pour vocation de maintenir un ordre sur les noeuds d’un même parent. Il maintient simplement la structure arborescente des noeuds.

      • OK c’est ce qu’il me semblait , alors moi le problème que j’ai rencontré nécessite une insertion à droite pour garder l’organisation demandée .
        Maintenant après une longue recherche j’est réussis à faire l’algorithme de l’insertion à droite , ça ne me dérange pas de le poster ici pour servir aux autres qui ont eu la meme galére que moi j’attends juste ta confirmation .

        et merci quand même pour ton code vraiment ça m’a servis pour la compréhension.

  7. ok :p

    donc pour commencer :
    project_tree est le nom de ma table qui stocke les informations suivante
    *project_tree_id , project_id , project_tree_left , project_tree_right ,project_tree_parent_id .
    ne soyez pas trop surprit de ma convention de nommage des colonnes de mes tables je suis fan de la convention zend :p

    project_id est l’id du projet enfin de l’article que je vais ajouter ,les autres colonnes normalement leurs noms sont explicites .
    $parentId c l’attribut qui contient l’Id du parent , c’est écrit en php .

    et voiçi le code :

    ' LOCK TABLE project_tree WRITE ; '
    . ' SELECT @ParentRgt := project_tree_right FROM project_tree WHERE project_id = ' . $parentId . ' ; '
     . ' INSERT INTO project_tree (project_tree_id, project_id, project_tree_left , project_tree_right,project_tree_parent_id )'
         . ' VALUES ('
             ' NULL,' . $this->_projectId . ', @ParentRgt + 1, @ParentRgt + 2 ,'.$parentId .' ) ; '
                            . ' UPDATE project_tree '
                            . ' SET project_tree_right = project_tree_right + 2'
                            . ' WHERE project_tree_right >= @ParentRgt ;'
                            . ' UPDATE project_tree'
                            . ' SET project_tree_left = project_tree_left + 2 '
                            . ' WHERE project_tree_left > @ParentRgt ; '
                            . ' UPDATE project_tree '
                            . ' SET project_tree_left = @ParentRgt, project_tree_right = @ParentRgt + 1 '
                            . ' WHERE project_id = ' . $this->_projectId . ' ; '
                            . ' UNLOCK TABLES ; ';
    

    Voilà a+

  8. Cette méthode du ver à l’air très performante, je vais essayer de la mettre en place.
    Par contre je me pose une question, si je souhaites gérer un ordre de tri pour les branches d’une même profondeur (ex: champ ordre int) :

    Quelle serait la requête SQL à utiliser ?

    • Si vous parlez d’un ordre sur tous les noeuds enfants d’un même noeud parent, cela ne change rien aux requêtes SQL de gestion de l’arbre (ajout d’un noeud, suppression d’un noeud…). En effet, ces requêtes s’occupent uniquement de gérer la structure arborescente (qui est enfant/parent de qui). Par contre, lorsque vous allez récupérer vos données avec des requêtes SELECT, il sera nécessaire d’ajouter un « ORDER BY ordre » pour obtenir la liste des enregistrements dans l’ordre que vous souhaitez.

      • Désolé je m’étais mal exprimé, (en considérant que l’ordre est le dernier numéro de la référence)
        il faudrait que ma requête me retour le jeu d’enregistrement dans cet ordre :

        P1
        P1.1
        P1.1.1
        P1.1.2
        P1.2
        P1.3
        P2
        P2.1
        P2.2
        P2.2.1
        P2.2.2
        P3
        P3.1
        P3.1.1
        P3.2

      • Une première solution qui s’en approche est d’utiliser un tri sur le champ « gauche » puisqu’il est incrémenté dans l’ordre de parcours en profondeur à gauche :

        SELECT * FROM arbre ORDER BY gauche;

        Par contre, comme la méthode d’insertion utilisée place le dernier noeud tout à gauche, les enfants d’un parent seront classés du plus récemment inséré au plus ancien.

        Autre solution qui apparemment n’a pas ce problème :

        SELECT P.* FROM arbre AS P
        LEFT OUTER JOIN arbre AS R ON R.gauche =
        (SELECT MAX(S.gauche)
        FROM arbre AS S
        WHERE P.gauche > S.gauche
        AND P.gauche < S.droite)
        ORDER BY P.droite DESC;

        Cette requête vient de la présentation disponible sur http://fr.slideshare.net/quipo/trees-in-the-database-advanced-data-structures (page 75).

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s