Réponse.

Travailler avec des structures hiérarchiques — un classique des bases de données relationnelles. Exemples : répertoires, menus en arbre, structures organisationnelles.

Historique de la question : Les bases de données adoptent un modèle tabulaire. Pour les données en arbre, plusieurs approches existent, chacune avec ses avantages et inconvénients.

Problème : Le modèle standard parent_id entraîne des SELECT récursifs lents. Les tâches réelles (recherche de tous les descendants, chemins, recalcul des sous-arbres) nécessitent une optimisation.

Solution :

Liste d'adjacence — simple référence à parent_id.
Chemin matérialisé — une chaîne représentant le chemin complet.
Ensembles imbriqués — stockage des limites gauche/droite (left/right), ce qui permet d'extraire facilement les sous-arbres.
Table de fermeture — une table séparée de relations (from->to) reflétant toutes les relations dans l'arbre.

Exemple de code pour le chemin matérialisé (PostgreSQL) :

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    path TEXT
);

-- Exemple de stockage du path : '1/2/5/' (racine/sous-catégorie/courant)
SELECT * FROM categories WHERE path LIKE '1/2/%'; -- tous les descendants de 2

Exemple de code pour les ensembles imbriqués :

CREATE TABLE nested_categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

-- Noeuds enfants
SELECT * FROM nested_categories WHERE lft > 2 AND rgt < 15;

Caractéristiques clés :

La liste d'adjacence est pratique pour les structures en arbre simples (faible imbrication).
Le chemin matérialisé — extraction rapide des sous-arbres, facile à mettre en œuvre.
Les ensembles imbriqués — obtention instantanée de tous les descendants, lecture rapide, mais modification complexe.

Questions pièges.

Peut-on simplement utiliser une SELECT imbriquée avec parent_id pour trouver tous les descendants à une profondeur arbitraire ?

Cela fonctionne uniquement pour des profondeurs faibles. Pour une recherche récursive, il faut soit un CTE récursif (WITH RECURSIVE), soit des schémas plus complexes, car des JOIN simples entraînent un grand nombre d'appels et une mauvaise performance.

Exemple :

WITH RECURSIVE cte AS (
    SELECT id, parent_id, name FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id, c.name
    FROM categories c
    INNER JOIN cte ON c.parent_id = cte.id
)
SELECT * FROM cte;

Pourquoi l'arbre moléculaire (ensembles imbriqués) extrait-il rapidement un sous-arbre mais est-il lent à ajouter/supprimer des noeuds ?

Lors d'un changement dans l'arbre, il faut modifier les valeurs lft/rgt dans de nombreuses lignes (la portée de ce changement — toutes les valeurs supérieures à l'insertion/suppression). Idéal pour la lecture, mais pour des modifications fréquentes, utilisez d'autres méthodes.

Quand utiliser la table de fermeture plutôt que parent_id ou le chemin matérialisé ?

La table de fermeture fonctionne parfaitement pour des requêtes multiples sur les descendants à n'importe quel niveau et pour le recalcul régulier des relations. Inconvénient — elle nécessite plus d'espace.

Exemple :

CREATE TABLE closure (
    ancestor INT,
    descendant INT,
    depth INT
);

Erreurs typiques et anti-modèles

Stockage de l'arbre uniquement via parent_id lorsqu'une recherche rapide de structures imbriquées est nécessaire.
Recalcul manuel des chemins ou des valeurs lft/rgt sans fonctions auxiliaires.
Absence d'indexation des colonnes clés (parent_id/path/lft/rgt).

Exemple de la vie réelle

Cas négatif

Dans un magasin en ligne, les catégories sont implémentées via parent_id. Tous les niveaux imbriqués sont définis manuellement, la recherche des sous-catégories se fait par des SELECT imbriqués.

Avantages :

Simplicité, pas besoin de support avancé.

Inconvénients :

La performance tombe même à 3-4 niveaux d'imbrication.
Les opérations de déplacement des noeuds — peu évidentes, entraînent des erreurs logiques.

Cas positif

Utilisation du chemin matérialisé ou de la table de fermeture. Toutes les requêtes sur les catégories imbriquées sont instantanées, le recalcul — par des scripts groupés.