Hierarchische Daten modellieren: vier Ansaetze im Vergleich

1. Warum hierarchische Daten in relationalen Datenbanken schwierig sind

Hierarchische Daten wie Produktkategorien, Organisationsstrukturen, Dateisysteme oder verschachtelte Kommentar-Threads haben eine baumfoermige Struktur mit beliebiger Tiefe, waehrend relationale Tabellen von Natur aus flach sind: Eine Zeile hat feste Spalten, keine variable Anzahl an Kindern. Diese strukturelle Spannung zwingt jedes Modell fuer hierarchische Daten zu einem Kompromiss zwischen Schreib- und Leseperformance.

Die zentrale Frage lautet immer: Welche Operationen sind haeufig, und welche duerfen dafuer langsamer sein? Ein Kategoriebaum in einem Shop wird selten strukturell geaendert, aber sehr haeufig fuer Navigationsmenues und Teilbaum-Abfragen gelesen. Ein Kommentar-Thread dagegen bekommt staendig neue Eintraege, waehrend komplette Baumabfragen seltener und meist nur fuer eine begrenzte Tiefe noetig sind. Die vier in diesem Beitrag besprochenen Modelle, Adjacency List, Nested Sets, Path Enumeration und Closure Table, loesen diesen Kompromiss auf unterschiedliche Weise.

Keines der vier Modelle ist universell "das beste" fuer hierarchische Daten. Jedes optimiert bewusst fuer bestimmte Operationen auf Kosten anderer, und die richtige Wahl haengt vollstaendig vom tatsaechlichen Zugriffsmuster der jeweiligen Anwendung ab. Die folgenden Abschnitte zeigen jedes Modell mit konkretem Schema und typischen Abfragen.

2. Adjacency List: das einfachste Modell und seine Grenzen

Die Adjacency List ist das intuitivste Modell fuer hierarchische Daten: Jede Zeile speichert lediglich eine Referenz auf ihren direkten Elternknoten ueber eine selbstreferenzierende Fremdschluessel-Spalte parent_id. Die Wurzel des Baums hat parent_id = NULL, jeder andere Knoten verweist auf genau einen Elternknoten.

-- Adjacency List: einfachste Modellierung ueber parent_id
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  parent_id    INTEGER REFERENCES categories(category_id),
  name         VARCHAR(255) NOT NULL
);

-- Einfuegen ist trivial: nur die parent_id des neuen Knotens setzen
INSERT INTO categories (parent_id, name) VALUES (3, 'Grafikkarten');

-- Direkte Kinder eines Knotens: ein einfacher, indizierter Join
SELECT * FROM categories WHERE parent_id = 3;

-- Ganzer Teilbaum: benoetigt eine rekursive CTE (siehe Abschnitt 8)
WITH RECURSIVE subtree AS (
  SELECT * FROM categories WHERE category_id = 3
  UNION ALL
  SELECT c.* FROM categories c
  JOIN subtree s ON c.parent_id = s.category_id
)
SELECT * FROM subtree;

Der Vorteil liegt in maximaler Einfachheit: Einfuegen, Verschieben und Loeschen eines einzelnen Knotens sind jeweils ein einziges, schnelles INSERT, UPDATE oder DELETE. Die Grenze zeigt sich bei Teilbaum-Abfragen: Ohne rekursive CTE oder eine Anwendung, die die Rekursion selbst uebernimmt, ist es unmoeglich, in einer einzigen einfachen Abfrage "alle Nachfahren eines Knotens" zu ermitteln, weil die Tiefe des Baums zur Abfragezeit unbekannt ist.

3. Nested Sets: Baumstruktur ueber left- und right-Werte

Nested Sets kodieren die Baumstruktur nicht ueber eine Elternreferenz, sondern ueber zwei Zahlenwerte pro Knoten, traditionell lft und rgt genannt, die aus einer Tiefensuche des Baums entstehen. Jeder Knoten umschliesst mit seinem Intervall [lft, rgt] die Intervalle aller seiner Nachfahren vollstaendig, wodurch Teilbaum-Abfragen zu einem einfachen Bereichsvergleich werden.

-- Nested Sets: Baumstruktur ueber lft/rgt-Intervalle
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL,
  lft          INTEGER NOT NULL,
  rgt          INTEGER NOT NULL
);

-- Ganzer Teilbaum eines Knotens: ein einziger Bereichsvergleich,
-- KEINE Rekursion noetig
SELECT child.*
FROM categories AS node, categories AS child
WHERE child.lft BETWEEN node.lft AND node.rgt
  AND node.category_id = 3;

-- Alle Vorfahren eines Knotens: ebenfalls ein einziger Bereichsvergleich
SELECT ancestor.*
FROM categories AS node, categories AS ancestor
WHERE node.lft BETWEEN ancestor.lft AND ancestor.rgt
  AND node.category_id = 17;

-- Einfuegen eines neuen Knotens erfordert das Verschieben ALLER
-- rechts liegenden lft/rgt-Werte, teuer bei grossen Baeumen:
-- UPDATE categories SET rgt = rgt + 2 WHERE rgt >= :insert_position;
-- UPDATE categories SET lft = lft + 2 WHERE lft >= :insert_position;

Der grosse Vorteil von Nested Sets: Teilbaum- und Vorfahren-Abfragen sind extrem schnell, weil sie ohne Rekursion und ohne Joins ueber mehrere Ebenen auskommen, nur ein einfacher Bereichsvergleich auf indizierten Integer-Spalten ist noetig. Der Nachteil ist massiv bei Schreiboperationen: Jedes Einfuegen oder Verschieben eines Knotens erfordert das Aktualisieren der lft/rgt-Werte aller rechts liegenden Knoten im gesamten Baum, was bei grossen, haeufig geaenderten Baeumen zu Sperren und Performance-Problemen fuehrt.

4. Path Enumeration: der Pfad als String-Spalte

Path Enumeration speichert fuer jeden Knoten den vollstaendigen Pfad von der Wurzel als String, typischerweise mit einem Trennzeichen zwischen den Ids der Vorfahren. Ein Knoten mit Pfad 1.3.17 bedeutet: Wurzel-Id 1, dann Kind-Id 3, dann Kind-Id 17, also die eigene Id am Ende des Pfads.

-- Path Enumeration: vollstaendiger Pfad als String pro Knoten
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL,
  path         VARCHAR(500) NOT NULL   -- z.B. '1.3.17'
);

CREATE INDEX idx_categories_path ON categories (path);

-- Alle Nachfahren eines Knotens mit Pfad '1.3': Praefix-Suche
SELECT * FROM categories WHERE path LIKE '1.3.%';

-- Alle Vorfahren eines Knotens mit Pfad '1.3.17': Pfad in Segmente zerlegen
-- und gegen category_id der jeweiligen Segmente pruefen (vereinfachtes Beispiel)
SELECT * FROM categories
WHERE category_id = ANY (string_to_array('1.3.17', '.')::int[]);

-- Einfuegen ist einfach: eigenen Pfad aus dem Elternpfad ableiten
INSERT INTO categories (name, path) VALUES ('Grafikkarten', '1.3.17.42');

Der Vorteil dieses Modells: Einfuegen ist ebenso einfach wie bei der Adjacency List, und Nachfahren-Abfragen sind ueber eine indizierte Praefix-Suche moeglich, ohne Rekursion. Der Nachteil ist das Verschieben eines Teilbaums: Wird ein Knoten mit vielen Nachfahren an eine andere Stelle im Baum verschoben, muss der Pfad-String jedes einzelnen Nachfahren aktualisiert werden, aehnlich teuer wie bei Nested Sets. Zusaetzlich begrenzt die maximale Spaltenlaenge implizit die maximale Baumtiefe.

5. Closure Table: alle Vorfahren-Nachfahren-Beziehungen explizit

Die Closure Table geht einen anderen Weg als die drei vorherigen Modelle: Statt die Hierarchie in der Knoten-Tabelle selbst zu kodieren, speichert eine separate Tabelle jede Vorfahren-Nachfahren-Beziehung als eigene Zeile, inklusive der Distanz zwischen beiden Knoten. Ein Knoten ist dabei auch sein eigener Vorfahre mit Distanz null.

-- Closure Table: jede Vorfahren-Nachfahren-Beziehung als eigene Zeile
CREATE TABLE categories (
  category_id  SERIAL PRIMARY KEY,
  name         VARCHAR(255) NOT NULL
);

CREATE TABLE category_paths (
  ancestor_id    INTEGER NOT NULL REFERENCES categories(category_id),
  descendant_id  INTEGER NOT NULL REFERENCES categories(category_id),
  depth          INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

-- Ganzer Teilbaum eines Knotens: einfacher Join, keine Rekursion
SELECT c.* FROM categories c
JOIN category_paths cp ON cp.descendant_id = c.category_id
WHERE cp.ancestor_id = 3;

-- Alle Vorfahren eines Knotens: derselbe Join, andere Filterrichtung
SELECT c.* FROM categories c
JOIN category_paths cp ON cp.ancestor_id = c.category_id
WHERE cp.descendant_id = 17;

-- Einfuegen eines neuen Blatt-Knotens unter Elternknoten 3:
-- Kopiere alle Vorfahren-Beziehungen des Elternknotens plus eine neue Zeile fuer sich selbst
INSERT INTO category_paths (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 42, depth + 1 FROM category_paths WHERE descendant_id = 3
UNION ALL
SELECT 42, 42, 0;

Der Vorteil der Closure Table: Sowohl Teilbaum- als auch Vorfahren-Abfragen sind einfache, nicht-rekursive Joins, und das Verschieben eines Teilbaums betrifft nur die Zeilen, die den verschobenen Knoten und seine Nachfahren betreffen, nicht den gesamten Baum wie bei Nested Sets. Der Nachteil ist Speicherbedarf: Die Anzahl der Zeilen in der Closure Table waechst quadratisch mit der Tiefe eines Teilbaums, ein Knoten mit hundert Nachfahren erzeugt potenziell tausende Beziehungszeilen.

6. Schreiboperationen im Vergleich: Einfuegen, Verschieben, Loeschen

Bei hierarchischen Daten unterscheiden sich die vier Modelle am staerksten bei Schreiboperationen. Adjacency List und Path Enumeration sind beim reinen Einfuegen eines neuen Blattknotens gleich guenstig, ein einziger INSERT reicht aus. Nested Sets dagegen erfordert bei jedem Einfuegen ein Update aller rechts liegenden lft/rgt-Werte im gesamten Baum, was bei tausenden Knoten spuerbar wird.

Beim Verschieben eines Teilbaums, etwa wenn eine Kategorie mit vielen Unterkategorien in einen anderen Zweig wandert, zeigt sich der groesste Unterschied: Bei Adjacency List reicht ein einziges UPDATE der parent_id des verschobenen Knotens, alle Nachfahren bleiben unveraendert, weil sie relativ zu ihrem direkten Elternknoten weiterhin korrekt referenziert sind. Bei Path Enumeration und Nested Sets muss dagegen jeder einzelne Nachfahre aktualisiert werden. Die Closure Table liegt dazwischen: Nur die Beziehungszeilen des verschobenen Teilbaums muessen neu berechnet werden, nicht die gesamte Tabelle.

7. Leseoperationen im Vergleich: Teilbaum, Tiefe, Vorfahren

Bei Leseoperationen dreht sich das Bild fast vollstaendig um. Adjacency List benoetigt fuer jede Teilbaum- oder Vorfahren-Abfrage entweder eine rekursive CTE oder mehrere Anwendungslogik-Roundtrips, was bei tiefen Baeumen spuerbar langsamer ist als ein einzelner Join. Nested Sets, Path Enumeration und Closure Table loesen genau dieses Problem, jedes auf eigene Weise, mit einer einzigen, nicht-rekursiven Abfrage.

Die Tiefe eines Knotens im Baum ist bei Nested Sets nicht direkt gespeichert und muss ueber die Anzahl umschliessender Intervalle gezaehlt werden, waehrend Closure Table die Tiefe explizit in der depth-Spalte mitfuehrt und damit trivial abfragbar macht. Path Enumeration liefert die Tiefe indirekt ueber die Anzahl der Trennzeichen im Pfad-String. Fuer Anwendungen, die haeufig nach "alle Knoten auf Ebene 3" fragen, ist die Closure Table oder ein zusaetzliches depth-Feld bei den anderen Modellen die praktikabelste Loesung.

8. Wann rekursive CTEs ausreichen und wann nicht

Rekursive Common Table Expressions loesen das Adjacency-List-Leseproblem elegant, ohne das Datenmodell zu aendern: Eine WITH RECURSIVE-Abfrage lauft solange, bis keine weiteren Kindknoten mehr gefunden werden, und liefert damit den kompletten Teilbaum in einer einzigen Anweisung. Fuer moderate Baumtiefen von wenigen Dutzend Ebenen und moderate Datenmengen ist dieser Ansatz oft vollkommen ausreichend und deutlich einfacher zu pflegen als Nested Sets oder Closure Table.

Die Grenzen rekursiver CTEs zeigen sich bei sehr haeufigen Teilbaum-Abfragen unter hoher Last, weil jede Abfrage die Rekursion erneut ausfuehren muss, ohne von vorberechneten Strukturen zu profitieren. Auch sehr tiefe Baeume, etwa mehrere hundert Ebenen, koennen bei manchen Datenbank-Engines an konfigurierbare Rekursionslimits stossen. Fuer Systeme mit seltenen Strukturaenderungen, aber sehr haeufigen, performance-kritischen Teilbaum-Abfragen lohnt sich der zusaetzliche Schreibaufwand von Nested Sets oder Closure Table, waehrend rekursive CTEs auf Adjacency List fuer die meisten Anwendungsfaelle der pragmatischste Startpunkt bleiben.

9. Alle vier Modelle im Vergleich

Die folgende Tabelle fasst die Kosten der vier Modellierungsstrategien fuer hierarchische Daten zusammen.

10. Zusammenfassung

Kein Modell fuer hierarchische Daten ist universell ueberlegen, jedes verschiebt den Aufwand zwischen Schreib- und Leseoperationen. Adjacency List ist beim Schreiben unschlagbar guenstig, verlangt aber rekursive CTEs fuer Teilbaum-Abfragen. Nested Sets liefert extrem schnelle Leseoperationen ueber einen einfachen Bereichsvergleich, bezahlt das aber mit teuren Schreiboperationen auf dem gesamten Baum.

Path Enumeration liegt bei Einfuegeoperationen nah an Adjacency List, verschiebt Nachfahren aber teuer bei einem verschobenen Teilbaum. Closure Table bietet den ausgewogensten Kompromiss zwischen Lese- und Schreibkosten, kostet dafuer zusaetzlichen Speicherplatz. Die richtige Wahl fuer hierarchische Daten ergibt sich aus dem tatsaechlichen Verhaeltnis von Schreib- zu Leseoperationen der konkreten Anwendung, nicht aus einer generellen Bestenliste.

11. FAQ: Hierarchische Daten modellieren