Baumstrukturen kommen in der Webentwicklung sehr häufig vor. Beispielsweise werden Navigationen häufig als Baum in einer Datenbank gespeichert. Jeder Navigationspunkt erhält dabei zusätzlich die ID des Vaterknotens. Dieses sehr häufig eingesetzte Verfahren ist leider alles andere als Optimal.
Was bringen Nested Sets
Die deutlich bessere Lösung heißt “Nested Sets”. Nested Sets haben den Vorteil gegenüber der herkömmlichen Variante, dass Lesezugriffe stark beschleunigt werden. Der Nachteil besteht im vergleichsweise langsamen Schreiben von Änderungen im Baum, sowie dem minimal größeren Speicheraufwand (der heutzutage vernachlässigbar ist). Ein weiterer Grund für die bisher nur geringe Verbreitung ist die vergleichsweise komplizierte Logik. Da Webseiten i.a. sehr viele Besucher haben, muss die Navigation sehr häufig aus der Datenbank gelesen werden. Deshalb ist der Nachteil des langsamen schreibens gegenüber dem gewalltigen Vorteil beim lesen vernachlässigbar.
Wie funktionieren Nested Sets
Denken wir uns die Navigation einer fiktive Seite:
Startseite
|__News
| |__Heute
| |__Archiv
| |__2005
| |__2006
| |__2007
|__Impressum
Wenn wir den Baum in eine Datenbank speichern möchten, müssen wir uns vorstellen, dass man den gesamten Baum von der Wurzel bis erneut zur Wurzel wie an einem langen Faden durchwandert. Jeder Knoten besitzt 2 Werte: einen linken- und einen rechten Knoten.
Wann immer man auf einen Knoten trifft, wird der linke Wert um eins erhöht. Außerdem wird ein interner Zähler im Faden ebenfalls um eins erhöht. Irgendwann wird man das Ende eines Astes erreichen. Ist das der Fall, so wandert der Faden auf die rechte Seite und von dort weiter zur linken Seite des nachfolgenden Asts.
Sollte es kein nachfolgenden Ast mehr geben, so gehen wir zurück zum übergeordneten Ast. Das ganze machen wir solange, bis wir die Wurzel des Astes wieder erreicht haben.
So ergeben sich die Daten für oben stehenden Baum:
links rechts 0 13 -> Startseite 1 12 -> News 2 3 -> Heute 4 11 -> Archiv 5 6 -> 2005 7 8 -> 2006 9 10 -> 2007 1 2 -> Impressum
Neuen Knoten einfügen
Den ersten (Wurzel) Eintrag in die Datenbank, wird so eingetragen:
INSERT INTO baum (name,links,rechts) VALUES ('Startseite',0,1);
Die Werte 0 bzw. 1 sind fest vorgegeben. Diese Werte werden sich im Verlauf der nachfolgenden Einfügeoperationen verändern. Wenn man einen weiteren Knoten in den Baum einfügen möchte, so sucht man sich den Knoten, an den der neue Knoten angehängt werden soll. Von diesem merkt man sich den linken und rechten Wert und verwendet diese als $LINKS bzw. $RECHTS.
UPDATE baum SET rechts=rechts+2 WHERE rechts >= $RECHTS;
UPDATE baum SET links=links+2 WHERE links > $LINKS;
INSERT INTO baum (name,links,rechts) VALUES ('News', $RECHTS, $RECHTS +1);
Lesen von Daten
Nachdem wir jetzt unseren Baum in der Datenbank haben, können wir diesen höchst effizient auslesen. Fangen wir mit einer einfachen Anfrage an, um den gesamten Baum auszulesen:
SELECT * FROM baum ORDER BY links;
Jetzt möchten wir zusätzlich noch die Tiefe des Knotens ermitteln. Folgende Abfrage hilft:
SELECT b1.name, COUNT(*)-1 AS ebene
FROM baum AS b1,
baum AS b2
WHERE b1.links BETWEEN b2.links AND b2.rechts
GROUP BY b1.links
ORDER BY b1.links;
Falls es das Datenbanksystem und Tabellenformat (z.B. InnoDB) zulässt sollten die Schreibzugriffe per Transaktion durchgeführt werden.
Löschen von Knoten und Ästen
Wer Knoten einfügt muss diese früher oder später auch wieder löschen. Die nachfolgenden Anfragen löschen den Knoten mit dem entsprechenden Links- und Rechtswert.
DELETE FROM baum WHERE links BETWEEN $LINKS AND $RECHTS; UPDATE baum SET links = links-ROUND(($RECHTS-$LINKS+1)) WHERE links>$RECHTS; UPDATE baum SET rechts = rechts-ROUND(($RECHTS-$LINKS+1)) WHERE rechts>$RECHTS;
Kommentare