Im einführenden Beitrag zu CakePHP habe ich bereits kurz über das Tree Behavior gesprochen und kurz angedeutet, wofür dies verwendet werden kann. Da dieses Behavior zum einen ein Kern Behavior ist (also bei CakePHP standardmäßig dabei), aber auch regen Gebrauch findet, widme ich diesem teilweise komplizierten Behavior einen dezidierten Beitrag mit Anwendungsbeispiel und ausführlichen Erklärungen.
Das Tree Behavior findet immer dann Anwendung, wenn eine sortierte oder verschachtelte Liste (nested set) in einer Datenbank gespeichert werden soll. Hierfür muss das Tree Behavior zum einen an das jeweilige Modell angehängt werden
public $actsAs = array('Tree');und die Datenbank vorbereitet werden, da das Tree Behavior drei zusätzliche Felder benötigt.
Dies sind parent_id, lft (left) und rght (right).
Das Feld parent_id adressiert das übergeordnete Element in einer verschachtelten Liste oder NULL, wenn das aktuelle Element auf oberster Ebene sein soll.
Die Felder lft und rght dienen dazu die Reihenfolge der Elemente festzulegen.
Ebenso ist durch die beiden Felder eine einfache Suche und Abfrage über die Liste möglich (warum dies so ist, wird später deutlich).
Der genaue Nutzen der Felder lft und rght wird deutlich, wenn man sich die Theorie dazu anschaut:
Das Tree Behavior stützt sich auf das in der Informatik bewährte Konzept des Tiefensuchbaums oder auch Depth First Search (DFS).
Da man eine Webseitennavigation als verschachtelte Liste auffassen kann, bauen wir unser Beispiel auf folgende Liste auf:
Die Elemente Home, Universities, Impress und Team befinden sich auf oberster Ebene der Liste und haben daher keine Elternknoten. Das Feld parent_id ist _NULL _(vgl. Tabelle unten). Überträgt man alle Elemente in eine Tabelle mit Datensatz-ID, Titel und parent_id Feld, erhält man folgendes Ergebnis:
| id | title | parent_id | lft | rght |
|---|---|---|---|---|
| 1 | Home | NULL | 1 | 2 |
| 2 | Universities | NULL | 3 | 10 |
| 3 | Impress | NULL | 11 | 12 |
| 4 | Team | NULL | 13 | 20 |
| 5 | University of Duisburg-Essen | 2 | 4 | 5 |
| 6 | University of Cologne | 2 | 6 | 7 |
| 7 | University of Munich | 2 | 8 | 9 |
| 8 | Administrators | 4 | 14 | 15 |
| 9 | Coordinators | 4 | 16 | 17 |
| 10 | Content-Assistants | 4 | 18 | 19 |
Doch wie kommen die Felder lft und rght zustande? Dies ist nicht ganz einfach zu erklären.
Zunächst muss man die verschachtelte Liste als Baum aufzeichnen (siehe Bild).
Ausgehend von der Wurzel (NULL), welche selbst nicht explizit in der Datenbank gespeichert wird, muss man jeweils den Kind-Knoten “besuchen”, welcher noch nicht besucht wurde und am weitesten links liegt.
Um dies zu verdeutlichen durchlaufen wir ein paar Elemente des Baumes:
Der erste linke nicht besuchte Knoten ist “Home”.
Navigiert man nun also von _NULL _zu Home, muss im Feld lft eine 1 eingetragen werden, da man erst einen Schritt gegangen ist.
Home selbst hat keine Kind-Knoten, sodass man nun zum Elternknoten zurückgehen muss.
Hierfür muss jedoch immer der Umweg über sich selbst genommen werden.
Dieser Umweg wird ebenfalls als ein Schritt gezählt und die Anzahl im Feld rght festgehalten.
Daraus resultiert der Wert 2 für das Feld rght des Home-Knotens.
{% include image.html caption=“Abbildung 1: Aufgespannter Baum der Beispielnavigationsstruktur” file=“Treebehavior.png” %}
Das ist der dritte Weg, den man gehen musste, also bekommt der Knoten “Universities” im Feld lft den Wert 3.
Universities hat Kinderknoten.
Hier muss jeweils wieder der am weitesten links gelegene gewählt werden: University of Duisburg-Essen.
Wenn man dort hingeht, sind wir 4 Wege gegangen.
lft ist also 4 für diesen Kind-Knoten.
Der Knoten selbst hat keine Kinder und man muss erneut den Umweg über ihn selbst gehen, rght ist daher 5.
– Das Prinzip sollte nun klar sein.
Sortiert man die Einträge anhand des Feldes lft oder rght, kann eine sortierbare bzw.
sortierte Liste realisiert werden.
Möchte man bspw.
Impressum und Team tauschen, so ändern sich die lft und rght-Werte für Impress, Team und alle Unterknoten von Team.
Da dies automatisch vom Framework über das Tree Behavior berechnet wird, muss man sich jedoch keine Gedanken machen.
Es reicht der Aufruf der Methode moveUp($id) und das Framework berechnet alle Werte selbstständig neu.
Durch diese beiden Felder ist es zum Beispiel auch möglich alle Kinder-Knoten eines Elternknotens zu ermitteln:
Gebe mir alle Knoten zurück, wo die lft-Werte größer oder gleich dem lft-Wert und die rght-Werte kleiner oder gleich dem rght-Wert des Elternknotens sind.