Réponse.

Travailler avec des arbres et des hiérarchies est un cas courant lors de la programmation en SQL : catalogues de produits, structure organisationnelle, menus. À l'origine, la plupart des SGBD ne supportaient qu'une référence au parent (ParentId), mais avec le temps, des méthodes alternatives ont émergé - ensembles imbriqués et chemins (Path), ainsi que des requêtes récursives via CTE.

Problème de l'approche Parent-Enfant traditionnelle - lenteur lors de la traversée de grandes hiérarchies ; les sélections à un niveau plus profond que 2-3 entraînent un nombre d'JOIN exponentiel. Des techniques plus complexes (Nested Sets, Path Enumeration) accélèrent les traversées massives, mais compliquent les insertions/suppressions.

Solution - choix du modèle de stockage optimal pour la tâche spécifique :

Pour des modifications rares et une lecture massive : Nested Sets (enregistrement des limites gauche/droite dans les nœuds pour une recherche rapide des descendants)
Pour des modifications fréquentes : Adjacency List + CTE récursif
Pour une recherche rapide de chemin - Path et stockage du chemin complet dans une chaîne

Exemple de recherche récursive d'un sous-arbre via CTE :

WITH RecursiveTree AS (
  SELECT id, parent_id, name, 0 as level
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.parent_id, c.name, rt.level + 1
  FROM categories c
  INNER JOIN RecursiveTree rt ON c.parent_id = rt.id
)
SELECT * FROM RecursiveTree;

Caractéristiques clés :

Choix de la structure de stockage en fonction du scénario (Parent-Enfant, Nested Sets, Path)
Utilisation de CTE récursifs pour des profondeurs arbitraires
Évaluation de la fréquence des modifications et des lectures pour adapter la méthode optimale

Questions pièges.

Peut-on remplacer le stockage des arbres par une seule table dénormalisée avec un seul niveau de références, si la profondeur est fixe ?

Seulement si la profondeur est faible et toujours fixe (2-3 niveaux) - sinon, les JOIN deviennent incontrôlables, rendant le traitement des modifications complexe.

Et le CTE ne "tombera pas" avec de grands arbres - y a-t-il des limites de pile, de profondeur de récursion ?

Oui, la plupart des SGBD imposent des limites de profondeur de récursion (par exemple, 100/32767). Pour des arbres de plus de 1000 niveaux, une gestion manuelle de la profondeur ou des algorithmes de traversée/splitting personnalisés seront nécessaires.

Les Nested Sets sont-ils la solution à tous les problèmes ?

Non, les nested sets trouvent instantanément tous les descendants, mais l'insertion/suppression nécessite une mise à jour massive de tous les index gauche/droite - c'est lent avec un grand nombre de modifications fréquentes.

Exemple d'insertion (simplifié) :

UPDATE tree SET lft = lft + 2 WHERE lft > @parent_right;
UPDATE tree SET rgt = rgt + 2 WHERE rgt >= @parent_right;
INSERT INTO tree(id, name, lft, rgt) VALUES(@new_id, @name, @parent_right, @parent_right + 1);

Erreurs typiques et anti-modèles

Attendre que le Parent-Enfant soit facilement scalable - avec un arbre profond, les coûts augmentent rapidement
Ensembles imbriqués pour des données mises à jour (insertions/suppressions) - coûteux
Non prise en compte des limites CTE/Stack Overflow dans de grands arbres

Exemple de la vie réelle

Cas négatif

Un grand magasin en ligne stockait l'arbre des catégories dans une liste d'adjacence et construisait le menu avec des sous-requêtes imbriquées. Avec 6 niveaux de menu, la requête principale prenait plusieurs minutes, et toute modification de l'arbre entraînait une mise à jour en cascade. Avantages :

Code simple
Support d'un schéma SQL standard

Inconvénients :

Traversée lente, difficulté à construire des agrégats et des rapports

Cas positif

Passé aux Nested Sets pour des arbres statiques (catégories), et pour les chemins dans le menu - à Path. Utilisation de CTE pour des scénarios dynamiques. La recherche des descendants est devenue instantanée, et les modifications ont été effectuées par lots. Avantages :

Recherche rapide à n'importe quel niveau d'imbrication
Flexibilité, différents modèles pour différentes tâches