Nested Set

Ein Nested Set ist eine Datenstruktur, die verwendet wird, um hierarchische Daten wie Baumstrukturen (z.B. Organisationshierarchien, Kategoriebäume) in einer flachen, relationalen Datenbanktabelle zu speichern. Diese Methode bietet eine effiziente Möglichkeit, Hierarchien zu speichern und Abfragen zu optimieren, die ganze Unterbäume betreffen.

Hauptmerkmale des Nested Set Modells

1. Linke und rechte Werte: Jeder Knoten in der Hierarchie wird durch zwei Werte dargestellt: den linken (lft) und den rechten (rgt) Wert. Diese Werte bestimmen die Position des Knotens im Baum.

2. Hierarchie repräsentieren: Die linken und rechten Werte eines Knotens umfassen die Werte aller seiner Kinder. Ein Knoten ist Elternteil eines anderen Knotens, wenn seine Werte innerhalb des Bereichs der Werte dieses Knotens liegen.

Beispiel

Betrachten wir ein einfaches Beispiel einer hierarchischen Struktur:

1. Home
   1.1. About
   1.2. Products
       1.2.1. Laptops
       1.2.2. Smartphones
   1.3. Contact

Diese Struktur kann als Nested Set wie folgt gespeichert werden:

Abfragen

• Alle Kinder eines Knotens finden: Um alle Kinder eines Knotens zu finden, kann man die folgenden SQL-Abfrage verwenden:

SELECT * FROM nested_set WHERE lft BETWEEN parent_lft AND parent_rgt;

Beispiel: Um alle Kinder des Knotens "Products" zu finden, verwendet man:

SELECT * FROM nested_set WHERE lft BETWEEN 4 AND 9;

Pfad zu einem Knoten finden: Um den Pfad zu einem bestimmten Knoten zu finden, kann man diese Abfrage verwenden:

SELECT * FROM nested_set WHERE lft < node_lft AND rgt > node_rgt ORDER BY lft;

Beispiel: Um den Pfad zum Knoten "Smartphones" zu finden, verwendet man:

SELECT * FROM nested_set WHERE lft < 7 AND rgt > 8 ORDER BY lft;

Vorteile

• Effiziente Abfragen: Das Nested Set Modell erlaubt es, komplexe hierarchische Abfragen effizient zu beantworten, ohne dass rekursive Abfragen oder mehrere Joins erforderlich sind.
• Leichtes Auslesen von Unterbäumen: Das Lesen aller Nachkommen eines Knotens ist sehr effizient.

Nachteile

• Komplexität bei Modifikationen: Einfügen, Löschen oder Verschieben von Knoten erfordert eine Neuberechnung der linken und rechten Werte vieler Knoten, was komplex und ressourcenintensiv sein kann.
• Schwierige Wartung: Das Modell kann schwieriger zu warten und zu verstehen sein als einfachere Modelle wie das Adjacency List Modell (Verwaltung von Eltern-Kind-Beziehungen durch Parent-IDs).

Das Nested Set Modell ist besonders nützlich in Szenarien, in denen die Daten hierarchisch strukturiert sind und häufig Abfragen auf Unterbäumen oder auf der gesamten Hierarchie durchgeführt werden müssen.