Il y a plusieurs méthodes pour stocker une hiérarchie de données dans une base de données MySQL [1], elles sont toutes les deux décrites dans ce document [2]. Il est assez complet, mais il me manque cependant quelques requêtes pour la manipulation des données selon la méthode de l'arbre. On va donc mettre en place ces requêtes.

Première étape : mise en place de l'environnement

Pour cela, nous avons besoin d'une table et de quelques données.

  1. /* Création de la table */
  2. CREATE TABLE tree
  3. ( id int AUTO_INCREMENT
  4. , name varchar(3)
  5. , lft int
  6. , rgt int
  7. , PRIMARY KEY (id));
  8.  
  9. /* Insertion des données */
  10. INSERT INTO tree (name,lft,rgt)
  11. VALUES ('A',1,14)
  12. , ('B',2,7)
  13. , ('D',3,4)
  14. , ('E',5,6)
  15. , ('C',8,13)
  16. , ('F',9,10)
  17. , ('G',11,12);

Maintenant, nous pouvons vérifier la structure de notre arbre avec la requête suivante [3]:

  1. /* Affichage de l'arbre de manière visuelle */
  2. SELECT concat(repeat('----',(count(p.name)-1)),n.name) AS NAME
  3. , n.lft AS LFT
  4. , n.rgt AS RGT
  5. , n.id AS ID
  6. FROM tree AS n
  7. , tree AS p
  8. WHERE n.lft BETWEEN p.lft
  9. AND p.rgt
  10. GROUP BY n.id
  11. ORDER BY n.lft;

Ce qui nous donne ceci :

+-----------+------+------+----+
| NAME      | LFT  | RGT  | ID |
+-----------+------+------+----+
| A         |    1 |   14 |  1 |
| ----B     |    2 |    7 |  2 |
| --------D |    3 |    4 |  3 |
| --------E |    5 |    6 |  4 |
| ----C     |    8 |   13 |  5 |
| --------F |    9 |   10 |  6 |
| --------G |   11 |   12 |  7 |
+-----------+------+------+----+
7 rows in set (0.00 sec)

Deuxième étape : ajouter un élément

J'ai décidé de n'ajouter un élément que sous un autre élément. Donc le nouvel élément se trouvera être le dernier enfant de son parent. Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément parent */
  5. SELECT @parentRight := rgt
  6. FROM tree
  7. WHERE name = 'B';
  8.  
  9. /* Mise à jour des bornes droites des éléments concernés */
  10. UPDATE tree
  11. SET rgt = rgt + 2
  12. WHERE rgt >= @parentRight;
  13.  
  14. /* Mise à jour des bornes gauches des éléments concernés */
  15. UPDATE tree
  16. SET lft = lft + 2
  17. WHERE lft >= @parentRight;
  18.  
  19. /* Insertion du nouvel élément */
  20. INSERT INTO tree (name,lft,rgt)
  21. VALUES ('ZZZ',@parentRight,@parentRight + 1);
  22.  
  23. /* Suppression des verrous */
  24. UNLOCK TABLES;

Ce qui nous donne ceci :

+-------------+------+------+----+
| NAME        | LFT  | RGT  | ID |
+-------------+------+------+----+
| A           |    1 |   16 |  1 |
| ----B       |    2 |    9 |  2 |
| --------D   |    3 |    4 |  3 |
| --------E   |    5 |    6 |  4 |
| --------ZZZ |    7 |    8 | 11 |
| ----C       |   10 |   15 |  5 |
| --------F   |   11 |   12 |  6 |
| --------G   |   13 |   14 |  7 |
+-------------+------+------+----+
8 rows in set (0.00 sec)

Troisième étape : déplacer un élément

J'ai décidé de ne gérer que les déplacements vers un parent qui ne fait pas parti des enfants de l'élément. Pour prendre le cas précédent, je peux déplacer B vers C mais pas vers ZZZ. Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément à déplacer */
  5. SELECT @nodeLeft := lft
  6. , @nodeRight := rgt
  7. , @nodeRange := rgt - lft + 1
  8. FROM tree
  9. WHERE name = 'ZZZ';
  10.  
  11. /* Récupération des informations du nouvel élément parent */
  12. SELECT @newParentLeft := lft
  13. , @newParentRight := rgt
  14. FROM tree
  15. WHERE name = 'C';
  16.  
  17. /* Calcul de la valeur de déplacement de l'élément à déplacer */
  18. SELECT @offsetRange := @newParentRight - @nodeRight - 1 + IF( sign( @newParentRight - @nodeRight ) < 1 , @nodeRange , 0 );
  19.  
  20. /* Calcul de la borne gauche de déplacement des autres éléments */
  21. SELECT @offsetLeft := IF( sign( @offsetRange ) = 1 , @nodeRight , @newParentRight );
  22.  
  23. /* Calcul de la borne droite de déplacement des autres éléments */
  24. SELECT @offsetRight := IF( sign( @offsetRange ) = 1 , @newParentRight - 1 , @nodeLeft - 1 );
  25.  
  26. /* Calcul de la valeur de déplacement des autres éléments */
  27. SELECT @signedNodeRange := sign( @offsetRange ) * @nodeRange;
  28.  
  29. /* Exclusion temporaire de l'élément à déplacer */
  30. UPDATE tree
  31. SET lft = -lft
  32. , rgt = -rgt
  33. WHERE lft >= @nodeLeft
  34. AND rgt <= @nodeRight;
  35.  
  36. /* Mise à jour des bornes droites des éléments concernés */
  37. UPDATE tree
  38. SET rgt = rgt - @signedNodeRange
  39. WHERE rgt BETWEEN @offsetLeft AND @offsetRight;
  40.  
  41. /* Mise à jour des bornes gauches des éléments concernés */
  42. UPDATE tree
  43. SET lft = lft - @signedNodeRange
  44. WHERE lft BETWEEN @offsetLeft AND @offsetRight;
  45.  
  46. /* Repositionnement de l'élément à déplacer */
  47. UPDATE tree
  48. SET lft = -lft + @offsetRange
  49. , rgt = -rgt + @offsetRange
  50. WHERE rgt < 0;
  51.  
  52. /* Suppression des verrous */
  53. UNLOCK TABLES;

Ce qui nous donne ceci :

+-------------+------+------+----+
| NAME        | LFT  | RGT  | ID |
+-------------+------+------+----+
| A           |    1 |   16 |  1 |
| ----B       |    2 |    7 |  2 |
| --------D   |    3 |    4 |  3 |
| --------E   |    5 |    6 |  4 |
| ----C       |    8 |   15 |  5 |
| --------F   |    9 |   10 |  6 |
| --------G   |   11 |   12 |  7 |
| --------ZZZ |   13 |   14 | 11 |
+-------------+------+------+----+
8 rows in set (0.00 sec)

Quatrième étape : supprimer un élément

Pour faire cela, il suffit de lancer ces quelques requêtes :

  1. /* Verrouillage en écriture de la table*/
  2. LOCK TABLE tree WRITE;
  3.  
  4. /* Récupération des informations de l'élément à supprimer */
  5. SELECT @nodeRight := rgt
  6. , @nodeLeft := lft
  7. , @range := rgt - lft + 1
  8. FROM tree
  9. WHERE name = 'ZZZ';
  10.  
  11. /* Suppression de l'élément */
  12. DELETE FROM tree
  13. WHERE lft >= @nodeLeft
  14. AND rgt <= @nodeRight;
  15.  
  16. /* Mise à jour des bornes droites des éléments concernés */
  17. UPDATE tree
  18. SET rgt = rgt - @range
  19. WHERE rgt >= @nodeRight;
  20.  
  21. /* Mise à jour des bornes gauches des éléments concernés */
  22. UPDATE tree
  23. SET lft = lft - @range
  24. WHERE lft >= @nodeRight;
  25.  
  26. /* Suppression des verrous */
  27. UNLOCK TABLES;

Ce qui nous donne ceci :

+-----------+------+------+----+
| NAME      | LFT  | RGT  | ID |
+-----------+------+------+----+
| A         |    1 |   14 |  1 |
| ----B     |    2 |    7 |  2 |
| --------D |    3 |    4 |  3 |
| --------E |    5 |    6 |  4 |
| ----C     |    8 |   13 |  5 |
| --------F |    9 |   10 |  6 |
| --------G |   11 |   12 |  7 |
+-----------+------+------+----+
7 rows in set (0.00 sec)

Et voila. J'ai fait les tests de déplacement et de suppression d'arbres et ça fonctionne correctement. Ne me croyez pas sur parole, essayez. Par contre, vous avez remarqué que je n'ai pas fait de test de validation des données. Si vous voulez allez plus loin, je vous laisse le soin de les faire.

Notes

[1] Pour les autres bases de données aussi, mais ce n'est pas le propos du jour.

[2] La lecture de ce document est un pré-requis pour la compréhension de ce qui va suivre.

[3] Nous utiliserons cette requête pour valider l'ensemble des résultats ultérieurs.