:: handcode :: Selbstreferenzierende Bäume - klein - einfach

Selbstreferenzierende Bäume - klein - einfach - schnell

Immer wieder stellt sich die Aufgabe aus einer Datenbank eine hierarchische Struktur, also einen Baum zu erstellen.
In der Webprogrammierung sind die häufigsten Aufgaben das Erstellen von Strukturen für Produkte, Rubriken, Themen, Berechtigungen (Gruppen in Gruppen), Seitenstrukturen, usw.

Die beiden wohl am meisten verbreiteten Arten zur Abbildung von Bäumen in Datenbanken sind die klassischen Parent - Child Bäume und Nested Sets.

Nested Sets sind schick, lesend super schnell aber irgendwie sind sie doch meistens zu kompliziert sobald es dran geht den Baum schreibend zu pflegen.

Die klassischen Parent - Child Bäume haben dagegen den Ruf zwar einfach pflegbar, aber im lesenden Zugriff (vor allem auf Teilbäume) eher inperformant zu sein.
Oft kommen hier rekursive Funktionen zum Einsatz, vor allem um von einem Blatt wieder zurück zur Root zu kommen.

Wenn man den Baum aber "nur" aus Referenzen auf eine "flache" Liste der Knoten aufbaut, hat man damit einen schnellen, einfachen und direkten Zugriff auf alle Teilbäume.

Beispiel anhand einer kleinen Tabelle

+----+--------+--------------+ 
| id | parent | name         | 
+----+--------+--------------+ 
|  0 |      0 | ROOT         |  
|  1 |      0 | Knoten 1     |  
|  2 |      0 | Knoten 2     |  
|  3 |      1 | Knoten 1.1   |  
|  4 |      1 | Knoten 1.2   |  
|  5 |      2 | Knoten 2.1   |  
|  6 |      2 | Knoten 2.1   |  
|  7 |      3 | Knoten 1.1.1 |  
|  8 |      3 | Knoten 1.1.2 |  
+----+--------+--------------+

PHP:



<?php



$result = mysql_query('SELECT * FROM `tree` ORDER BY `parent`, `name`'); 

 

// Root "von Hand" definieren 

$nodes = array(0 => array('name' =>  'ROOT')); 

 

// Ueber das Ergebnis iterieren 

while ($row = mysql_fetch_assoc($result)) { 

   

  // Den aktuellen Knoten mit seiner id als key im nodes Array ablegen 

  $nodes[$row['id']] = $row; 

 

  // Hat der Parent des aktuellen Knotens schon Kinder? 

  if (! isset($nodes[$row['parent']])) { 

 

    // Wenn nein das childs-Array initialisieren 

    $nodes[$row['parent']]['childs'] = array(); 

     

  } 

 

  // Referenz auf den aktuellen Knoten im childs-Array des Parent 

  // erstellen. 

  $nodes[$row['parent']]['childs'][] =& $nodes[$row['id']]; 

 

 } 



?>

Das war's auch schon ;-)

Beispiele für den Zugriff:

PHP:



<?php



// der gesamte Baum 

print_r($nodes[0]); 



?>

PHP:



<?php



// Nur der Teilbaum des Knotens mit der ID 2 

print_r($nodes[2]); 



?>

Array
(
    [id] => 2
    [parent] => 0
    [name] => Knoten 2
    [childs] => Array
        (
            [0] => Array
                (
                    [id] => 5
                    [parent] => 2
                    [name] => Knoten 2.1
                )

            [1] => Array
                (
                    [id] => 6
                    [parent] => 2
                    [name] => Knoten 2.1
                )

        )

)

Soweit so gut, aber wie kommt man einfach von einem Blatt wieder zurück zum Root?

Auch kein Problem, wenn man beim aufbauen des Baumes z.B. bei jeden Knoten ein Array mit den IDs zurück zum root mitschreibt.
Natürlich könnte man auch als "back to the root" Info bei jedem Knoten eine Array von Referenzen zu den Elternknoten aufbauen, aber als Beispiel sollen hier mal die IDs reichen.

PHP:



<?php



$result = mysql_query('SELECT * FROM `tree` ORDER BY `parent`, `name`'); 

 

// Root "von Hand" definieren 

$nodes = array(0 => array('id' => 0, 

                          'name' =>  'ROOT', 

                          'to_root' => array())); 

 

// Ueber das Ergebnis iterieren 

while ($row = mysql_fetch_assoc($result)) { 

   

  // Den aktuellen Knoten mit seiner id als key im nodes Array ablegen 

  $nodes[$row['id']] = $row; 

 

  // Den Pfad "back-to-the-root" mitschreiben 

  $nodes[$row['id']]['to_root'] = $nodes[$row['parent']]['to_root']; 

 

  // ... und den parents des aktuellen Knotens dort mit aufnehmen 

  // Fuer die Reihenfolge Kind -> Root muessen wir immer eine neues 

  // Element an den Anfang des bestehenden Arrays einfuegen. 

  array_splice($nodes[$row['id']]['to_root'], 0, 0, $nodes[$row['parent']]['id']); 

 

  // Hat der Parent des aktuellen Knotens schon Kinder? 

  if (! isset($nodes[$row['parent']])) { 

 

    // Wenn nein das childs-Array initialisieren 

    $nodes[$row['parent']]['childs'] = array(); 

     

  } 

 

  // Referenz auf den aktuellen Knoten im childs-Array des Parent 

  // erstellen. 

  $nodes[$row['parent']]['childs'][$row['id']] =& $nodes[$row['id']]; 

 

 } 



?>

Dann hat man einfachen Zugriff auf alle Eltern ohne sich mit Rekursionen "rumplagen" zu müssen.

PHP:



<?php



// vom Knoten mit der Id 8 "back to the root" 

echo $nodes[8]['name'] . "\n";  

 

foreach ($nodes[8]['to_root'] as $parent) { 

  echo $nodes[$parent]['name'] . "\n"; 

} 



?>

ergibt:

Knoten 1.1.2
Knoten 1.1
Knoten 1
ROOT

Eigentlich ganz einfach oder?

Aber (wie immer) gibt es natürlich auch hier einen Haken:
Da immer die komplette Baumstruktur aus der DB gelesen und als Baum aufgebaut werden muss, auch wenn man nur ein kleiner Teilbaum benötigt wird, skaliert diese Methode nicht unendlich. Ab einer gewissen Größe des Baumes sollte man vielleicht doch z.B. Nested Sets verwenden.
Ab welcher Größe? Müsste man mal testen, aber ich denke merkliche Unterschiede wird es erst ab ein paar hundert oder tausend Knoten geben.

Und ganz ehrlich, meistens sind die Bäume doch eher kleiner oder?

Autor: Jens Giessmann in DB, PHP am Donnerstag, 28. Dezember 2006 um 22:21
Kommentare (0) | Trackbacks (0)

Tags für diesen Artikel: db, php, programming

Artikel mit ähnlichen Themen:

Trackbacks

Trackback-URL für diesen Eintrag

Keine Trackbacks

Kommentare

Ansicht der Kommentare: (Linear | Verschachtelt)

Noch keine Kommentare

Kommentar schreiben

Name
E-Mail
Homepage
Antwort zu
Kommentar	Die angegebene E-Mail-Adresse wird nicht dargestellt, sondern nur für eventuelle Benachrichtigungen verwendet. Um maschinelle und automatische Übertragung von Spamkommentaren zu verhindern, bitte die Zeichenfolge im dargestellten Bild in der Eingabemaske eintragen. Nur wenn die Zeichenfolge richtig eingegeben wurde, kann der Kommentar angenommen werden. Bitte beachten Sie, dass Ihr Browser Cookies unterstützen muss, um dieses Verfahren anzuwenden. Hier die Zeichenfolge der Spamschutz-Grafik eintragen: Umschließende Sterne heben ein Wort hervor (wort), per _wort_ kann ein Wort unterstrichen werden.
	Daten merken?