Gérer des structures arborescentes en base de données peut rapidement devenir un casse-tête.

Si vous avez déjà écrit des requêtes SQL avec des jointures récursives sur une même table pour parcourir une hiérarchie, vous savez de quoi je parle : des JOIN en cascade, des performances qui s'effondrent à mesure que l'arbre grandit.

Catégories, menus de navigation, organigrammes, commentaires imbriqués ... Les cas d'usage sont nombreux et méritent une solution plus élégante.

L'approche classique : la colonne parent_id

La solution la plus intuitive consiste à ajouter une colonne parent_id à votre table pour référencer le nœud parent :

1| id | name         | parent_id |
2|----|--------------|-----------|
3| 1  | Électronique | NULL      |
4| 2  | Smartphones  | 1         |
5| 3  | iPhone       | 2         |

Simple à comprendre, mais problématique à l'usage.

Pour récupérer tous les descendants d'un nœud, vous devez effectuer des requêtes récursives. En PHP, cela peut se traduit simplement par une boucle qui interroge la base à chaque niveau de profondeur.

Plus votre arbre est profond, plus le nombre de requêtes explose.

L'alternative : le modèle Nested Set

Le modèle Nested Set (ou "ensembles imbriqués") adopte une approche différente.

Chaque nœud possède deux valeurs numériques : _lft (left) et _rgt (right) qui encadrent tous ses descendants.

1| id | name         | _lft | _rgt | parent_id |
2|----|--------------|------|------|-----------|
3| 1  | Électronique | 1    | 10   | NULL      |
4| 2  | Smartphones  | 2    | 7    | 1         |
5| 3  | iPhone       | 3    | 4    | 2         |
6| 4  | Android      | 5    | 6    | 2         |
7| 5  | Ordinateurs  | 8    | 9    | 1         |

Visualisons cette numérotation sur l'arbre. Les valeurs _lft et _rgt correspondent à un parcours en profondeur, on descend par la gauche et on remonte par la droite :

1                  (1) Électronique (10)
2                           │
3              ┌────────────┴────────────┐
4              │                         │
5     (2) Smartphones (7)        (8) Ordinateurs (9)
6              │
7      ┌───────┴───────┐
8      │               │
9(3) iPhone (4)  (5) Android (6)

Le principe est simple : chaque nœud "encadre" ses descendants avec ses valeurs _lft et _rgt.

"Électronique" englobe tout l'arbre (1 à 10), "Smartphones" englobe ses enfants (2 à 7), tandis que les feuilles comme "iPhone" (3 à 4) n'encadrent qu'elles-mêmes.

Grâce à cette structure, une seule requête SQL suffit pour récupérer tous les descendants :

1SELECT * FROM categories WHERE _lft > 2 AND _rgt < 7

Les performances de lecture sont ainsi constantes, peu importe la profondeur de l'arbre.

Le compromis  ? Les opérations d'écriture (ajout, déplacement, suppression) nécessitent de recalculer les valeurs _lft et _rgt des nœuds affectés.

Ce modèle est donc idéal pour les structures lues fréquemment, mais modifiées rarement, comme les catégories d'un e-commerce ou les menus de navigation.

La librairie kalnoy/nestedset intègre ce modèle directement dans Eloquent, cela vous permettra de manipuler vos arbres avec une API fluide sans jamais vous soucier des calculs de _lft et _rgt.

Passons à l'action !

Le package s'installe dans votre projet via composer composer require kalnoy/nestedset, et ne nécessitera aucune configuration supplémentaire.

Vous devrez ensuite ajouter les colonnes nécessaires pour constituer les arbres N-aires dans vos tables d'arborescences. La méthode NestedSet::columns($table) ajoutera automatiquement ces colonnes pour vous :

• _lft : la valeur gauche du nœud
• _rgt : la valeur droite du nœud
• parent_id : la référence vers le nœud parent

Vous pouvez donc enrichir n'importe quelle table existante ou non.

 1<?php
 2 
 3use Kalnoy\Nestedset\NestedSet;
 4use Illuminate\Database\Migrations\Migration;
 5use Illuminate\Database\Schema\Blueprint;
 6use Illuminate\Support\Facades\Schema;
 7 
 8return new class extends Migration
 9{
10    /**
11     * Run the migrations.
12     */
13    public function up(): void
14    {
15        Schema::create('categories', function (Blueprint $table) {
16            $table->id();
17            $table->string('name');
18            NestedSet::columns($table); 
19            $table->timestamps();
20        });
21    }
22 
23    /**
24     * Reverse the migrations.
25     */
26    public function down(): void
27    {
28        Schema::dropIfExists('categories');
29    }
30};

Vous devrez également modifier votre modèle pour qu'il utilise le trait NodeTrait fourni dans le package. Ce trait incorpore toutes les fonctionnalités nécessaires pour la gestion du "Nested Set" à votre modèle Eloquent.

 1<?php
 2 
 3namespace App\Models;
 4 
 5use Kalnoy\Nestedset\NodeTrait;
 6use Illuminate\Database\Eloquent\Model;
 7 
 8class Category extends Model
 9{
10    use NodeTrait; 
11 
12    protected $fillable = [
13        'name',
14    ];
15}

Construire un catalogue de catégories

Pour illustrer les fonctionnalités du package, nous allons construire pas à pas le catalogue d'un site e-commerce spécialisé dans l'électronique.

1Électronique (la racine)
2├── Smartphones
3│   ├── iPhone
4│   └── Android
5└── Ordinateurs

Étape 1 : Créer la catégorie racine

Toute arborescence commence par une entité principale. Ici, nous créons "Électronique" qui servira de point d'entrée à nos catégories.

Lorsqu'un nœud est sauvegardé sans parent, le package le considère automatiquement comme un nœud racine :

1$root = new Category(['name' => 'Électronique']);
2$root->save();

Notre arbre contient maintenant un seul élément : Électronique (id: 1).

Étape 2 : Ajouter les sous-catégories principales

Un site e-commerce propose généralement plusieurs familles de produits. Nous allons ajouter deux sous-catégories à notre racine : "Smartphones" et "Ordinateurs".

La méthode appendToNode() permet de rattacher un nouveau nœud à un parent existant :

1$rootNode = Category::find(1);
2 
3$smartphones = new Category(['name' => 'Smartphones']);
4$smartphones->appendToNode($rootNode)->save();
5 
6$ordinateurs = new Category(['name' => 'Ordinateurs']);
7$ordinateurs->appendToNode($rootNode)->save();

Notre arbre possède maintenant trois éléments : Électronique → Smartphones (id: 2) et Ordinateurs (id: 3).

Étape 3 : Affiner avec des sous-sous-catégories

Les clients recherchent souvent des produits par marque ou système d'exploitation. Nous allons donc créer deux sous-catégories pour "Smartphones" : "iPhone" et "Android".

Le principe reste identique, nous rattachons simplement les nouveaux nœuds à "Smartphones" plutôt qu'à la racine :

1$smartphones = Category::find(2);
2 
3$iphone = new Category(['name' => 'iPhone']);
4$iphone->appendToNode($smartphones)->save();
5 
6$android = new Category(['name' => 'Android']);
7$android->appendToNode($smartphones)->save();

Notre catalogue est maintenant complet avec cinq catégories sur trois niveaux de profondeur.

Naviguer dans notre catalogue

Maintenant que notre catalogue est construit, voyons comment le parcourir efficacement. Le package offre plusieurs méthodes pour naviguer dans votre arbre hiérarchique.

Fil d'Ariane : récupérer les ancêtres

Sur une fiche produit, vous souhaitez afficher le fil d'Ariane pour aider l'utilisateur à se repérer. La méthode ancestorsOf() retourne tous les parents d'un nœud, du plus proche au plus éloigné :

1$ancestors = Category::ancestorsOf(4);

Pour notre catégorie "iPhone" (id: 4), nous obtenons : [Smartphones, Électronique]. Idéal pour afficher : Électronique > Smartphones > iPhone.

Menu latéral : récupérer les descendants

Pour construire un menu de navigation affichant toutes les sous-catégories d'une section, utilisez descendantsOf() :

1$descendants = Category::descendantsOf(1);

Pour notre racine "Électronique" (id: 1), nous obtenons : [Smartphones, Ordinateurs, iPhone, Android]. Toutes les catégories de notre catalogue sont ainsi accessibles en une seule requête.

Indentation : connaître la profondeur d'un nœud

Pour afficher correctement un menu avec indentation, vous avez besoin de connaître le niveau de chaque catégorie. La méthode withDepth() donne cette information :

1$depth = Category::withDepth()->find(2)->depth;

"Smartphones" (id: 2) retourne une profondeur de 1, car c'est un enfant direct de la racine.

1$depth = Category::withDepth()->find(4)->depth;

"iPhone" (id: 4) retourne une profondeur de 2, car c'est un petit-enfant de la racine.

Afficher le catalogue complet

Pour un menu de navigation ou une page de catégories, vous aurez besoin d'afficher l'intégralité de l'arbre avec sa structure hiérarchique. La méthode toTree() reconstruit la relation parent-enfant et permet un parcours récursif :

 1$traverse = function ($categories, $prefix = '-') use (&$traverse) {
 2    foreach ($categories as $category) {
 3        echo PHP_EOL . $prefix . ' ' . $category->name;
 4 
 5        $traverse($category->children, $prefix . '-');
 6    }
 7};
 8 
 9$rootNode = Category::find(1);
10$rootNode->load('children', 'descendants');

Selon votre besoin, plusieurs variantes s'offrent à vous.

Pour afficher uniquement les enfants directs de la racine (niveau 1), utilisez la relation children :

1$traverse($rootNode->children->toTree());
2 
3# - Smartphones
4# - Ordinateurs

Pour afficher tous les descendants sans inclure la racine, utilisez descendants() :

1$traverse($rootNode->descendants()->toTree());
2 
3# - Smartphones
4# -- iPhone
5# -- Android
6# - Ordinateurs

Pour afficher l'arbre complet incluant la racine, utilisez descendantsAndSelf() :

1$traverse($rootNode->descendantsAndSelf()->toTree());

Résultat :

1- Électronique
2-- Smartphones
3--- iPhone
4--- Android
5-- Ordinateurs

Obtenir les arborescences des nœuds descendants

Le package propose également des méthodes statiques pratiques pour obtenir l'arborescence des nœuds descendants :

Descendants d'un nœud sans le nœud lui-même :

1$tree = Category::descendantsOf($rootNode->id)->toTree();

Descendants incluant le nœud lui-même :

1$tree = Category::descendantsAndSelf($rootNode->id)->toTree();

Sécuriser les écritures avec les transactions

Nous avons vu en introduction que le Nested Set privilégie les performances en lecture au détriment des écritures. Chaque insertion ou déplacement de nœud déclenche un recalcul des valeurs _lft et _rgt sur une partie de l'arbre.

Si une erreur survient en plein milieu de ce recalcul, votre arbre se retrouve dans un état incohérent : certains nœuds auront été mis à jour, d'autres non. Pour éviter ce scénario catastrophe, encapsulez vos opérations d'écriture dans une transaction :

1use Illuminate\Support\Facades\DB;
2 
3DB::transaction(function () use ($parent) {
4    $node1 = new Category(['name' => 'Tablettes']);
5    $node1->appendToNode($parent)->save();
6 
7    $node2 = new Category(['name' => 'Accessoires']);
8    $node2->appendToNode($parent)->save();
9});

En cas d'échec, la transaction annule toutes les modifications et votre arbre reste intact.

Le package ne démarre pas automatiquement de transaction pour vous laisser le contrôle. Pensez également à utiliser un moteur de base de données qui supporte les transactions, comme InnoDB pour MySQL.

Pour aller plus loin

Nous avons couvert les fonctionnalités essentielles du package, mais d'autres possibilités s'offrent à vous :

• Déplacer un nœud : $node->appendToNode($newParent)->save()
• Supprimer un sous-arbre : $node->delete() supprime le nœud et tous ses descendants
• Reconstruire l'arbre : Category::fixTree() recalcule les valeurs _lft et _rgt
• Vérifier si un nœud est un ancêtre : $node->isAncestorOf($other)
• Vérifier si un nœud est un descendant : $node->isDescendantOf($other)

Dans vos models Eloquent, vous n'avez plus qu'à personnaliser des scopes qui vous permettront de filtrer vos arbres selon vos besoins métier.

Vous pourrez également gérer plusieurs arbres dans une même table grâce au support du multi-tree.

Enfin, la méthode fixTree() vous sera utile pour reconstruire les valeurs _lft et _rgt en cas de corruption des données.

À votre tour de cultiver vos arbres N-aires !

Antoine Benevaut

PHP & Laravel Consultant - Lead Developer, Paris / Passionate / Cat lover / #laravel 😍