# Datahierarkier: Hantera hierarkiska data med EF Core och PostgreSQL (Översikt) ## Inledning 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](/blog/1188), och de grundläggande utmaningarna förblir desamma i dag. ### Varför hierarkier är svåra i SQL 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](https://www.amazon.com/Joe-Celkos-Thinking-Sets-Management/dp/0123741378), 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: 1. Hitta de närmaste barnen 2. För varje barn, hitta *deras* barn 3. Upprepa tills du har korsat hela underträdet 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: - [Rekursiva CTE-värden](https://www.postgresql.org/docs/current/queries-with.html#QUERIES-WITH-RECURSIVE) (tillagt till SQL:1999, men beräkning dyrt) - Flera turer till databasen - Smart denormalisering som förutberäknar relationer 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](https://www.amazon.com/Hierarchies-Smarties-Kaufmann-Management-Systems/dp/0123877334), som täcker alla dessa tillvägagångssätt på djupet. [TOC] ## Exempel: Gängade kommentarer 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: ```mermaid flowchart TD subgraph Post["Post: How to Deploy Docker Containers"] C1["Comment 1: Great article!
depth 0"] C2["Comment 2: Thanks!
depth 1"] C3["Comment 3: Very helpful indeed
depth 1"] C4["Comment 4: Agreed!
depth 2"] C5["Comment 5: What about Kubernetes?
depth 0"] C6["Comment 6: That's covered in part 2
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: - **Få alla kommentarer för ett inlägg** (med trådstruktur bevarad) - **Få alla förfäder** för en kommentar (breadcrumb trail) - **Få alla ättlingar** av en kommentar (hela underträdet) - **Lägg till en ny kommentar** (som svar på en befintlig kommentar) - **Ta bort ett underträd** (Ta bort en kommentar och alla svar) - **Flytta ett underträd** (Reparentera en kommentar - sällsyntare, men ibland behövs) ## De fem tillvägagångssätten Varje metod behandlas i detalj i sin egen artikel. Här är en sammanfattning som hjälper dig att välja: --- ### 1. Adjakslista (föräldrareferens) **[Läs hela artikeln](/blog/efcore-hierarchical-data-adjacency)** 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. --- ### 2. Stängningstabell **[Läs hela artikeln](/blog/efcore-hierarchical-data-closure)** 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. --- ### 3. Materialiserad väg **[Läs hela artikeln](/blog/efcore-hierarchical-data-path)** 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. --- ### 4. Inhägnade uppsättningar **[Läs hela artikeln](/blog/efcore-hierarchical-data-nested)** 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. --- ### 5. PostgreSQL ltree **[Läs hela artikeln](/blog/efcore-hierarchical-data-ltree)** 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](https://www.npgsql.org/efcore/mapping/translations.html#ltree-functions) för träd via `LTree` typ, men rekursiva CTEs fortfarande kräver rå SQL. --- ## Sammanfattning av jämförelsen 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 ## Beslut Flödesschema ```mermaid flowchart TD Start([Start]) --> Q1{Shallow tree?
< 5 levels} Q1 -->|Yes| Q2{Need EF Core
navigation properties?} Q2 -->|Yes| AL[Adjacency List] Q2 -->|No| Q3{Performance
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 ``` ## Real-World Choice: Denna blogg Den här bloggen använder en **Avslutningstabell** Förfaringssätt för kommentarer: 1. Kommentarer läses mycket oftare än skrivs 2. Vi måste visa inbäddade kommentarstrådar på ett effektivt sätt 3. Djup-begränsande frågor är viktiga för prestanda (vi cap på 5 nivåer djupt) 4. Rörliga kommentarer är sällsynta (moderatorer ibland behöver göra detta) Se också [Del 1.2: Stängningstabell](/blog/efcore-hierarchical-data-closure) Fullständiga uppgifter om genomförandet. ## Serienavigering - **Del 1: Översikt** (denna artikel) - [Del 1.1: Tilläggslista](/blog/efcore-hierarchical-data-adjacency) - Enkla föräldrareferenser - [Del 1.2: Stängningstabell](/blog/efcore-hierarchical-data-closure) - Förutfastställda relationer - [Del 1.3: Materialiserad väg](/blog/efcore-hierarchical-data-path) - Sökväg strängar - [Del 1.4: Inhägnade satser](/blog/efcore-hierarchical-data-nested) - Gränser till vänster/höger - [Del 1.5: Ltree](/blog/efcore-hierarchical-data-ltree) - PostgreSQL inbyggt tillägg - Del 2: Rå SQL och Dapper (kommer snart)