Antwort.

Die Arbeit mit Bäumen und Hierarchien ist ein häufiger Fall beim Programmieren in SQL: Produktkataloge, Organisationsstrukturen, Menüs. Ursprünglich unterstützten die meisten DBMS nur einen Verweis auf den Elternknoten (ParentId), aber im Laufe der Zeit wurden alternative Methoden wie verschachtelte Mengen und Pfade (Path) sowie rekursive Abfragen über CTE eingeführt.

Problem des traditionellen Parent-Child-Ansatzes ist die niedrige Geschwindigkeit beim Durchlaufen großer Hierarchien; Abfragen auf einer Tiefe von mehr als 2-3 führen zu einer schneeballartigen Zahl von JOINs. Komplexere Techniken (Nested Sets, Path Enumeration) beschleunigen Massenabfragen, erschweren aber Einfügungen/Löschungen.

Lösung — die Wahl des optimalen Speichermodells für eine bestimmte Aufgabe:

Für seltene Änderungen und häufiges Lesen: Nested Sets (wir speichern die Grenzen left/right in den Knoten für eine schnelle Suche nach Nachkommen)
Für häufige Änderungen: Adjacency List + rekursive CTE
Für eine schnelle Pfadsuche — Path und Speicherung des gesamten Pfades in einer Zeile

Beispiel für eine rekursive Suche eines Teilbaums über CTE:

WITH RecursiveTree AS (
  SELECT id, parent_id, name, 0 as level
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.parent_id, c.name, rt.level + 1
  FROM categories c
  INNER JOIN RecursiveTree rt ON c.parent_id = rt.id
)
SELECT * FROM RecursiveTree;

Wichtige Merkmale:

Auswahl der Speicherstruktur für das Szenario (Parent-Child, Nested Sets, Path)
Verwendung eines rekursiven CTE für beliebige Tiefen
Bewertung der Häufigkeit von Änderungen und Lesevorgängen zur Auswahl der optimalen Methode

Fragen mit einem Haken.

Kann die Speicherung von Bäumen durch eine denormalisierte Tabelle mit einer Verweistiefe ersetzt werden, wenn die Tiefe festgelegt ist?

Nur wenn die Tiefe gering und immer festgelegt ist (2-3 Ebenen) — danach werden JOINs unübersichtlich, die Verarbeitung von Änderungen wird komplizierter.

Wird CTE bei großen Bäumen nicht "hängen bleiben" — gibt es keine Einschränkungen für den Stack oder die Rekursionstiefe?

Ja, die meisten DBMS setzen Grenzen für die Rekursionstiefe (zum Beispiel 100/32767). Für Bäume mit 1000+ Ebenen ist eine manuelle Verwaltung der Tiefe oder die Verwendung benutzerdefinierter Algorithmen für das Durchlaufen/Teilen erforderlich.

Sind Nested Sets die Lösung aller Probleme?

Nein, nested sets finden sofort alle Nachkommen, aber das Einfügen/Löschen erfordert eine massenhafte Aktualisierung aller links/rechts Indizes — das ist langsam bei einer hohen Anzahl häufiger Änderungen.

Beispiel für eine Einfügung (vereinfacht):

UPDATE tree SET lft = lft + 2 WHERE lft > @parent_right;
UPDATE tree SET rgt = rgt + 2 WHERE rgt >= @parent_right;
INSERT INTO tree(id, name, lft, rgt) VALUES(@new_id, @name, @parent_right, @parent_right + 1);

Typische Fehler und Anti-Pattern

Erwartung, dass Parent-Child leicht skalierbar ist — bei einem tiefen Baum schnelle Kostensteigerung
Verschachtelte Mengen für aktualisierte Daten (Einfügungen/Löschungen) — kostspielig
Keine Berücksichtigung der CTE/Stack Overflow-Limits bei großen Bäumen

Beispiel aus dem Leben

Negativer Fall

Ein großer Online-Shop speicherte das Baumdiagramm der Kategorien in einer Adjacency List und baute Menüs mit verschachtelten Unterabfragen. Bei mehr als 6 Ebenen dauerte die Hauptabfrage mehrere Minuten, und jede Änderung des Baums führte zu einer Kaskadenaktualisierung. Vorteile:

Einfacher Code
Unterstützung des standardmäßigen SQL-Schemas

Nachteile:

Langsame Durchläufe, schwer Aggregationen und Berichte zu erstellen

Positiver Fall

Wir sind zu Nested Sets für statische Bäume (Kategorien) gewechselt und für die Pfade im Menü auf Path. Wir nutzten CTE für dynamische Szenarien. Die Suche nach Nachkommen wurde sofort, Änderungen erfolgten in Batches. Vorteile:

Schnelle Suche auf jeder Verschachtelungsebene
Flexibilität, verschiedene Modelle für verschiedene Aufgaben