Datenstruktur: Nested Sets

Dieser Artikel sollte überarbeitet werden.
Die Regeln für GlossarWiki-Artikel sollten beachten werden.

Von Wurzeln, Ästen, Blättern und einem Wurm

Um dieses Prinzip in der Datenbank abzubilden, behilft sich das Modell mit einem einfachen System: Jedes Element des Baumes erhält zwei Werte - einen linken und einen rechten, die fortlaufend durch die gesamte Struktur bei jedem Schritt um eins erhöht werden. Joe Celko [1] bedient sich zur Verdeutlichung eines Wurmes, der - an der Wurzel beginnend - den gesamten Baum durchwandert. Der Wurm hinterlässt bei jedem Knoten, den er besucht, eine Nummer und erhöht anschließend seinen Zähler um eins. Dabei wird zunächst immer erst der linke Wert gesetzt. Gelangt der Wurm an das Ende eines Astes (Blatt), springt der Wurm von der linken auf die rechte Seite und wandert von dort weiter zur linken Seite des nächsten Knotens. Folgen keine weiteren Blätter oder Äste, geht er wieder zurück zum letzten übergeordneten Knoten, bis er schließlich wieder an der Wurzel des Baumes ankommt.

Abbildung 3 Abbildung 3: Weg durch die Struktur

Um das Prinzip besser zu verstehen, verfolgen wir nun den Weg des Wurmes Schritt für Schritt anhand der bereits eingeführten Beispielstruktur (Abbildung 3): Der Weg beginnt beim linken Wert des Wurzelknotens ("Säugetiere"). Dieser besitzt per Definition den Wert 1. Das erste Kind des Wurzelknotens ("Primaten"), erhält als linken Wert die 2. Der rechte Wert bleibt - wie bereits beim Wurzelknoten - zunächst frei, da erst die Kinder des Knotens abgearbeitet werden müssen. Folglich erhält der Knoten "Halbaffen" den linken Wert 3. Da dieser Knoten keine Kinder hat, hinterlässt der Wurm als rechten Wert die 4 und macht sich auf zum nächsten Knoten auf der aktuellen Ebene ("Affen"). Da auch dieser keine Kinder hat, notiert der Wurm das Wertepaar 5 und 6. Da auf dieser Ebene keine weiteren Knoten folgen, geht der Wurm wieder zurück zum zuletzt besuchten Knoten, bei dem er keinen rechten Wert hinterlassen hat ("Primaten"), um dies mit dem nächsten Wert (7) nachzuholen. Von hier aus geht es dann auf der Ebene weiter zu den "Nagetieren", wo mangels Kindern direkt 8 und 9 hinterlassen werden. Anschließend wandert der Wurm, da es keine weiteren Geschwister gibt, erneut nach oben, erreicht soe wieder den Wurzelknoten ("Säugetiere") und setzt dort schließlich den rechten Wert auf 10.

Sie sollten sich an dieser Stelle unbedingt die Zeit nehmen, den Weg des Wurmes nachzuvollziehen, da dieser für das Verständnis der Nested Sets wesentlich ist. Sie müssen übrigens keine Angst haben, dass Sie bei der Verwendung von Nested Sets zu einem Wurm mutieren und fortan auf endlos erscheinenden Pfaden durch Ihre Baumstruktur wandeln müssen. Denn diese undankbare Arbeit nehmen uns glücklicherweise ein paar SQL-Statements gerne ab.

Abbildung 4 Abbildung 4: Mengen über fortlaufenden linken bzw. rechten Werten

Weitere Infos gibts unter http://www.klempert.de/nested_sets/