Status Quo
Ein häufige Programmieraufgabe ist es baumartige Strukturen abzubilden, also Strukturen in denen jeder Knoten einen Baumes beliebig viele Unterknoten besitzen kann, die jeweils wieder beliebig viele Unterknoten besitzen können etc.
Diese Strukturen kennt jeder, wenn er sich mal genauer Filesystem-Browser (z.B. den Windows-Explorer o.ä), strukturierte Webkataloge oder ähnliche Tools angeschaut hat: Verzeichnisse (Knoten) enthalten Dateien und Verzeichnisse, die ihrerseits wieder Dateien und Verzeichnisse enthalten. Diese Schachtelung erfolgt dabei beliebig tief.
Nun, in Filesystem-Browsern erfolgt die Darstellung rekursiv, da der ganze darzustellende Baum mittels Pointern im RAM offensichtlich schnell genug durchlaufen werden kann. Was ist aber, wenn man aus einer relationalen SQL-Datenbank Daten performant holen möchte, um diese als einen Baum mit z.B. HTML zu visualisieren?
Die mit Abstand schlechteste Idee ist es, verkettete Listen mit Rückwärts- bzw. Vorwärtsreferenzen in der Datenbank zu erzeugen und ebenfalls rekursiv für jeden Knoten eines vermeintlichen SQL-Baumes eine separate Query an die Datenbank abzusetzen.
Solange der darzustellende Baum klein bleibt, werden Performanceverluste nicht augenscheinlich und fallen nicht ins Gewicht, aber bei größerer Datenmengen wird die Datenbank bei diesem Verfahren zwangsläufig in die Knie gehen müssen, da hunderte von Queries den Server verstopfen können.
Merke:
- Nie rekursive Queries an die Datenbank absetzen, wenn es sich vermeiden lässt.
Mit “Nested Sets” (verschachtelten Mengen), einfachen Kenntnissen der Relationalen Algebra und wenig SQL-Verständnis lassen sich binäre und allgemeine Bäume abbilden, ohne dass es im Datenbanklayer zu Rekursion kommen muss. Relationale Algebra ist auch das interne Arbeitsprinzip der meisten SQL-Datenbanken.
Dieses Tutorial beschreibt einen Ansatz für ein Threaded Forum mit Nested Sets in einer abstrakten Form. Den Anfang macht ein visuelles Modell.
Das visuelle Modell
Um einen Baum in einer SQL-Datenbank darstellen zu können, bieten sich sog. “Nested Sets” – verschachtelte Mengen – an. Für das Auslesen einer beliebig tiefen Baumstruktur benötigt man dann nur einen einzigen Datenbank-Query.
Hat man eine Oracle-Datenbank zur Hand, so ist es unnötig auf die hier beschriebene Methode auszuweichen, da Oracle den SQL-Befehl CONNECT BY (PRIOR) beherrscht, und sich somit leicht verkettete Datensätze samt ihrem Grad (Einrückungstiefe, LEVEL) herauslesen lassen. Mehr zu CONNECT BY findet sich in der freundlichen Oracle-Dokumentation.
Das gleiche gilt für IBM’s Datenbank DB2. Dort läßt sich eine “konventionelle” Baumdarstellung mittels verketteter Listen dadurch effizient gestalten, dass rekursive Queryies direkt von der Datenbank unterstützt und optimiert werden. Für nähere Informationen dazu siehe RECURSIVE QUERY der “SQL Reference” von DB2.
Beides sind jedoch proprietäre Erweiterungen von Oracle / IBM und kein Standard-SQL, also in der Regel bei anderen DBMS nicht verfügbar. Die “Nested Set Modellierung” arbeitet dagegen auch auf Systemen effizient, die nur einen minimale SQL Standard unterstützen.
Ein Baumast mit zwei Blättern läßt sich als Menge folgendermaßen abbilden:
Mengen (Blätter) B und C sind Untermengen der Menge A, also Kinder der Wurzel A. In unseren Beispielen verwenden wir einfachheitshalber nur binäre Bäume – also Bäume mit nur jeweils höchstens zwei Kindern. Selbstverständlich ist die Technik auch auf allgemeine Bäume, deren Knoten wiederum beliebig viele Kind-Knoten enthalten können, anwendbar.
Was hier im Modell offensichtlich ist, muß in einer Datenbanktabelle nicht nur als solches gekennzeichnet werden, es muß auch die Reihenfolge (B vor C) gespeichert werden.
Für diese Speicherung der Abhängigkeit innerhalb einer solchen Struktur benötigen wir zwei Tabellenfelder (im Folgenden LFT und RGT gennant). Die Payload, also die Nutzlast des Knotens beschränkt sich in unseren Beispielen zunächst nur auf einen Buchstaben (A .. n), um die verschiedenen Knoten des Baumes benennen zu können.
Dies sei ein Beispielknoten mit der Nutzlast und dem Zahlenpaar, das die Abhängigkeiten repräsentiert:
Um die Reihenfolge der Knoten zu sichern, speichern wir in den LFT- und RGT-Feldern Zahlen, die uns beim Herauslesen der Daten ermöglichen, mit dem den sog. Preorder-Walk den Baum zu traversieren (zu durchlaufen) – beim Preorder-Walk bedeutet das, dass zuerst der Wurzel-Knoten, dann alle Knoten, die “links” vom jeweiligen Vaterknoten, danach alle Knoten die “rechts” davon liegen, gelesen werden.
Die LFT- und RGT-Zahlenpaare setzen sich für unseren kleinen Beispielbaum folgendermaßen zusammen:
Das Verständnis für die LFT- und RGT-Zahlen ist essentiell, um das Nested-Sets-Prinzip zu erfassen: von der ersten LFT-Zahl (die “1″ im Wurzel-Knoten A) ausgehend, wird zuerst das linke Blatt (B) durchlaufen, danach das rechte (C). Bei dieser Traverse – einfach den Pfeilen folgen – wird jeweils eine Zählervariable um den Wert 1 inkrementiert, und zuerst im LFT- und dann nochmals inkremetiert im RGT-Feld gespeichert.
Das zweite Beispiel sieht damit nicht mehr so kompliziert aus:
Ausgehend von der Wurzel A wird wiederum jeweils der linke Teilbaum durchlaufen, dann jeweils der rechte. Die LFT- und RGT-Zahlen werden in der vorgebenen Reihenfolge inkrementiert. Besitzt ein Kind-Knoten seinerseits Kinder, so wiederholt sich die Prozedur ebenfalls für diesen Kind-Knoten etc.
Die Reihenfolge des Preorder-Walks ist den Pfeilen oder einfach nur dem Gesetz des Alphabetes zu entnehmen. Dieser Nested Sets-Baum würde in einer seiner Nutzformen den Baum darstellen, der im rechten Teil der Grafik abgebildet ist.
Die Mengendarstellung dieses Baumes könnte folgendermaßen aussehen:
Aufgrund der verschiedenen Zahlenabhängigkeiten kann man sich leicht vorstellen, dass die Nested Sets-Technik sich primär für Strukturen eignet, die nur gelesen werden müssen, z.B. die Darstellung von Forumsbeiträgen oder Katalog- und Menübäumen, da bei jeder Änderung des Baumes alle Abhängigkeiten geändert werden müssen. Bei Forumsbeiträgen oder ähnlichen Bäumen kann man davon ausgehen, das in 95% der Fälle der Zugriff lesend erfolgt.
Bäume die sich öfters dynamisch verändern (müssen) – z.B. Sortierung – werden mit dieser Technik ausgebremst.
