Bäume in MySQL

Baumstrukturen sind weit verbereitet in der EDV. Jedes aktuelle Betriebssystem kennt "Verzeichnisse" oder "Ordner" die beliebig verschachtelt werden können und auch viele moderne Applikationen beschränken sich nicht mehr auf eine feste Anzahl von Ebenen. Aber wie legt man so einen Baum in einer (SQL-)Datenbank ab?

Kenne Deine Eltern...

Mir waren bisher zwei Modelle bekannt: Parent und Childs. Beim Parent-Modell enthält jede Datenbankzeile einfach die ID der übergeordneten Zeile. So ein Baum lässt sich ziemlich einfach von einem Blatt zum Stamm durchlaufen, weil die nächste ID in jedem Datensatz enthalten ist. Außerdem ist ein Parent-Baum ziemlich resistent gegen Inkonsistenzen und lässt sich sehr schnell schreiben. Selbst das Löschen geht recht schnell, weil zunächst nur der tatsächlich betroffene Datensatz gelöscht werden muss. Im Hintergrund oder per regelmäßigem (Cron-)Job können dann alle Elemente gelöscht werden, deren Parent nicht mehr existiert. So räumt sich die Datenbank von selbst auf und der aktuelle Konsistenzzustand ist jederzeit bekannt. Alternativ kann die Parent-Spalte auch mit einem Fremdschlüssel auf die gleiche Tabelle belegt werden (sofern dies unterstützt wird), dann übernimmt der Datenbankserver die Konsistanzprüfung.

...oder Kinder

Die Childs-Variante lässt sich dagegen schneller von der Wurzel zu den Blättern lesen, bringt aber einige Probleme mit sich. Jede Zeile muss eine Liste der IDs ihrer Kinder enthalten - entweder in einer Spalte oder über eine Mapping-Tabelle (die Probleme mit zu vielen Kindelementen vermeidet und sich leichter durchsuchen lässt). Um das Eltern-Element zu bestimmen, müssen im schlimmsten Fall die Childs-Listen aller anderen Elemente durchsucht werden. Ein Element kann dabei mehrere Eltern oder sogar sich selbst als Elternelement haben. Ob eine solche Konstellation gewünscht ist, hängt von der Applikation ab.

Eine wissenschaftliche Lösung

Eine weitere Variante, so habe ich heute gelernt, ist das Nested Sets Modell. Es ist nicht so einfach verständlich wie die vorgenannten, dafür lassen sich alle Arten von Lese- und Statistikoperationen sehr schnell ausführen. Arne Klempert beschreibt den Aufbau eines Nested Sets Baum in seinem gut geschriebenen Artikel. Seine Benchmark-Ergebnisse möchte ich allerdings anzweifeln - in einem normalen Parent-Modell sollte die Parent-Spalte indiziert sein - damit sollte sich die Query-Zeit massiv verbessern lassen. Zumindest beim Path-Modell wären auch leicht alle möglichen Path-Werte in einem Query abrufbar.

Praktische Umsetzung

Das Modell liest sich für mich wie eine Erfindung der theoretischen Informatik (oder Mathematik). Bei vielen Lese- und Statistikoperationen halte ich es auch für die beste Lösung, allerdings besteht meine aktuelle Problemstellung aus mehr Schreib- als Leseoperationen und einem sehr großen Datenbestand.

Dabei ist es nicht möglich, die komplette Tabelle zu sperren und viele Zeilen zu ändern um eine neue Zeile einzufügen oder zu löschen. Eine Transaktion würde das Risiko von inkonsistenten Daten zwar reduzieren, aber effektiv trotzdem große Teile der Tabelle locken. Bei row-based-locks können dann je nach Datenbank sogar die Anzahl der im System verfügbaren Locks überschritten werden.