Hierarkidata finns överallt inom programvaruutveckling: gängade kommentarer, organisatoriska diagram, filsystem, produktkategorier och forumdiskussioner. Den eviga frågan om "hur lagrar jag ett träd i en relationsdatabas?" har hemsökt utvecklare sedan de första dagarna av SQL, och ärligt talat, det finns fortfarande inget enda svar som gör alla glada. skrevs första gången om detta ämne 2004, och de grundläggande utmaningarna förblir desamma i dag.
Här är det grundläggande problemet: relationsdatabaser tänker i uppsättningar, inte träd. Som Joe Celko förklarar i sin utmärkta bok Att tänka på olika sätt, SQL fungerar på hela tabeller, inte enskilda rader.
När du skriver en SQL-fråga, fungerar databasmotorn på raduppsättningar. Det är lysande på verksamhet som "hitta alla beställningar över 100" eller "gå kunder till sina inköp" - dessa är inställda operationer som passar naturligt med hur tabeller fungerar. Resultatet är alltid en platt uppsättning rader.
Men en hierarki är i sig själv rekursiv. För att hitta alla ättlingar till en nod, måste du:
Denna rekursiva traversal kartlägger inte naturligt för att ställa in operationer. Du kan inte uttrycka "ge mig alla ättlingar på något djup" i en enda, enkel SQL uttalande utan antingen:
Varje tillvägagångssätt i denna serie representerar en annan avvägning mellan skriva komplexitet, läsa komplexitet, och lagring overhead. Det finns ingen gratis lunch - du alltid handla en kostnad för en annan. För den definitiva referensen i detta ämne, se Joe Celkos Träd och hierarkier i SQL för smarties, som täcker alla dessa tillvägagångssätt på djupet.
För att göra jämförelserna konkreta, vi kommer att använda gängade kommentarer som vårt kör exempel - något som denna blogg använder. En kommentar tråd kan se ut så här:
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
Vi måste stödja dessa operationer:
Varje metod behandlas i detalj i sin egen artikel. Här är en sammanfattning som hjälper dig att välja:
Det enklaste och mest intuitiva tillvägagångssättet. Varje rad lagrar en hänvisning till sin förälder nod. Det är vad de flesta utvecklare når först eftersom det kartor naturligt till hur vi tänker om hierarkier.
Hur det fungerar: Varje kommentar har en ogiltig ParentCommentId kolumn. Rotkommentarer har NULL, svar pekar på deras förälder.
Bäst för: Skala hierarkier (mindre än 5-6 nivåer), ofta subtree flyttar, när du vill att EF Core navigation egenskaper att fungera naturligt.
Avsättningar: Få förfäder eller ättlingar kräver rekursiva CTEs eller flera frågor. Enkel att skriva, potentiellt långsam att läsa djupa träd.
Förkompilerar och lagrar varje förfader-decendant relation i en separat tabell. Istället för att räkna ut relationer vid frågestunden, lagrar vi dem uttryckligen med sitt djup.
Hur det fungerar: A separat CommentClosure bordsbutiker (ancestor_id, ättling_id, djup) för varje par. Kommentar 4 under Kommentar 1 via Kommentar 3 skulle ha poster: (1,4.2), (3,4.1, (4,4.40).
Bäst för: Lästunga program, när du behöver fråga på godtyckliga djup, när du sällan flyttar underträd.
Avsättningar: Mer komplexa skär (måste lägga till stängningsposter), lagring växer med djup, rörliga delträd kräver återuppbyggnad stängningar.
Lagrar hela härkomsten som en avgränsad sträng. Tänk på det som att lagra hela postadressen snarare än bara gatunamnet.
Hur det fungerar: Varje kommentar har en Path Kolumn som "1/3/7" betyder "roten är 1, föräldern är 3, denna är 7". Förfäder kan tolkas från strängen; ättlingar finns med LIKA frågor.
Bäst för: Här-är-du-generation, när förfäder ställs mer än ättlingar, när du vill ha människa-läsbara vägar för felsökning.
Avsättningar: LIKA frågor kan vara långsamma utan korrekta index, vägsträngar har längdgränser, rörliga delträd kräver uppdatering av alla nedstigande vägar.
Tilldela varje nod vänster och höger gränsnummer från en djup-första traversal. Alla ättlingar har värden mellan föräldrarnas gränser.
Hur det fungerar: Varje kommentar har Left och Right värden. En nod med L=4, R=7 innehåller alla noder där 4 < Vänster och höger < 7. Descendanter hittas med enkla avståndsförfrågningar.
Bäst för: Läs-tunga, skriv-sällsynt scenarier som kategori träd. Utmärkt för "få hela underträd i display ordning" frågor.
Avsättningar: Infogar kräver uppdatering av många rader (ändra alla värden för att göra plats), rörliga delträd är komplexa. Inte lämplig för frekventa skriver.
PostgreSQL: s ursprungliga förlängning för hierarkiska data. Som materialiserade vägar men med databasnivåoptimering och kraftfull mönstermatchning.
Hur det fungerar: Använder ltree datatyp med sökvägar som "1.3.7". GiST-index möjliggör effektiva förfader/avvisande frågor med hjälp av operatörer som @> och <@.
Bäst för: PostgreSQL-endast distributioner där prestanda spelar roll, när du behöver mönstermatchande frågor, när du vill ha det bästa av materialiserade vägar.
Avsättningar: PostgreSQL- only, lägger till databastilläggsberoende. Observera: Npgsql leverantör stöder LINQ översättningar för träd via LTree typ, men rekursiva CTEs fortfarande kräver rå SQL.
Tillvägagångssätt och sätt in en förfrågan Subtree på förfrågan Förfäder och flytta Subtree och lagring på EF Core Support och
|----------|--------|---------------|-----------------|--------------|---------|-----------------|
| Adjakslista O(1) O(n) med CTE på O(d) med CTE på O(1) på minimalt sätt
| Avslutningstabell O(n) O(d) O(1) O(1) O(1) O(s x d) O(n x d) O(n x d)
| Materialiserad väg O(1) O(1) O(1) O(1)* O(1) O(s) O(s) A(s) O(d) per nod på gott sätt
| Inhägnade uppsättningar O(n) O(n) O(1) O(1) O(n) O(n) på ett minimalt och bra sätt
| Iträd O(1) A(1) O(1) O(1) O(1) O(s) O(s) O(s) O(d) per nod på gott sätt (via LTree typ)
n = totala noder, d = djup, s = delträdets storlek *Med korrekt 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
Den här bloggen använder en Avslutningstabell Förfaringssätt för kommentarer:
Se också Del 1.2: Stängningstabell Fullständiga uppgifter om genomförandet.
© 2026 Scott Galloway — Unlicense — All content and source code on this site is free to use, copy, modify, and sell.