Antwort.

Die Arbeit mit hierarchischen Strukturen ist ein Klassiker relationaler Datenbanken. Beispiele: Kataloge, baumartige Menüs, organisatorische Strukturen.

Historie der Frage: Datenbanken basieren auf einem tabellarischen Modell. Für baumartige Daten gibt es mehrere Ansätze, jeder mit seinen Vor- und Nachteilen.

Problem: Das Standardmodell parent_id führt zu langsamen rekursiven SELECT-Abfragen. Reale Aufgaben (Suche nach allen Nachkommen, Pfaden, Zählung von Teilbäumen) erfordern Optimierung.

Lösung:

Adjacency List – einfache Verknüpfung zu parent_id.
Materialized Path – eine Zeichenkette, die den vollständigen Pfad widerspiegelt.
Nested Sets – Speicherung von linken/rechten Grenzen (left/right), was die Extraktion von Teilbäumen erleichtert.
Closure Table – separate Beziehungstabelle (from->to), die alle Beziehungen im Baum widerspiegelt.

Beispielcode für Materialized Path (PostgreSQL):

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    path TEXT
);

-- Beispiel für die Speicherung des Pfades: '1/2/5/' (Wurzel/Subkategorie/Aktuell)
SELECT * FROM categories WHERE path LIKE '1/2/%'; -- alle Nachkommen von 2

Beispielcode für Nested Sets:

CREATE TABLE nested_categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

-- Unterknoten
SELECT * FROM nested_categories WHERE lft > 2 AND rgt < 15;

Wesentliche Merkmale:

Die Adjacency List ist bequem für einfache baumartige Strukturen (geringe Verschachtelung).
Materialized Path – schnelle Extraktion von Teilbäumen, einfach zu implementieren.
Nested Sets – sofortiger Zugriff auf alle Nachkommen, schnelles Lesen, aber komplexe Modifikationen.

Tückische Fragen.

Kann man einfach einen geschachtelten SELECT mit parent_id verwenden, um alle Nachkommen auf beliebiger Tiefe zu finden?

Das funktioniert nur für kleine Tiefen. Für rekursive Suchen benötigt man entweder ein rekursives CTE (WITH RECURSIVE) oder komplexere Schemas, da einfache JOINs zu einer riesigen Anzahl an Zugriffen und schlechter Leistung führen.

Beispiel:

WITH RECURSIVE cte AS (
    SELECT id, parent_id, name FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id, c.name
    FROM categories c
    INNER JOIN cte ON c.parent_id = cte.id
)
SELECT * FROM cte;

Warum extrahiert ein molekulares Baum (Nested Sets) schnell Teilbäume, fügt aber langsam Knoten hinzu/entfernt?

Bei Änderungen im Baum müssen lft/rgt sofort bei vielen Zeilen geändert werden (Änderungsschritt – alle Werte, die größer sind als Einfügen/Löschen). Für das Lesen ist der Ansatz ideal, für häufige Änderungen sollten andere Methoden verwendet werden.

Wann sollte man Closure Table statt parent_id oder Materialized Path verwenden?

Closure Table funktioniert ideal für wiederholte Anfragen nach Nachkommen beliebiger Ebenen und regelmäßige Neuberechnungen von Beziehungen. Nachteil – benötigt mehr Platz.

Beispiel:

CREATE TABLE closure (
    ancestor INT,
    descendant INT,
    depth INT
);

Typische Fehler und Anti-Pattern

Speicherung der Hierarchie nur über parent_id, wenn schnelle Suchen nach verschachtelten Strukturen erforderlich sind.
Manuelles Neuberechnen von Pfaden oder lft/rgt ohne Hilfsfunktionen.
Fehlende Indizierung von Schlüsselspalten (parent_id/path/lft/rgt).

Beispiel aus dem Leben

Negativer Fall

In einem Online-Shop werden Kategorien über parent_id implementiert. Alle Verschachtelungen werden manuell festgelegt, die Suche nach Unterkategorien erfolgt über verschachtelte SELECTs.

Vorteile:

Einfachheit, keine erweiterte Unterstützung erforderlich.

Nachteile:

Die Leistung sinkt bereits bei 3-4 Ebenen der Verschachtelung.
Verschiebungen von Knoten – unklar, führen zu logischen Fehlern.

Positiver Fall

Es wird Materialized Path oder Closure Table verwendet. Alle Anfragen zu verschachtelten Kategorien sind sofort, Neuberechnungen – mit Gruppenskripten.