This is a viewer only at the moment see the article on how this works.
To update the preview hit Ctrl-Alt-R (or ⌘-Alt-R on Mac) or Enter to refresh. The Save icon lets you save the markdown file to disk
This is a preview from the server running through my markdig pipeline
Saturday, 06 December 2025
Les données hiérarchiques sont partout dans le développement logiciel: commentaires threaded, organigrammes, systèmes de fichiers, catégories de produits, et discussions de forum. La question éternelle de "comment puis-je stocker un arbre dans une base relationnelle?" a hanté les développeurs depuis les débuts de SQL, et franchement, il n'y a toujours pas de réponse unique qui rend tout le monde heureux. d'abord écrit sur ce sujet en 2004, et les défis fondamentaux restent les mêmes aujourd'hui.
Voici le problème fondamental : Les bases de données relationnelles pensent en ensembles, pas en arbres. Comme l'explique Joe Celko dans son excellent livre Penser dans des ensembles, SQL fonctionne sur des tables entières, pas sur des lignes individuelles.
Lorsque vous écrivez une requête SQL, le moteur de base de données fonctionne sur ensembles de lignes. Il est brillant à des opérations comme "trouver toutes les commandes de plus de 100" ou " rejoindre les clients à leurs achats" - ce sont des opérations définies qui correspondent naturellement à la façon dont les tables fonctionnent. Le résultat est toujours un ensemble plat de lignes.
Mais une hiérarchie est intrinsèquement récursif. Pour trouver tous les descendants d'un noeud, vous devez:
Cette traversée récursive ne permet pas naturellement de définir les opérations. Vous ne pouvez pas exprimer "donnez-moi tous les descendants à n'importe quelle profondeur" dans une seule, simple déclaration SQL sans l'un ni l'autre:
Chaque approche de cette série représente un compromis différent entre la complexité de l'écriture, la complexité de la lecture et les frais généraux de stockage. Il n'y a pas de déjeuner gratuit - vous êtes toujours trading un coût pour un autre. Pour la référence définitive à ce sujet, voir Joe Celko's Arbres et hiérarchies dans SQL pour Smarties, qui couvre toutes ces approches en profondeur.
Pour rendre les comparaisons concrètes, nous utiliserons les commentaires threaded comme exemple de course - quelque chose que ce blog utilise. Un fil de commentaire pourrait ressembler à ceci:
flowchart TD
subgraph Post["Post: How to Deploy Docker Containers"]
C1["Comment 1: Great article!<br/>depth 0"]
C2["Comment 2: Thanks!<br/>depth 1"]
C3["Comment 3: Very helpful indeed<br/>depth 1"]
C4["Comment 4: Agreed!<br/>depth 2"]
C5["Comment 5: What about Kubernetes?<br/>depth 0"]
C6["Comment 6: That's covered in part 2<br/>depth 1"]
end
C1 --> C2
C1 --> C3
C3 --> C4
C5 --> C6
style Post stroke:#10b981,stroke-width:2px
style C1 stroke:#6366f1,stroke-width:2px
style C2 stroke:#8b5cf6,stroke-width:2px
style C3 stroke:#8b5cf6,stroke-width:2px
style C4 stroke:#a855f7,stroke-width:2px
style C5 stroke:#6366f1,stroke-width:2px
style C6 stroke:#8b5cf6,stroke-width:2px
Nous devons soutenir ces opérations :
Chaque approche est traitée en détail dans son propre article. Voici un résumé pour vous aider à choisir:
L'approche la plus simple et la plus intuitive. Chaque rangée stocke une référence à son noeud parent. C'est ce que la plupart des développeurs atteignent pour la première fois parce qu'il map naturellement à la façon dont nous pensons aux hiérarchies.
Comment ça marche : Chaque commentaire a une valeur nulle ParentCommentId colonne. Les commentaires racines ont NULL, les réponses pointent à leur parent.
Meilleur pour: Hiérarchies peu profondes (moins de 5-6 niveaux), déplacements fréquents sous-arbres, lorsque vous voulez que les propriétés de navigation d'EF Core fonctionnent naturellement.
Conciliation: Obtenir des ancêtres ou des descendants nécessite des CTE récursifs ou de multiples requêtes. Simple à écrire, potentiellement lent à lire des arbres profonds.
Précalcule et stocke chaque relation ancêtre-descendant dans une table séparée. Au lieu de déterminer les relations au moment de la requête, nous les stockons explicitement avec leur profondeur.
Comment ça marche : Un autre CommentClosure les magasins de table (ancestor_id, descendant_id, profondeur) pour chaque paire. Commentaire 4 sous Commentaire 1 via Commentaire 3 aurait des entrées: (1,4,2), (3,4,1), (4,4,0).
Meilleur pour: Applications lue-lourdes, quand vous avez besoin de demander à des profondeurs arbitraires, quand vous déplacez rarement des sous-arbres.
Conciliation: Les inserts plus complexes (doivent ajouter des entrées de fermeture), le stockage se développe avec la profondeur, les sous-arbres mobiles nécessitent la reconstruction des fermetures.
Enregistre l'ascendance complète comme une chaîne délimitée. Pensez-y comme en stockant l'adresse postale complète plutôt que simplement le nom de rue.
Comment ça marche : Chaque commentaire a un Path colonne comme "1/3/7" signifiant "root is 1, parent is 3, this is 7". Les ancêtres peuvent être analysés à partir de la chaîne; les descendants trouvés avec les requêtes Like.
Meilleur pour: Fil d'Ariane génération, quand les ancêtres sont interrogés plus que les descendants, quand vous voulez des chemins lisibles par l'homme pour le débogage.
Conciliation: Comme les requêtes peuvent être lentes sans index approprié, les chaînes de chemins ont des limites de longueur, le déplacement des sous-arbres nécessite la mise à jour de tous les chemins descendants.
Attribue chaque noeud à gauche et à droite des nombres de limites à partir d'une première traversée de profondeur. Tous les descendants ont des valeurs entre les limites du parent.
Comment ça marche : Chaque commentaire a Left et Right Un noeud avec L=4, R=7 contient tous les nœuds où 4 < Gauche et Droite < 7. Descendants sont trouvés avec des requêtes de plage simple.
Meilleur pour: Scénarios lus-lourds, écrivant-rarement comme des arbres de catégorie. Excellent pour les requêtes "obtenir tout le sous-arbre dans l'ordre d'affichage".
Conciliation: Les insertions nécessitent la mise à jour de nombreuses lignes (déplacer toutes les valeurs pour faire de la place), le déplacement des sous-arbres est complexe.
L'extension native de PostgreSQLTM pour les données hiérarchiques. Comme les chemins matérialisés mais avec l'optimisation au niveau de la base de données et le couplage puissant des motifs.
Comment ça marche : Utilise les ltree type de données avec des chemins comme "1.3.7". Les index GiST permettent des requêtes d'ancêtre/descendant efficaces en utilisant des opérateurs comme @> et <@.
Meilleur pour: PostgreSQL-seulement les déploiements où les performances comptent, lorsque vous avez besoin de requêtes de correspondance de motifs, lorsque vous voulez le meilleur des chemins matérialisés.
Conciliation: PostgreSQL-seulement, ajoute une dépendance à l'extension de base de données. Le fournisseur de Npgsql prend en charge les traductions de LINQ pour l'arbre par l'intermédiaire de LTree type, bien que les CTE récursifs nécessitent toujours SQL brut.
Déplacer le sous-arbre de stockage de l'EF Support de base de l'EF
|----------|--------|---------------|-----------------|--------------|---------|-----------------|
| Liste des dépendances O(n) O(d) O(d) O(d) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n)
| Tableau de fermeture O(d)= O(1)= O(1)= O(s x d)= O(n x d)= Bon
| Voie matérialisée O(1) O(1)* O(s) O(s) O(d) par noeud
| Ensembles nichés O(n)=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=
| L'arbre O(1)(s) O(1)(s) O(s) O(d) par noeud O(1)(s) O(d) par noeud O(1)(s) O(s) O(s) O(s) O(s) O(d) par noeud O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) O(s) LTree Type)
n = nœuds totaux, d = profondeur, s = taille du sous-arbre *Avec un indice approprié
flowchart TD
Start([Start]) --> Q1{Shallow tree?<br/>< 5 levels}
Q1 -->|Yes| Q2{Need EF Core<br/>navigation properties?}
Q2 -->|Yes| AL[Adjacency List]
Q2 -->|No| Q3{Performance<br/>critical?}
Q3 -->|No| AL
Q3 -->|Yes| MP[Materialised Path]
Q1 -->|No| Q4{Read-heavy?}
Q4 -->|Yes| Q5{Writes rare?}
Q5 -->|Yes| NS[Nested Sets]
Q5 -->|No| CT[Closure Table]
Q4 -->|No| Q6{PostgreSQL only?}
Q6 -->|Yes| LT[ltree]
Q6 -->|No| Q7{Need breadcrumbs?}
Q7 -->|Yes| MP
Q7 -->|No| CT
style Start stroke:#10b981,stroke-width:2px
style AL stroke:#6366f1,stroke-width:2px
style MP stroke:#8b5cf6,stroke-width:2px
style NS stroke:#ec4899,stroke-width:2px
style CT stroke:#f59e0b,stroke-width:2px
style LT stroke:#14b8a6,stroke-width:2px
Ce blog utilise un Tableau de fermeture La raison d'être :
Voir Partie 1.2: Tableau de fermeture pour les détails de la mise en œuvre complète.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.