Bäume in relationalen Datenbanken
Um meinen Blog nicht ganz verkommen zu lassen habe ich mich entschlossen, mal wieder etwas zu verfassen. Diesmal möchte ich mich ein wenig mit der Datenstruktur Baum auseinandersetzen und deren Speicherung in einer relationalen Datenbank. Der einfache Teil hierbei ist die Datenstruktur. Hier ist der klassische Fall einer 1-zu-n Beziehung. Jeder Knoten kann beliebige Kind-Knoten haben aber nur einen übergeordneten (Eltern)Knoten. Daher macht es wenig Sinn, die Kinder eines Knotens zu speichern sondern lediglich den übergeordneten Knoten. Dieser lässt sich einfach durch einen Fermdschlüssel auf den Primärschlüssel der eigenen Tabelle darstellen. Dies könnte wie folgt aussehen:
Beim einfügen und ändern des Baumes muss man also nur die entsprechenden Fremdschlüssel korrekt pflegen. Etwas komplizierter ist es beim auslesen. Die erste Lösung die mir hierbei in den Kopf gekommen ist, ist das ganze rekursiv zu lösen. Dabei hat man eine Funktion die alle Kinder des Wurzel-Knoten liest, und sich anschließend selbst für jeden gefundenen Knoten aufruft um wiederum dessen Kinder zu bestimmen. Dies funktioniert auch einwandfrei und ist nicht sonderlich kompliziert. Allerdings besitzt es den Nachteil, dass sehr viele Querys abgeschossen werden müssen, nämlich eins pro Knoten. Je nach Größe des Baumes kann dies sicherlich nicht ganz unwesentlich sein. Auch Rekursion im Allgemeinen sollte man vermeiden sofern es Alternativen gibt.
Wegen dieser Probleme habe ich noch einmal über das Problem nachgedacht und bin auf eine Lösung mit einer, bzw. ggf. zwei Schleifen und lediglich einem Query gekommen. Dabei macht man sich die Tatsache zunutze, dass Objekte in PHP als Referenz übergeben werden. Man liest also mit einem Query alle Knoten aus der Datenbank aus und schreibt sie alle als Objekte in ein Array, wobei ihnen ihre id als Schlüssel zugeordnet wird. Nun erweitert man die Objekte um ein Attribut wie z.B. children, welches wiederum ein leeres Array ist. Zusätzlich definiert man sich noch einen Wurzel-Knoten mit der selben Eigenschaft, auf welchen man gesondert verweist. Nun iteriert man über alle Knoten und schreibt jeden Knoten in das children-Attribut des Vaters. Sollte kein Vater vorhanden sein, fügt man den Knoten in das Wurzel-Element ein. Und anschließend kann man über das Wurzel-Element wunderschön auf den gesamten Baum zugreifen. Und um das Ganze etwas zu veranschaulichen, hier ein grobes Codebeispiel, unter Nutzung einer Datenbankklasse:
<?php
$nodes = db()->select( 'beispiel' )->objects( 'id' );
$root = new stdClass();
foreach( $nodes as $node )
if( $node->parent ) $nodes[$node->parent]->children[] = $node;
else $root->children[] = $node;
?>