Während meiner zeitweise recht intensiven Beschäftigung mit der Programmiersprache PHP bin ich irgendwann mal über das Nested-Sets-Konzept gestolpert, eine faszinierende Methode zur Abbildung von hierarchischen Strukturen in einer relationalen Datenbank. Ein Ergebnis meiner Auseinandersetzung damit war der folgende Fachartikel, der 2003 im PHP-Magazin erschienen ist.

Jeder Programmierer steht früher oder später vor der Aufgabe, Baumstrukturen in einer Datenbank abbilden zu müssen - sei es für ein hierarchisches Diskussionsforum, die Navigation einer Website oder zur Abbildung einer Ordner- und Dateistruktur. Immer wieder ist bei Betrachtungen zu diesem Thema die Rede vom Nested Sets-Modell, vor dem jedoch viele Einsteiger und auch einige fortgeschrittene Anwender zurückschrecken, da es auf den ersten Blick kompliziert erscheint. Dieser Artikel möchte den Einstieg in dieses elegante und gleichzeitig performante Modell erleichtern.

Von den ungezählten Möglichkeiten, Baumstrukturen in SQL-Datenbanken abzubilden (ein Vergleich verschiedener Ansätze findet sich in Ausgabe 2.2002) ist das Nested Sets-Modell sicher eines der interessantesten. Seine Stärken spielt es insbesondere bei komplexen Bäumen aus, da es keine Beschränkungen bei der Verschachtelungstiefe gibt und auch keine performancekritischen Rekursionen nötig sind. Die immer wieder aufkeimenden Diskussionen in den einschlägigen Mailinglisten belegen jedoch, dass das zugrundeliegende Prinzip auf den ersten Blick schwer verständlich erscheint. Auf den zweiten Blick erschließt sich dem Entwickler jedoch die ganze Eleganz des Modells.

"Nested Sets" bedeutet wörtlich übersetzt "Verschachtelte Mengen". Abstrakt betrachtet bildet dabei jeder Knoten eine gemeinsame Menge mit seinen Kindern und ist gleichzeitig Teilmenge seiner übergeordneten Knoten (Abbildung 1). Aber die Nested Sets können noch mehr als aus der Mengendarstellung ersichtlich ist, denn sie speichern auch die Reihenfolge der Knoten auf einer Ebene (Abbildung 2).

Abbildung 1

Abbildung 1: Mengendarstellung

Abbildung 2

Abbildung 2: Hierarchische Darstellung

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

Doch bevor wir zum praktischen Teil kommen, betrachten wir uns noch einmal die linken und rechten Werte. Sortiert man diese aufsteigend und zeichnet darüber die entsprechenden Knoten, ergibt sich ein interessantes Bild (Abbildung 4), das uns an die Mengendarstellung in Abbildung 1 erinnert.

Auch wenn unser Beispielbaum nicht sonderlich komplex ist, lassen sich an ihm bereits alle wesentliche Merkmale der Nested Sets im Hinblick auf die linken und rechten Werte (im folgenden als LFT und RGT benannt) erkennen:

  • Die Wurzel hat grundsätzlich 1 als LFT-Wert
  • Die Sortierung der Knoten ergibt sich aus den LFT-Werten
  • Die Anzahl der Nachfahren eines Knotens errechnet sich durch (RGT - LFT - 1) / 2.
  • Entsprechend gilt für alle Knoten ohne Kinder: RGT - LFT = 1
  • LFT und RGT aller Nachfahren liegen zwischen den LFT- und RGT-Werten der Vorfahren

Diese Zusammenhänge sind der Grundstein für das performante Auslesen von Nested Sets aus einer relationalen Datenbank. Wir kommen darauf im folgenden noch mehrfach zurück.

Der Baum wird gepflanzt und wächst

Bevor wir unseren ersten Knoten (die Baumwurzel) erzeugen können, müssen wir zunächst die Datenbank-Tabelle anlegen. Streng genommen benötigt eine Baumstruktur nach dem Nested Sets-Modell lediglich zwei Felder (lft und rgt). Wir gönnen den Knoten unseres Baumes aber auch noch eine eindeutige id und ein kurzes Textfeld (name).

	CREATE TABLE tree (
		id    INT(12)      UNSIGNED NOT NULL AUTO_INCREMENT,
		name  VARCHAR(50)  NOT NULL,
		lft   INT(12)      UNSIGNED NOT NULL,
		rgt   INT(12)      UNSIGNED NOT NULL,
		PRIMARY KEY (id),
		key lft (lft),
		key rgt (rgt),
	);
	

Beim Aufbau des bereits aus den obigen Ausführungen vertrauten Baumes muss zunächst der Wurzelknoten eingefügt werden. Wir erinnern uns, dass für die Wurzel per Definition LFT=1 gilt. Da der Knoten (noch) keine Nachfahren hat, ergibt sich: RGT = 2. Folglich lautet unser Statement zum Erstellen der Wurzel:

	INSERT INTO tree (name,lft,rgt) VALUES ('Säugetiere',1,2);
	

Genießen Sie den Anblick dieses einfachen Statements, denn die folgenden Operationen werden teilweise erheblich komplexer. Halten Sie aber dennoch durch; denn Ihre Mühen werden mit ein paar wirklich faszinierenden Select-Abfragen belohnt. Im nächsten Schritt fügen wir das erste Kind des Wurzelknotens ein. Hierzu müssen wir zunächst ein wenig Platz zwischen dem LFT- und dem RGT-Wert der Wurzel schaffen. Genaugenommen müssen alle Vorfahren unseres neuen Knotens (in diesem Fall nur die Wurzel) einen um zwei erhöhten RGT-Wert erhalten. Ist der Platz geschaffen können wir anschließend gefahrlos den neuen Knoten einfügen:

	UPDATE tree SET rgt=rgt+2 WHERE rgt = 2;
	INSERT INTO tree (name,lft,rgt) VALUES ('Primaten',2,3);
	

Fügen wir als nächstes den Bruder "Nagetiere" ein. Hierfür benötigen wir zunächst wieder den LFT- und den RGT-Wert des Vorfahren (erneut der Wurzelknoten), für die im folgenden die Variablen $LFT und $RGT verwendet werden. Für den Wurzelknoten gilt zur Zeit $LFT = 1 und $RGT = 4.

	UPDATE tree SET rgt=rgt+2 WHERE rgt >= $RGT;
	INSERT INTO tree (name,lft,rgt) VALUES ('Nagetiere', $RGT, $RGT+1);
	

Wie bereits beim Einfügen des ersten Kindes erhöhen wir wieder den rechten Wert des Vorfahrens um zwei. Der neue Knoten erhält als linken Wert den ehemaligen rechten seines Vorfahrens und der rechte Wert ist um eins höher als der linke.

Bisher haben wir nur Knoten an das Ende der Struktur eingefügt und mussten folglich auch nur die RGT-Werte von bestehenden Knoten manipuliert werden. Gehen wir nun einen Schritt weiter und fügen das erste Kind des Knotens "Primaten" ein. Für diesen Knoten gilt in der aktuellen Tabelle $LFT = 2 und $RGT = 3.

	UPDATE tree SET rgt=rgt+2 WHERE rgt >= $RGT;
	UPDATE tree SET lft=lft+2 WHERE lft > $RGT;
	INSERT INTO tree (name,lft,rgt) VALUES ('Halbaffen', $RGT, $RGT +1);
	

Wiederholen wir nun diesen Schritt zum Einfügen des Knotens "Affen" (allerdings mit den neuen Werten des Vaters "Primaten": $LFT = 2 und $RGT = 5), ergibt sich die Tabelle 1.

Tabelle 1

Tabelle 1: Die SQL-Tabelle nach den Einfügeoperationen

Wer nun übrigens denkt, dass für jeden Fall eine spezielle Update-/Insert-Folge notwendig ist, liegt falsch. Denn bei näherer Betrachtung kann die letzte Befehlsfolge auch für die beiden vorangegangenen Operationen verwendet werden. Lediglich die Wurzelknoten bildet einen Sonderfall.

Dennoch muss an dieser Stelle zugunsten anderer Datenbankmodelle für Baumstrukturen eines festgehalten werden: Das Einfügen von Knoten ist der wunde Punkt der Nested Sets. Denn im schlimmsten Fall müssen bei der Einfügoperation die LFT-/RGT-Werte aller bestehenden Knoten verändert werden. Dies wirkt sich natürlich insbesondere bei sehr komplexen Bäumen negativ auf die Performance aus. Da in den allermeisten Anwendungen aber der lesende Zugriff sehr viel häufiger ist als der schreibende, braucht uns dies nicht weiter zu verunsichern.

Wenn der Baum von mehreren Administratoren oder gar Besuchern einer Website verändert werden kann (z.B. durch neue Beiträge in einem Diskussionsforum), sollte unbedingt darauf geachtet werden, dass es bei parallel durchgeführten Einfügeoperationen nicht zu Kollisionen kommt und so eventuell die LFT-/RGT-Werte durcheinander geraten. In MySQL lässt sich dies leicht durch das Sperren der Tabelle sicherstellen:

	LOCK TABLES tree WRITE;
	[...]
	UNLOCK TABLES;
	

In neueren MySQL-Versionen können für diesen Zweck auch Transaktionen eingesetzt werden (derzeit nur mit den Tabellentypen InnoDB und BerkleyDB). Nähere Informationen zu diesem Thema finden Sie im Artikel "MySQL auf der Überholspur" (Ausgabe 1.2002) sowie in der Online-Dokumentation von MySQL [3].

Blick auf den kompletten Baum

Kommen wir nun zu dem Punkt, an dem die Nested Sets uns für die ganzen Mühen beim Einfügen belohnen: dem komfortablen Auslesen der Struktur aus der Datenbank. Erinnern wir uns hierzu zunächst an die logischen Zusammenhänge (Aufzählung im ersten Abschnitt): "Die Sortierung der Knoten ergibt sich aus den LFT-Werten." Um alle Knoten in der richtigen Reihenfolge auszulesen benötigen wir also nur einen einfachen Select-Befehl:

	  SELECT name,
		FROM tree
	ORDER BY lft;
	

Das Ergebnis ist noch nicht sonderlich aussagekräftig, da es zwar die Reihenfolge der einzelnen Elemente beinhaltet, aber nicht die zuvor so mühsam definierten Abhängigkeiten zwischen den Knoten. Erweitern wir also unsere Abfrage und nutzen dafür einen weiteren logischen Zusammenhang: "LFT und RGT aller Nachfahren liegen zwischen den LFT- und RGT-Werten der Vorfahren".

	  SELECT n.name,
			 COUNT(*)-1 AS level
		FROM tree AS n,
			 tree AS p
	   WHERE n.lft BETWEEN p.lft AND p.rgt
	GROUP BY n.lft
	ORDER BY n.lft;
	
Tabelle 2

Tabelle 2: Alle Elemente des Baums mit ihrer Ebene

Das Resultat (siehe Tabelle 2) enthält nun alle Elemente des Baumes inklusive ihrer jeweiligen Ebene (level). Diese erhalten wir, indem wir mittels einer Tabellenverknüpfung alle Elemente zählen, bei denen die LFT-/RGT-Werte den LFT-Wert des aktuellen Knotens umschließen (also alle Vorfahren). Aufgrund der Tatsache, dass BETWEEN auch gleiche Werte mitzählt (in diesem Fall also auch den Knoten selbst), müssen wir von COUNT(*) eins abziehen. Diese Informationen reichen aus, um einen einfachen Baum darzustellen:

  • Säugetiere
    • Primaten
      • Halbaffen
      • Affen
    • Nagetiere

Für viele Anwendungen ist es notwendig darüber hinaus auch noch zu wissen, ob es sich um ein Blatt (Knoten hat keine Nachfahren) oder einen Ast (Knoten hat Nachfahren) handelt, und eventuell ist sogar die Anzahl der Nachfahren interessant. Greifen wir also erneut auf die logischen Zusammenhänge zurück: "Die Anzahl der Nachfahren eines Knotens errechnet sich durch (RGT - LFT - 1) / 2."

	  SELECT n.name,
			 COUNT(*)-1 AS level,
			 ROUND ((n.rgt - n.lft - 1) / 2) AS offspring
		FROM tree AS n,
			 tree AS p
	   WHERE n.lft BETWEEN p.lft AND p.rgt
	GROUP BY n.lft
	ORDER BY n.lft;
	
Tabelle 3

Tabelle 3: Alle Elemente des Baums mit Ebene und Anzahl ihrer Nachkommen

Als Ergebnis (Tabelle 3) erhalten wir nun für jeden Knoten neben der Ebene auch noch die Anzahl seiner Nachkommen (offspring). Wenn nötig können aber noch mehr Informationen ermittelt werden, zum Beispiel ob ein Knoten vorhergehende oder nachfolgende Geschwister hat:

	  SELECT n.*,
			 round((n.rgt-n.lft-1)/2,0) AS offspring,
			 count(*)-1+(n.lft>1) AS level,
			 ((min(p.rgt)-n.rgt-(n.lft>1))/2) > 0 AS lower,
			 (((n.lft-max(p.lft)>1))) AS upper
		FROM tree n,
			 tree p
	   WHERE n.lft BETWEEN p.lft AND p.rgt
		 AND (p.id != n.id OR n.lft = 1)
	GROUP BY n.id
	ORDER BY n.lft;
	

Bevor man jedoch zu solch komplexen Statements greift, sollte geprüft werden, ob diese Informationen wirklich benötigt werden. Denn auch MySQL benötigt seine Zeit für die entsprechenden Berechnungen - wenn auch deutlich weniger als eine nachträgliche Berechnung mittels PHP.

Blick auf Teilbäume

Kommen wir wieder zu einfacheren Ausdrücken. Bisher haben wir immer den kompletten Baum ausgelesen. Häufig werden jedoch in der Praxis nur Informationen über einen Teil des Baumes benötigt, zum Beispiel über den Weg von der Wurzel zu einem bestimmten Blatt. In diesem Zusammenhang erinnern wir uns noch einmal an die Regel: "LFT und RGT aller Nachfahren liegen zwischen den LFT- und RGT-Werten der Vorfahren". Den Pfad von der Wurzel bis zum Knoten mit id = 5 ("Affen") ermitteln wir also folgendermaßen:

	  SELECT p.*
		FROM tree n,
			 tree p
	   WHERE n.lft BETWEEN p.lft AND p.rgt
		 AND n.id = 5
	ORDER BY n.lft;
	

Selbstverständlich funktioniert das ganze auch umgekehrt, um beispielsweise die Struktur unterhalb des Knotens "Primaten" (id = 2) zu ermitteln:

	  SELECT o.name,
			 COUNT(p.id)-1 AS level
		FROM tree AS n,
			 tree AS p,
			 tree AS o
	   WHERE o.lft BETWEEN p.lft AND p.rgt
		 AND o.lft BETWEEN n.lft AND n.rgt
		 AND n.id = 2
	GROUP BY o.lft
	ORDER BY o.lft;
	

Blätter und Äste entfernen

Genau wie in der Natur können auch unsere Bäume wieder kleiner werden. Fangen wir - wie schon in den vorangegangenen Beispielen - wieder möglichst einfach an und lassen zunächst ein Blatt vom Baum fallen. Wir löschen das Blatt "Halbaffen" und passen anschließend die LFT-/RGT-Werte der verbleibenden Knoten an:

	DELETE FROM tree WHERE lft=3;
	UPDATE tree SET lft=lft-2 WHERE lft>4;
	UPDATE tree SET rgt=rgt-2 WHERE rgt>4;
	

Um auch Knoten löschen zu können, die Nachfahren haben, verallgemeinern wir die Operation ein wenig. Wiederum sehen wir dabei das LFT-/RGT-Werte als gegeben. Sind diese nicht bekannt, müssen diese zuvor über eine Select-Abfrage ermittelt werden.

	DELETE FROM tree WHERE lft BETWEEN $LFT AND $RGT;
	UPDATE tree SET lft=lft-ROUND(($RGT-$LFT+1)) WHERE lft>$RGT;
	UPDATE tree SET rgt=rgt-ROUND(($RGT-$LFT+1)) WHERE rgt>$RGT;
	

Sollen die Nachfahren nicht verloren gehen, sondern statt dessen auf die Ebene des gelöschten Knotens verschoben werden, wird es wieder etwas komplexer:

	DELETE FROM tree WHERE lft = $LFT;
	UPDATE tree SET lft=lft-1, rgt=rgt-1
	 WHERE lft BETWEEN $LFT AND $RGT;
	UPDATE tree SET lft=lft-2 WHERE lft>$RGT;
	UPDATE tree SET rgt=rgt-2 WHERE rgt>$RGT;
	

Wer bis zu diesem Punkt durchgehalten und die Beispiele nachvollzogen hat, wird hoffentlich feststellen, dass die Nested Sets so kompliziert nicht sind. Wer das Prinzip einmal verstanden hat, wird auch in der Lage sein, Algorithmen zu erstellen, um Knoten oder ganze Teilbäume zu verschieben. Wer es einfacher mag, kann sich auch einer seit kurzem verfügbaren PEAR-Klasse bedienen (siehe Kasten "Nested Sets ganz einfach").

Nested Sets ganz einfach

Wer sich beim Einsatz von Nested Sets die Arbeit vereinfachen möchte oder sich nach der Lektüre dieses Artikels noch nicht auf Anhieb im Stande sieht, Nested Sets produktiv einzusetzen, wird seit kurzem auch in PEAR [4] fündig. Unter dem Namen DB_NestedSet hat Daniel Khan eine Klasse veröffentlicht, die alle wichtigen Funktionen zum Manipulieren und Auslesen von Nested Sets-Strukturen über eine einfache API zur Verfügung stellt. Dabei macht er auch Gebrauch von einigen Erweiterungen des Modells (siehe Kasten "Reine Lehre?"). Die Klasse befindet sich zwar derzeit noch im Beta-Stadium, was sich nach Auskunft des Autors jedoch nur auf den Event listener sowie den PEAR::MDB-Support bezieht. Beispiele und eine API-Dokumentation finden Sie auf der Projekthomepage [5]

Performance

Neben der nun hoffentlich ersichtlichen Eleganz der Nested Sets wird ihnen auch immer wieder eine hohe Performance beim Auslesen von Baumstrukturen zugesprochen. Mit einem kleinen Test soll überprüft werden, inwiefern diese Aussage zutrifft. Verglichen werden dabei die drei Modelle aus dem bereits erwähnten Artikel "Weltenbaum - Selbstreferenzierende Bäume in MySQL" (Ausgabe 2.02):

  • Parent-Modell (1):
    Die Kinder eines Knotens enthalten im Feld parent die id ihres Vorfahren
  • Pfad-Modell (2):
    Jedes Element enthält in einem Feld vom Typ varchar den kompletten Pfad (0001-0004-0002)
  • Nested Sets-Modell (3):
    Hier werden die im Kasten "Reine Lehre?" erwähnten Erweiterungen genutzt.

Für den Test benötigen wir zunächst eine etwas komplexere Baumstruktur als in unseren bisherigen Beispielen. Der Beispielbaum verfügt über fünf Hauptäste, die wiederum jeweils fünf Äste besitzen, diese wieder usw. (bis zur fünften Ebene). Die gesamte Struktur verfügt über 3.905 Knoten - ein Umfang, den gut besuchte Diskussionsforen schnell erreichen können. Der Beispielbaum wird für alle drei Modelle in eine gemeinsame Tabelle geschrieben, deren Struktur aus Tabelle 4 ersichtlich ist.

Im ersten Testlauf wollen wir alle Nachfahren des Knotens 1 ermitteln. Hierbei kommen folgende Abfragen zum Einsatz:

Tabelle 4

Tabelle 4: Die drei Modelle des Vergleichs in einer Tabelle.

	(1) SELECT * FROM tree
		 WHERE parent=2;
	   (rekursiv für jede ermittelte ID)
	=> 1.217 sek.

	(2) SELECT * FROM tree
		 WHERE path LIKE '0001%'
	  ORDER BY path;
	=> 0.044 sek.

	(3) SELECT * FROM tree
		 WHERE root=1
	  ORDER BY lft;
	=> 0.039 sek.
	

Bereits bei diesem ersten Testlauf trennt sich die Spreu vom Weizen: Das Parent-Modell fällt glatt durch. Es ist um den Faktor 31 langsamer als das Nested Sets-Modell und immerhin noch um den Faktor 27 langsamer als das Pfad-Modell. Im übrigen kann mit dem einfachen Parent-Modell auch keine Reihenfolge von Knoten innerhalb einer Ebene ermittelt werden.

Gehen wir nun den umgekehrten Weg und ermitteln alle Vorfahren des Knotens 1-2-3-4-5:

	(1) SELECT * FROM tree WHERE id=245;
		SELECT * FROM tree WHERE id=240;
		SELECT * FROM tree WHERE id=221;
		SELECT * FROM tree WHERE id=158;
		SELECT * FROM tree WHERE id=1;
	=> 0.002 sek.

	(2) SELECT * FROM tree
		WHERE path='0001-0002-0003-0004-0005';
		SELECT * FROM tree
		WHERE path='0001-0002-0003-0004';
		SELECT * FROM tree
		WHERE path='0001-0002-0003';
		SELECT * FROM tree
		WHERE path='0001-0002';
		SELECT * FROM tree
		WHERE path='0001';
	=> 0.003 sek.

	(3) SELECT p.*
		  FROM tree n,
			   tree p
		 WHERE n.lft BETWEEN p.lft AND p.rgt
		   AND n.lft = '485'
		   AND n.root = 1
		   AND p.root = 1
	  GROUP BY p.id
	  ORDER BY p.lft DESC
	=> 0.005 sek.
	

Unser nächster und letzter Test soll alle Knoten der ersten Ebene inklusive der Anzahl ihrer Nachfahren ermitteln (eine typische Anwendung für ein Diskussionsforum):

	(1) SELECT * FROM tree
		 WHERE parent=1; (rekursiv für jede ermittelte ID)
		=> 35.279 sek.

	(2) SELECT n.*,count(*) AS offspring
		  FROM tree n, tree o
		 WHERE LENGTH(n.path)=4
		   AND o.path LIKE CONCAT(n.path,'-%')
	  GROUP BY n.id
	  ORDER BY path
		=> 0.051 sek.

	(3) SELECT *,
			ROUND((n.rgt-n.lft-1)/2) AS offspring
		  FROM tree
		 WHERE level = 1
	  ORDER BY root;
		=> 0.001 sek.
	

Was sagen uns diese Ergebnisse? Zunächst einmal, dass das Parent-Modell - wie nicht anders zu erwarten war - durch seine zwangsläufig rekursiven Abfragen für umfangreichere Strukturen ausscheidet. Das Pfad-Modell kann in einigen Einsatzgebieten durchaus mit den Nested Sets mithalten - zumal auch für dieses Modell Erweiterungen denkbar sind, die die Performance weiter verbessern (zum Beispiel durch das Speichern der Nachfahren für jeden Knoten). Nicht vergessen werden darf aber in diesem Zusammenhang, dass das Pfad-Modell gegenüber den Nested Sets nicht beliebig skalierbar ist, da sowohl die Anzahl der Elemente auf einer Ebene als auch die Anzahl der Ebenen beschränkt ist. Wer sich darüber keine Gedanken machen möchte, sollte also lieber zu den Nested Sets greifen, zumal diese spätestens mit dem Erscheinen der PEAR-Klasse DB_NestedSet sehr einfach genutzt werden können.

Reine Lehre?

Das in diesem Artikel vorgestellte Nested Sets-Modell basiert auf dem ursprünglichen Ansatz von Joe Celko [1], den auch Kristian Köhntopp in [6] vorstellt. In Ergänzung dieser "reinen Lehre" haben sich zwischenzeitlich einige Erweiterungen etabliert, die unter Beibehaltung des Grundmodells einige Vorteile bieten.

Sehr beliebt ist hierbei das Speichern von mehreren Bäumen in einer Tabelle bzw. das Aufteilen einer großen in mehrere kleine Nested Sets-Strukturen. Hierfür wird ein zusätzliches Feld root_id benötigt, in dem die id des jeweiligen Wurzelknotens abgelegt wird. Beispiele für diesen Ansatz beschreibt Daniel T. Gorski unter [2].

Eine andere hilfreiche Erweiterung ist die zusätzliche Speicherung der Ebene, die zum Beispiel Daniel Khan in seiner PEAR-Klasse DB_NestedSet [4] nutzt. Hierdurch werden sonst notwendige Tabellenverknüpfungen beim Auslesen der Struktur überflüssig.

Über dieses Dokument / Lizenz

Dieser Artikel erschien erstmalig in PHP-Magazin, Ausgabe 4.03. Das Urheberrecht liegt bei Arne Klempert. Der Autor gestattet die Vervielfältigung, Verbreitung und/oder Änderung unter einer der beiden folgenden Lizenzen:

  • GNU Freie Dokumentationslizenz: Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts.
  • Creative Commons (CC-BY-SA): Namensnennung, Weitergabe unter gleichen Bedingungen

Auch wenn die Lizenzen es nicht unbedingt erfordern, würde ich mich freuen, über entsprechende Nutzungen informiert zu werden.

Weitere Ressourcen