Nested Sets: effizient Baumstrukturen in Datenbanken speichern

nested sets baumstruktur in Datenbank speichernBaumstrukturen 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;

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen