MPTT Modified Preorder Tree Traversal
1. Dezember 2009 Roland
Nee, das ist keine Krankheit sondern eine Möglichkeit seine Bäume im Griff zu haben 
Ich bin beim CakePHP Programmieren darüber gestolpert.
Wenn du dort Bäume verwalten willst, dann kannst du das Tree Behaviour verwenden.
Bäume sind sehr praktisch, wenn du deine Daten hierachisch anordnen willst.
Wenn du z.B. das Organigramm einer Firma abbilden willst, dann kannst du eine Baumstruktur verwenden:
So können die einzelnen Mitarbeiter schön einer Abteilung, und die Abteilung am Ende der Firma zugeordnet werden.
Baumstrukturen kannst du auch gut verwenden, wenn du mal in die Verlegenheit kommst eine Navigation zu erstellen. Dort gibt es normalerweise Hauptpunkte und Unterpunkte. Und je nach Auftritt kann man das noch beliebig schachteln.
Irgendwie müssen nun die einzelnen Elemente in einer Datenstruktur abgelegt werden.
Bei MPTT werden die einzelnen Knoten so durchnummeriert, dass immer klar ist wo der linke und der rechte Knoten des entsprechenden Knotens liegt.
Unser Organigramm wird wie folgt durchnummeriert:
Wenn du nun deine Knoten mit einem Algrorithums durchläufst, musst du nur die Nummern entlanghangeln. Anhand der Information, ob dein Knoten links angelaufen werden soll, oder ob er rechts verlassen wird, kannst du schnell die hierachische Darstellung entsprechend aufbauen.
Du läufst somit an deinem ersten Knoten auf der linken Seite los, gehst zum Folgeknoten ebenfalls auf die linke Seite und verlässt den Folgeknoten auf der rechten Seite. Das machst du so lange, bis zu zu deinem ersten Knoten auf der rechten Seite wieder vorbeikommst.
Hier ein Bildchen, dass diese Aktion für die Abteilung Finanzen durchläuft:
Bei dieser Traversierung handelt es sich um eine lineare Aktion, die im Rechner sauschnell durchgeführt werden kann.
Wie sieht beim CakePHP MPTT die Datenstruktur aus?
Ich nehm nun als Beispiel die Abteilung Finanzen. Die IDs sind frei erfunden. Ich geh einfach mal davon aus, dass die Firma die ID 1 hat…
Bei CakePHP wurde für das Tree Behaviour folgende Datenstruktur angewendet:
| id | lft | right | parent_id | some data |
| 2 | 2 | 9 | 1 | Abteilung Finanzen |
| 3 | 3 | 4 | 2 | Franz Bauer |
| 4 | 5 | 6 | 2 | Gundula Gerber |
| 5 | 7 | 8 | 2 | Helga Wichtig |
Wozu wird die parent_id verwendet?
Um schnell alle Kinderknoten eines Knotens selektieren zu können, wurde die parent_id mit eingebunden. Für das native MPTT wird das nicht benötigt.
Wie du sehen kannst, handelt es sich bei der Abbildung in der Datenbank um eine flache Tabelle. Diese Struktur kann selektiert und in Arrays abgelegt durchlaufen werden.
Falls du mal einen etwas komplexeren Baum kreieren willst, dann mach das nicht von Hand. Du verzählst dich garantiert!
Es ist der Horror diese Datenstruktur “zu Fuß” zu befüllen.
Bei CakePHP übernimmt dies vollumfänglich das entsprechende Modell. Und das ist auch vernünftig so.
Diese Art von Bäumen abzubilden ist für den lesenden Zugriff sehr schnell. Das liegt daran, dass eine flache Hierachie hinterlegt wurde, die durch eine lineare Iteration durchlaufen werden kann.
Das Einfügen von neuen Knoten irgendwo im Modell bedingt jedoch einige Updates. Alle anderen Knoten müssen entsprechend angepasst werden. Somit ist diese Baumstruktur Darstellung nicht sehr sinnvoll, falls du viele Updates und Inserts hast.
Bei Organigrammen, Navigationen usw. werden die Daten jedoch häufiger gelesen als geschrieben. In solchen Fällen ist das MPTT eine coole Sache.
Fazit
Als ich meinen ersten Baum in CakePHP aufgebaut habe, bin ich fast verzweifelt. Das MPTT ist ein einfaches Pattern. Aber wenn man nicht weiß wie man es bedienen muss, oder wenn man glaubt man kann es von Hand betreuen, dann geht man unter. Die Befüllung sollte nur über entsprechende Automaten erfolgen.
Im täglichen Gebrauch ist dieses Pattern sehr angenehm zu verwenden. Seit ich dieses Pattern verwende, sind meine Navigationen deutlich dynamischer und einfach zu verändern. Natürlich nur über eine entsprechende Oberfläche 
Artikel mit ähnlichen Schlagwörtern
Der Beitrag wurde am Dienstag, den 1. Dezember 2009 um 00:34 Uhr veröffentlicht und wurde unter Design Pattern, IT abgelegt.
Dir gefiel der Artikel? Dann abonniere doch den RSS Feed
Du kannst die Kommentare zu diesem Eintrag durch den RSS 2.0 Feed verfolgen. Du kannst einen Kommentar schreiben, oder einen Trackback auf deiner Seite einrichten.
