Hiërarchische data is overal in de software ontwikkeling: thread comments, organisatorische grafieken, bestandssystemen, productcategorieën, en forum discussies. De eeuwige vraag van "hoe bewaar ik een boom in een relationele database?" heeft ontwikkelaars achtervolgd sinds de vroege dagen van SQL, en eerlijk gezegd, er is nog steeds geen enkel antwoord dat iedereen gelukkig maakt. voor het eerst over dit onderwerp geschreven in 2004, en de fundamentele uitdagingen blijven vandaag dezelfde.
Hier is het fundamentele probleem: relationele databases denken in verzamelingen, geen bomen. Zoals Joe Celko uitlegt in zijn uitstekende boek Denken in verzamelingen, SQL werkt op hele tabellen, niet op individuele rijen.
Wanneer u een SQL query schrijft, werkt de database engine op rijreeksen. Het is briljant bij operaties zoals "vind alle bestellingen boven de 100" of "bind klanten aan hun aankopen" - dit zijn set operaties die natuurlijk passen bij hoe tafels werken. Het resultaat is altijd een platte set van rijen.
Maar een hiërarchie is inherent recursief. Om alle afstammelingen van een knooppunt te vinden, moet je:
Deze recursieve traversale maakt geen natuurlijke map om operaties in te stellen. U kunt niet "geef me alle afstammelingen op enige diepte" in een enkele, eenvoudige SQL statement uitdrukken zonder:
Elke aanpak in deze serie vertegenwoordigt een andere afweging tussen schrijf complexiteit, lees complexiteit en opslag overhead. Er is geen gratis lunch - je bent altijd de ene kosten voor de andere. Voor de definitieve verwijzing over dit onderwerp, zie Joe Celko's Bomen en hiërarchieën in SQL voor slimmeriken, dat betrekking heeft op al deze benaderingen in de diepte.
Om de vergelijkingen concreet te maken, zullen we gebruik maken van schroefdraad opmerkingen als ons draaiende voorbeeld - iets wat deze zeer blog gebruikt. Een commentaar draad zou er als volgt uit kunnen zien:
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
We moeten deze acties ondersteunen:
Elke aanpak wordt in detail behandeld in zijn eigen artikel. Hier is een samenvatting om u te helpen kiezen:
De eenvoudigste en meest intuïtieve aanpak. Elke rij slaat een verwijzing naar zijn ouder knooppunt. Het is wat de meeste ontwikkelaars bereiken voor het eerst omdat het van nature in kaart brengt hoe we denken over hiërarchieën.
Hoe het werkt: Elke opmerking heeft een nullable ParentCommentId kolom. Root opmerkingen hebben NULL, antwoorden wijzen naar hun moeder.
Beste voor: Ondiepe hiërarchieën (minder dan 5-6 niveaus), frequente subboombewegingen, wanneer u wilt dat EF Core's navigatie-eigenschappen natuurlijk werken.
Afspraken: Het verkrijgen van voorouders of afstammelingen vereist recursieve CTE's of meerdere queries. Eenvoudig te schrijven, mogelijk traag om diepe bomen te lezen.
Precompiteert en slaat elke voorouder-afstammeling relatie op in een aparte tabel. In plaats van het uitzoeken van relaties op query tijd, slaan we ze expliciet op met hun diepte.
Hoe het werkt: Een aparte CommentClosure tabelopslag (ancestor_id, descendant_id, diepte) voor elk paar. Commentaar 4 onder Commentaar 1 via Commentaar 3 heeft ingangen: (1,4,2), (3,4.1), (4,4,0).
Beste voor: Lezen-zware toepassingen, wanneer u moet zoeken op willekeurige dieptes, wanneer u zelden subbomen verplaatst.
Afspraken: Meer complexe inserts (moet sluitingangen toevoegen), opslag groeit met diepte, bewegende subbomen vereisen wederopbouw sluitingen.
Bewaart de volledige afstamming als een afgebakend tekenreeks. Zie het als het opslaan van het volledige postadres in plaats van alleen de straatnaam.
Hoe het werkt: Elke opmerking heeft een Path kolom als "1/3/7" betekent "wortel is 1, ouder is 3, dit is 7." Voorouders kunnen worden ontleed van de string; afstammelingen gevonden met soortgelijke queries.
Beste voor: Breadcrumb generatie, wanneer voorouders meer worden gevraagd dan afstammelingen, wanneer je wilt menselijk leesbare paden voor debuggen.
Afspraken: Zoals vragen kunnen traag zijn zonder juiste indexen, pad strings hebben lengte grenzen, bewegende subtrees vereist het updaten van alle afstammelingen paden.
Geeft elk knooppunt links en rechts grensnummers vanaf een diepte-eerste doorkruising. Alle afstammelingen hebben waarden tussen de grenzen van de ouder.
Hoe het werkt: Elke opmerking heeft Left en Right waarden. Een knooppunt met L=4, R=7 bevat alle knooppunten waar 4 < links en rechts < 7. Afstammelingen worden gevonden met eenvoudige bereik queries.
Beste voor: Read-heavy, schrijf-zelver scenario's zoals categorie bomen. Uitstekend voor "krijg hele subboom in display volgorde" queries.
Afspraken: Invoegen vereist het bijwerken van vele rijen (verander alle waarden om ruimte te maken), bewegende subbomen is complex. Niet geschikt voor frequente schrijven.
PostgreSQL's native extensie voor hiërarchische data. Zoals gematerialiseerde paden maar met database-level optimalisatie en krachtige patroon matching.
Hoe het werkt: Gebruikt de ltree gegevenstype met paden als "1.3.5." GiST-indexen maken efficiënte voorouder/afstammeling queries mogelijk met behulp van operators zoals @> en <@.
Beste voor: PostgreSQL-alleen-implementaties waar performance belangrijk is, wanneer je patroon matching queries nodig hebt, wanneer je het beste wilt van gematerialiseerde paden.
Afspraken: PostgreSQL-alleen, voegt database extensie afhankelijkheid. Npgsql provider ondersteunt LINQ vertalingen voor ltree via de LTree type, hoewel recursieve CTE's nog steeds ruwe SQL nodig hebben.
Invoegen Query Subtree Query Voorouders Move Subtree Storage EF Core Support
|----------|--------|---------------|-----------------|--------------|---------|-----------------|
| Adjacentielijst O(1) O(n) met CTE O(d) met CTE O(1) Minimaal Uitstekend
| Sluitingstabel * O(d) * O(1) * O(s x d) * O(n x d) * Good *
| Gematerialiseerd pad * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) * O(1) ** * O(1) * O(s) * O(d) * per node * Good *
| geneste sets O(n) O(1) O(1) O(n) O(n) Minimaal
| ltree * O(1) * O(1) * O(1) * O(s) * O(d) * per node * Good (via LTree type)
n = totale knooppunten, d = diepte, s = subboomgrootte *Met juiste index
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
Deze blog maakt gebruik van een Sluitingstabel de aanpak van de opmerkingen.
Zie Deel 1.2: Sluitingstabel voor de volledige uitvoeringsdetails.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.