Datenhierarchien: Verwaltung hierarchischer Daten mit EF Core und PostgreSQL (Übersicht)
Einleitung
Hierarchische Daten sind überall in der Software-Entwicklung: Threaded-Kommentare, Organisationsdiagramme, Dateisysteme, Produktkategorien und Forumsdiskussionen. Die ewige Frage "Wie speichere ich einen Baum in einer relationalen Datenbank?" hat Entwickler seit den frühen Tagen von SQL heimgesucht, und offen gesagt, es gibt immer noch keine einzige Antwort, die alle glücklich macht. zum ersten Mal über dieses Thema im Jahr 2004 geschrieben, und die grundlegenden Herausforderungen bleiben heute die gleichen.
Warum Hierarchien in SQL schwer sind
Hier ist das grundlegende Problem: relationale Datenbanken denken in Sets, nicht in Bäumen. Wie Joe Celko in seinem ausgezeichneten Buch erklärt Denken in SätzenSQL arbeitet auf ganzen Tabellen, nicht auf einzelnen Zeilen.
Wenn Sie eine SQL-Abfrage schreiben, arbeitet die Datenbank-Engine auf Zeilensätze. Es ist brillant bei Operationen wie "finden Sie alle Aufträge über 100" oder "zusammen mit Kunden zu ihren Einkäufen" - das sind Set-Operationen, die natürlich passen, wie Tabellen funktionieren. Das Ergebnis ist immer ein flacher Satz von Zeilen.
Aber eine Hierarchie ist inhärent rekursiv. Um alle Nachkommen eines Knotens zu finden, müssen Sie:
- Finden Sie die unmittelbaren Kinder
- Für jedes Kind finden Sie deren Kinder
- Wiederhole, bis du den ganzen Teilbaum durchquert hast.
Dieses rekursive Traversal mapping nicht natürlich, um Operationen zu setzen. Sie können nicht ausdrücken, "geben Sie mir alle Nachkommen in jeder Tiefe" in einer einzigen, einfachen SQL-Anweisung ohne entweder:
- Rekursive CTEs (zu SQL:1999 hinzugefügt, aber rechnerisch teuer)
- Mehrere Rundfahrten zur Datenbank
- Clevere Entnormierung, die Beziehungen voraussetzt
Jeder Ansatz in dieser Serie stellt einen anderen Kompromiss zwischen Schreibkomplexität, Lesekomplexität und Speicheraufwand. Es gibt kein kostenloses Mittagessen - Sie traden immer eine Kosten für die andere. Für die endgültige Referenz zu diesem Thema, siehe Joe Celko's Bäume und Hierarchien in SQL für Smarties, die alle diese Ansätze tiefgreifend abdeckt.
Das Beispiel: Kommentare zum Thema
Um die Vergleiche konkret zu machen, verwenden wir Threaded-Kommentare als unser laufendes Beispiel - etwas, das genau dieses Blog verwendet. Ein Kommentar-Thread könnte so aussehen:
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
Wir müssen diese Operationen unterstützen:
- Erhalten Sie alle Kommentare für einen Beitrag (mit konservierter Gewindestruktur)
- Holen Sie sich alle Vorfahren eines Kommentars (Breadcrumb trail)
- Holt alle Nachkommen eines Kommentars (ganzer Teilbaum)
- Neuen Kommentar hinzufügen (als Antwort auf eine bestehende Bemerkung)
- Einen Unterbaum löschen (Entfernen Sie einen Kommentar und alle Antworten)
- Einen Unterbaum verschieben (berücksichtigen Sie einen Kommentar - seltener, aber manchmal erforderlich)
Die fünf Ansätze
Jeder Ansatz ist im Detail in seinem eigenen Artikel abgedeckt. Hier ist eine Zusammenfassung, die Ihnen helfen, zu wählen:
1. Adjazenzliste (Parent Reference)
Der einfachste und intuitivste Ansatz. Jede Zeile speichert eine Referenz auf ihren übergeordneten Knoten. Es ist das, was die meisten Entwickler zuerst erreichen, weil es natürlich darauf abbildet, wie wir über Hierarchien denken.
Wie es funktioniert: Jeder Kommentar hat eine annullierbare ParentCommentId Spalte. Root Kommentare haben NULL, Antworten verweisen auf ihre Eltern.
Am besten für: Flache Hierarchien (weniger als 5-6 Ebenen), häufige Subtree bewegt, wenn Sie wollen EF Core Navigationseigenschaften natürlich arbeiten.
Kompromisse: Ahnen oder Nachkommen zu bekommen erfordert rekursive CTEs oder mehrere Abfragen. Einfach zu schreiben, möglicherweise langsam, tiefe Bäume zu lesen.
2. Schließungstabelle
Präkomputiert und speichert jede Ahnen-Abhängige Beziehung in einer separaten Tabelle. Anstatt Beziehungen zur Abfragezeit herauszufinden, speichern wir sie explizit mit ihrer Tiefe.
Wie es funktioniert: Ein separates CommentClosure table stores (ancestor_id, nachkomme_id, deepth) für jedes Paar. Kommentar 4 unter Kommentar 1 via Kommentar 3 hätte Einträge: (1,4,2), (3,4,1), (4,4,0).
Am besten für: Lesen-schwere Anwendungen, wenn Sie in beliebigen Tiefen abgefragt werden müssen, wenn Sie selten Unterbäume verschieben.
Kompromisse: Komplexere Einsätze (müssen Schließungseinträge hinzufügen), die Lagerung wächst mit der Tiefe, bewegliche Unterbäume erfordern den Wiederaufbau Schließungen.
3. Materialisierter Pfad
Speichert die komplette Abstammung als begrenzter String. Betrachten Sie es als die vollständige Postanschrift anstatt nur den Straßennamen zu speichern.
Wie es funktioniert: Jeder Kommentar hat eine Path Spalte wie "1/3/7" bedeutet "root is 1, parent is 3, this is 7". Vorfahren können aus der Zeichenfolge parsiert werden; Nachkommen mit LIKE-Abfragen gefunden.
Am besten für: Breadcrumb Generation, wenn Vorfahren mehr als Nachkommen abgefragt werden, wenn Sie menschenlesbare Pfade zum Debuggen wollen.
Kompromisse: LIKE-Abfragen können ohne korrekte Indexe langsam sein, Pfad-Strings haben Längenbegrenzungen, bewegliche Unterbäume erfordern das Aktualisieren aller nachwachsenden Pfade.
4. Verschachtelte Sets
Zeigt jedem Knoten linke und rechte Grenzzahlen aus einem tiefen ersten Traversal. Alle Nachkommen haben Werte zwischen die Grenzen der Eltern.
Wie es funktioniert: Jeder Kommentar hat Left und Right Werte. Ein Knoten mit L=4, R=7 enthält alle Knoten, bei denen 4 < Links und Rechts < 7. Nachkommen mit einfachen Range-Abfragen gefunden werden.
Am besten für: Lesen-schwere, schreiben-seltene Szenarien wie Kategorie Bäume. Ausgezeichnet für "get ganze subtree in der Anzeige Reihenfolge" Abfragen.
Kompromisse: Inserts erfordern eine Aktualisierung vieler Zeilen (verschieben Sie alle Werte, um Platz zu schaffen), bewegliche Unterbäume ist komplex. Nicht geeignet für häufiges Schreiben.
5. PostgreSQL-Baum
PostgreSQL's native Erweiterung für hierarchische Daten. Wie materialisierte Pfade, aber mit Datenbank-Level-Optimierung und leistungsstarkem Pattern-Matching.
Wie es funktioniert: Verwendet die ltree Datentyp mit Pfaden wie "1.3.7". GiST-Indizes ermöglichen effiziente Vorfahren/Abhängige Abfragen mit Operatoren wie @> und <@.
Am besten für: Nur PostgreSQL-Bereitstellungen, bei denen Leistung wichtig ist, wenn Sie Muster-Matching-Abfragen benötigen, wenn Sie das Beste aus materialisierten Pfaden wollen.
Kompromisse: PostgreSQL-only, fügt Datenbankerweiterung Abhängigkeit. Npgsql-Anbieter unterstützt LINQ-Übersetzungen für ltree über die LTree Typ, obwohl rekursive CTEs immer noch Roh-SQL benötigen.
Zusammenfassung des Vergleichs
Anflug-Anflug-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-punkt-Anlauf-Anlauf-punkt-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-lauf-Anstieg-Anlauf-lauf-Anlauf-Anlauf-Anlauf-Anlauf-Anlauf-
|----------|--------|---------------|-----------------|--------------|---------|-----------------|
| Adjazenzliste O(1), O(n) mit CTE, O(d) mit CTE, O(1), Minimal, Excellent
| Schließungstabelle O(d)-O(1)-O(1)-O(s x d)-O(n x d)-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)
| Materialisierter Pfad 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) pro Knoten
| Verschachtelte Sets O(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n))(n)(n))(n)(n))(n)(n)(n)(n)(n))(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n)(n))(n)))(n)(n)(n)(n)(n)(n))()))(n)))()()(en)))))))(n))(e)(e)())(n)(n))()))))()()()()()()()()()()())))))()())()()()()()()()()()()()()()()()()()()()))()()())()()()))))()()())))()()()()()())))()()()()()()()()()()()()()))))()())()()()()()())))()()()()()()()()()))()()))()(
| Baum O(1), O(1), O(1), O(s), O(d) pro Knoten LTree Art)
n = Gesamtknoten, d = Tiefe, s = Unterbaumgröße *Mit passendem Index
Entscheidungsablaufdiagramm
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
Real-World Wahl: Dieser Blog
Dieser Blog verwendet eine Schließungstabelle Ansatz für Kommentare. Die Begründung:
- Kommentare werden viel öfter gelesen als geschrieben
- Wir müssen verschachtelte Kommentar-Threads effizient anzeigen
- Tiefenbegrenzende Abfragen sind wichtig für die Leistung (wir cap auf 5 Ebenen tief)
- Bewegte Kommentare sind selten (Moderatoren müssen dies gelegentlich tun)
Siehe Teil 1.2: Schließungstabelle für die vollständigen Durchführungsdetails.
Reihennavigation
- Teil 1: Überblick (dieser Artikel)
- Teil 1.1: Adjazenzliste - Einfache Elternreferenzen
- Teil 1.2: Schließungstabelle - Vorgerechnete Beziehungen
- Teil 1.3: Materialisierter Pfad - Pfad-Strings
- Teil 1.4: Verschachtelte Sets - Linke/rechte Grenzen
- Teil 1.5: Baum - PostgreSQL native Erweiterung
- Teil 2: Raw SQL und Dapper (in Kürze)