Nested Sets / Modified Preorder Tree Traversal (MPTT) verstehen und anwenden

Baum

Die sogenannten “Nested Sets” (auch bekannt unter dem Namen “Modified Preorder Tree Traversal” oder MPTT) ermöglichen es, hierarchische Strukturen in relationalen Datenbanken abzubilden. Das ist natürlich nichts besonderes, allerdings haben Sie mit diesem Modell die Möglichkeit, den gesamten Strukturbaum mit einem einzigen SQL Statement auszulesen und somit eine enorme Ressourcenverschwendung, die bei der herkömmlichen Lese-Variante mit einem rekursiven Lesezyklus auftritt (dem sogenannten Adjacency List Modell), zu vermeiden.

Dieses Tutorial wird Ihnen die Anwendung des Modells der Nested Sets näherbringen. Ebenso wird parallel zur Erklärung des Funktionsprinzips eine entprechende PHP- Klasse implementiert. Besonderer Dank gilt Jörg Siebhahn für seine Expertise und tatkräftige Unterstützung.

Benötigte Umgebung für dieses Tutorial

In diesem Tutorial verwende ich eine einfache LAMP Umgebung mit PHP 5.1.6 sowie einer MySQL Datenbank (v. 5.0.24). Die Logik kann aber sehr einfach in jede andere Sprache / jedes andere DBMS übernommen werden. Weiters wird das PEAR::DB Package zum Herstellen der Datenbankverbindung genutzt. Je nach Geschmack kann man die Verbindungen auch selbst aufbauen oder ebenfalls auf PEAR zurückgreifen.

Nach diesem Tutorial…

…kennen Sie die prinzipielle Funktionsweise von Nested Sets und deren Einsatzgebiet. Weiters haben Sie eine Klasse in PHP entwickelt, mit der Sie Nested-Sets-Bäume auslesen, neue Knoten einfügen und Teilbäume löschen können. Weitere Funktionen (wie etwa das Verschieben von Teilbäumen) werden in einem fortführenden Tutorial erläutert. Um die Problemstellung zu verstehen, möchte ich zuerst erläutern, was man unter hierarchischen Strukturen verstehen kann. Hierarchische Strukturen kommen jedem Softwareentwickler in seiner beruflichen Laufbahn vielfach unter.

Beispiele für den Einsatz hierarchischer Strukturen:

  • Website Menüs (Sitemaps)
  • Waren- und Produktgruppen
  • Familien-Stammbaum
  • Unternehmensstrukturen

Eine Hierarchie besteht immer aus einem Elternknoten, dem mindestens ein Kindknoten untergeordnet ist.

Fallbeispiel: Frischwarenladen „Vitamine & mehr“

Als Fallbeispiel für ein einfacheres Verständnis, möchte ich den Frischwarenladen „Vitamine & mehr“ mit seinem (zugegeben sehr beschränkten) Produktsortiment heranziehen. Die Produkte sind in unterschiedliche Warengruppen hierarchisch gegliedert. Diese Struktur soll nun mit Hilfe der Nested Sets gespeichert und ausgelesen werden.

Hierarchische Struktur der Warengruppen des Frischwarenladens „Vitamine & mehr“:

Die hier angewandte Darstellung möchte ich als „klassische“ Ansicht bezeichnen. Diese typische Darstellungsform kennen Sie zum Beispiel von der Verzeichnisauflistung in verschiedenen Dateimanagern (Windows Explorer etc.). Die Struktur wird immer von oben nach unten und von links nach rechts gelesen. Die rote Zahl neben jedem Element stellt die ID dar – meist in Form eines Primärschlüssels.

Verarbeitung hierarchischer Daten mit dem Adjacency List Modell („klassische Form“)

Um diese Warenstruktur in einer „zweidimensionalen“ Tabelle zu speichern, wird klassischerweise die „Adjacency List“ Methode verwendet. Ich bezeichne sie sinnvollerweise auch gerne als „is_child_of“ Methode. Dass heisst, dass jeder Knoten über eine eigene ID verfügt (rote Zahl) und zusätzlich die ID des jeweiligen Elternknotens in jedem Datensatz gespeichert wird. Wie Sie sehen können, wird beim Frischwarenladen (dem Wurzelelement oder „Root“) ein NULL Wert eingetragen (die letzte Spalte existiert normalerweise nicht und soll nur zum leichteren Verständnis dienen). Damit ist klar, dass es sich bei diesem Element um das erste der Hierarchie handelt. Bei allen weiteren Elementen wird in der Spalte „is_child_of“ der Wert der Spalte „key“ des Elternelements und somit die Struktur gespeichert:

  • Obst (ID: 2) ist ein Kind von Frischwarenladen (ID: 1) und hat daher den Wert 1 in der Spalte „is_child_of“
  • Birnen (ID: 6) ist ein Kind von Obst (ID: 2) und hat daher den Wert 2 in der Spalte „is_child_of“
  • Fisolen (ID: 10) ist ein Kind von Gemüse (ID: 8) und hat daher den Wert 10 in der Spalte „is_child_of“
  • usw.

Dieses Verfahren ist eine Möglichkeit, hierarchische Daten sehr schlank und einfach administrierbar in einer Tabelle zu speichern. Nun jedoch kommen wir zum eigentlichen Problem bei diesem Modell: Das Auslesen.

Rekursives Auslesen der Daten (Adjacency List Modell – „klassische Form“)

Nachdem wir die Daten in der Tabelle gespeichert haben, ist es nun an der Zeit, eine Funktion zum Auslesen zu erstellen. Diese Funktion muss beim Root-Knoten beginnen (in unserem Fall der Frischwarenladen) und sich Schritt für Schritt durch den Strukturbaum „suchen“. Eine recht schöne Form für diesen Algorithmus ist das Erstellen einer einzigen rekursiven Funktion, die jeweils die Kinder eines Knotens zurückliefert und sich selbst bei jedem Knoten aufruft. Diese könnte beispielsweise folgendermaßen aussehen:

// $parent ist die ID des Elternknotens, dessen Kinder 
 // wir sehen möchten 
 // $level wird mit jedem Ebenensprung um den Wert 1 
 // erhöht und nur zur Anzeige genutzt 
 function getTreeAdjacency($parent, $level) { // Alle Kinder von $parent auslesen 
     $sql='SELECT key,name FROM tbl_tree WHERE key='.$parent.';'; 
     $result = $this->_db->query($sql); // Jedes Kind anzeigen 
     while ($result->fetchInto($row)) { // Einrücken und Anzeigen des Knoten Namens 
         echo str_repeat('---',$level).$row['name'].' '; 
         // Diese Funktion erneut aufrufen, um die Kinder dieses Knotens auszulesen (Rekursion) 
         getTreeAdjacency($row['key'], $level+1); 
     } 
 }

Führt man diese Funktion aus, wird die Warenstruktur unseres Frischwarenladens sauber formatiert ausgegeben. Eine einfache und schnelle Lösung. Leider gibt es auch hier, wie bei vielen scheinbar simplen Lösungen, einen Haken: Liest man in unserem Beispiel den gesamten Baum aus, wird die Funktion insgesamt zehn mal ausgeführt. Das bedeutet wiederum, dass auch 10 SQL Queries an den Datenbankserver gesandt werden. Diese Last ist bei unserem Beispiel natürlich kein Problem. Geht man aber von sehr umfangreichen Struktur (mit beispielsweise 500 Knoten) und vielen Aufrufen aus, stößt man sehr schnell an die Grenzen der Serverleistung (vor allem des DBMS).

Beispiel für hohe Lasten bei Leseoperationen mit dem Adjacency List Modell:

  • 500 Elemente
  • 100 Zugriffe pro Minute (z.B. Seitenaufrufe)
  • = 50.000 SQL Abfragen pro Minute
  • = 840 SQL Abfragen pro Sekunde

Anhand dieser „Milchmädchenrechnung“ wird schnell klar, dass dieses Modell für große Systeme (mit vielen Leseoperationen) nicht geeignet ist. Wenden wir uns daher dem eigentlichem Thema zu, den Nested Sets.

Verarbeitung hierarchischer Strukturen mit Nested Sets

Zu Beginn müssen wir unsere bestehende Struktur aus einem neuen „Blickwinkel“ betrachten. Soll heißen, dass die Darstellung der Warenhierarchie in einer Baumstruktur (anstelle der oben gezeigten Listenstruktur) für das bessere Verständnis meiner Meinung nach zwingend notwendig ist. Bäume wachsen in der Informatik von oben nach unten:

 

Wie Sie erkennen können, ist hier die identische hierarchische Datenstruktur wie in unserem ursprünglichen Diagramm abgebildet. Diese Darstellungsform bezeichnet man passenderweise als Baumdiagramm.

„Die kleine Raupe“

Um die Struktur für die weitere Verwendung vorzubereiten, stellen Sie sich vor, eine kleine Raupe klettert durch den gesamten Baum. Von Blatt zu Blatt, von Ast zu Ast und von links nach rechts. Und bei jeder Blattseite wird eine Ziffer notiert, die je Schritt um den Wert 1 erhöht wird (beginnend bei 0 am Wurzelelement an der linken Seite). Diese „Blatt-Werte“ werden als „Left Order“ und „Right Order“ bezeichnet. Bei insgesamt 10 Elementen gibt es demnach 20 Left- & Right-Order Werte (von 0 bis 19).

Speichern der Hierarchie nach dem Nested Sets Modell in der Datenbank

Die Daten aus dem Diagramm müssen nun in die Datenbank aufgenommen werden. Dafür legen wir eine Tabelle an mit den zusätzlichen Spalten „lft“ und „right“ an. In diesen Spalten werden die Left-Order und Right-Order des jeweiligen Elements gespeichert.

Hinweis: Bennenen Sie die Spalten für den Left- und Right-Order Wert nicht mit „LEFT“ bzw. „RIGHT“, da diese beiden Bezeichnungen in den meisten DMBS reservierte Worte sind („LEFT JOIN, RIGHT JOIN…“)

Nun sind alle Elemente in der Datenank gespeichert. Anhand der Left- und Right-Order Werte (Spalten „lft“ und „rgt“) ist es uns jetzt möglich, die Daten mit einem einzigen SQL Statement auszulesen und abzubilden.

Vor- und Nachteile von Nested Sets

Nachdem Sie die grundlegende Logik von Nested Sets (und deren Abbildung in einer Datenbank) nun kennen, möchte ich die Entwicklungsarbeit kurz unterbrechen und nun auf weitere Vor- und Nachteile von Nested Sets eingehen. Einen großen Vorteil haben Sie ja bereits kennengelernt:

  • (+) Hohe Performance bei Leseoperationen
    Leseoperationen sind wesentlich schneller, da die Daten nur ein einziges mal aus der Datenbank abgefragt werden müssen. Dadurch sinkt die Last Ihres DBMS im Vergleich zum Adjacency List Modell enorm..
  • (+) Sortierung der Knoten auf einer Ebene
    Weiters haben Sie mit Nested Sets die Möglichkeit, die Reihung der Knoten eines Zweiges (also jene, die sich unterhalb des selben Elternknotens auf der selben Ebene befinden) durch die Left-Order und Right-Order Werte bereits auf Datenbankebene auszulesen.
  • (-) Stukturänderungen benötigen viel Last
    Im Gegensatz zu den Lesenoperationen benötigen Änderungen an der Struktur sehr viel Performance. Zum Beispiel: Wird ein Knoten mitten im Baum gelöscht, so müssen alle nachfolgenden Knoten „nachgezogen“, dass heisst neu durchnummeriert, werden. Beim Verschieben von Teilbäumen artet das möglicherweise in einen regelrechten „Query-Hagel“ auf Ihren Datenbankserver aus.
  • (-) Kein eindeutiger Composite-Key vorhanden

Beim Adjacency List Modell besteht die Möglichkeit, aus der ID des Elternknotens und dem Bezeichner eines Elements, einen Composite-Key (dt. „zusammengesetzter Schlüssel“) zu erzeugen. Dadurch ist es möglich, Doubletten bereits auf Datenbankebene zu verhindern. Dieses Logik wenden beispielsweise Filesysteme an. Bei Nested Sets kommt man nicht darum herum applikationsseitig zu prüfen, ob auf einer Ebene zwei Elemente mit dem selben Namen existieren.

Den Strukturbaum nach dem Nested Sets Modell aus der Datenbank auslesen

Wie man an dem Diagramm schön erkennen kann, bilden die Left- und Right-Order Werte die Beziehungen zwischen den Knoten ab. Wir können dies nun wie folgt definieren:

Definition der Knotenbeziehung (Eltern-Kind Beziehung):

  • Bedingung 1: Alle Knoten, deren Left-Order Wert GRÖSSER als der des Elternknotens ist UND
  • Bedingung 2: alle Knoten, deren Right-Order Wert KLEINER als der des Elternknotens ist
  • liegen unterhalb dieses Elternknotens.

Da dies sehr theoretisch klingt, hier ein Beispiel anhand unseres Frischwarenladens:

  • Unterhalb des Knotens Gemüse(LEFT=13, RIGHT=18) liegen die Elemente
    • Paprika (LEFT=14, RIGHT=15), da der Left-Order Wert von Paprika größer dem Left-Order Wert von Gemüse (14 > 13) und der Right-Order Wert von Paprika kleiner dem des Knotens Gemüse ist (15<18).
    • Fisolen (LEFT=16, RIGHT=17), da der Left-Order Wert von Fisolen größer dem Left-Order Wert von Gemüse (16 > 13) und der Right-Order Wert von Fisolen kleiner dem des Knotens Gemüse ist (17 < 18)

Sie sehen, das Prinzip ist wirklich sehr einfach und effektiv.

Hinweis: Beachten Sie, dass immer BEIDE Bedingungen erfüllt sein müssen (logische UND-Verknüpfung). Ist nur eine Bedingung erfüllt, zum Beispiel nur der Left-Order Wert des Kind Knotens > dem Left-Order Wert des Elternknotens, erhalten Sie falsche Ergebnisse.

Auslesen des Strukturbaums

Nachdem das grundlegende Prinzip von Nested Sets nun klar ist, können wir eine erste Funktion (oder Methode) entwerfen, die die Daten aus der Datenbank ausliest und ausgibt.

SELECT * FROM tbl_tree WHERE lft BETWEEN 0 AND 19 ORDER BY lft ASC

Dieses einfache SQL Statement liefert uns nun alle Knoten unterhalb des Root Elements Frischwarenladen. Natürlich ist das nur die halbe Miete, da wir ja nicht davon ausgehen können, dass immer genau 10 Elemente in der Tabelle gelistet sind. Außerdem erreichen wir damit noch keine Einrückung der Kindknoten bei der Anzeige. Implementieren wir dieses SQL Statement nun in eine Funktion, so sieht diese wie folgt aus:

Funktion zum Auslesen des Nested Sets Baums (gesamt):

<?php
 function getNestedSetsTree($rootID)
 { 
     /**
      * Zuerst müssen wir den Left-Order und Right-Order Wert des Root Knotens ermitteln 
      */
     $sql = 'SELECT lft, rgt FROM `tbl_tree` WHERE `key`=\''.$rootID.'\''; 
     $result = $this->_db->query($sql); 
     $result->fetchInto($row);
 
     /**
      * Erzeugen eines leeren Array Stacks, der die Ebenen mitloggt (zur Anzeige von Einrückungen bei der Ausgabe
      */
       $right = array(); 
       
     /**
      * Auslesen aller Kindknoten des Root Knotens
      */
     $sql = ' SELECT * ' .'FROM `tbl_tree` ' .'WHERE ' .'lft BETWEEN '.$row['lft'].' ' .'AND '.$row['rgt'].' ' .'ORDER BY `lft` ASC'; 
     $result = $this->_db->query($sql);
 
     /**
      * Anzeigen der Knoten 
      */
      while ($result->fetchInto($row)) { 
      
         /**
          * Stack nur prüfen, wenn sich bereits Elemente im Stack befinden
          */
         if (count($right)>0) { 
         
             /**
              * Prüfen, ob Knoten vom Stack entfernt werden sollen
              */ 
             while ($right[count($right)-1] array_pop($right); 
         } 
               
      } 
          
      /**
       * Knoten anzeigen (mit Einrückung)
       */
      echo str_repeat('---',count($right)).$row['name'].' '; 
      
      /**
       * Aktuellen Knoten auf den Stack legen
       */
      $right[] = $row['rgt'];
 }

Der Funktion wird die ID (key) jenes Knotens übergeben, von dem aus alle Kindknoten ausgelesen werden sollen. Möchten wir (in unserem Beispiel) die gesamte Produktkategoriesierung auslesen, rüfen wir die Funktion mit getNestedSetsTree(1) auf, wobei 1 der Key unseres Elements „Frischwarenladen“ ist. In Zeile 4 werden dann die Left-Order und Right-Order Werte des übergebenen Elements ermittelt. Diese verwenden wir dann in Zeile 14 um alle Kindelemente dieses Knotens, nach der bereits bekannten Regel, auszulesen. In Zeile 30 wird bei einem Ebenensprung nach oben der letzte Knoten von unserem Hilfsstack entfernt. Dadurch können wir für jeden Knoten die Ebene ermitteln und ihn anschließend in Zeile 36 entsprechend einrücken. In Zeile 39 wird bei jedem Durchlauf der aktuelle Knoten auf den Stack gelegt. Das war es auch schon. Die Funktion zum Auslesen eines Baums, basierend auf dem Nested Sets Modell, ist somit fertiggestellt.

Löschen eines Knotens

Nachdem die Funktion zum Auslesen des Strukturbaums fertiggestellt ist, möchte ich nun mit der Funktion zum Löschen eines Knotens (mitsamt seiner Kindknoten) fortfahren, da diese Operation ein weing einfacher als das Einfügen eines neuen Knotens ist. Den Löschvorgang kann man sich in zwei Schritten sehr einfach vorstellen:

  1. Löschen des Knotens sowie all seiner Kindknoten
  2. Nachziehen aller nachfolgenden Knoten

Um den Löschvorgang in unserem Beispiel auch anwenden zu können, fügen wir zuerst in die Methode zum Auslesen (getNestedSetsTree() ) einen Link namens „Löschen“ ein, der bei der Ausgabe neben jedem Element angezeigt wird. Dazu erweitern wir einfach die Zeile für die Ausgabe wie folgt:

// Knoten anzeigen (mit Einrückung) 
 echo str_repeat('---',count($right)) . '' . $row['name'] . ' | Löschen ';

Nun geht es mit der eigentlichen Funktion zum Löschen los.

Atomisieren der SQL Queries – Transaction Lock

Nachdem die Operation zum Löschen aus mehreren SQL Queries besteht, empfehle ich, diese Mithilfe von Transaction Locks zu atomarisieren. Nach außen hin wirkt die gesamte Operation somit wie ein einzelner SQL Query und mögliche Unterbrechungen zwischen den einzelnen Queries haben keine Auswirkung auf die Datenstruktur. Weitere Informationen zum Thema Transaction Lock (LOCK, COMMIT, ROLLBACK) bei den unterschiedlichen DBMS, finden Sie im Internet und für MySQL in der MySQL Dokumentation.

Hinweis: Beachten Sie bitte, dass Transaction Locks beim Einsatz von MySQL nur beim Tabellentyp „InnoDB“ möglich sind!

Aufbau der Funktion deleteNode($nodeID)

Als Parameter übergeben wir an die Funktion zum Löschen die ID (den key) jenes Knoten, der gelöscht werden soll ($nodeID) Als erster Schritt werden die nötigen Variablen initialisiert und die Tabelle gelockt (atomarisierung). Im zweiten Schritt müssen wir den Left- und Right-Order Wert des zu löschenden Knotens ermitteln:

SELECT lft, rgt FROM tbl_tree WHERE key = $nodeID

Dieses Vorgehen kennen Sie ja bereits schon aus der Aulese-Funktion. Diese beiden Werte speichern wir für die spätere Verwedung in den Variablen $parentNodeLft und $parentNodeRgt. Nachdem wir auch alle Kindknoten des zu löschenden Knotens entfernen möchten, muss unsere Funktion zuerst wissen, wieviele Kinder unser „Elternknoten“ hat. Dafür wenden wir folgende Regel an:

Kinder eines definierten Elternknotens sind jene Elemente, deren Left-Order Wert GRÖSSER dem des Elternknotens ist und deren Right-Order Wert KLEINER dem des Elternknotens ist.

Diese Regel lässt sich jetzt recht einfach in einen SQL Query umformen, der uns die Anzahl der Kindknoten zurückliefert:

SELECT COUNT(tbl_tree.key) AS childcount FROM tbl_tree AS tbl_tree WHERE tbl_tree.lft > $parentNodeLft AND tbl_tree.rgt < $parentNodeRgt LIMIT 0,1;

Die ermittelte Anzahl der Kindknoten speichern wir in der Variable $childCount. Aus diesem Wert berechnen wir nun die Variable $removeItemCount. Diese benötigen wir, um die nachfolgenden Elemente nach dem Löschvorgang „nachzuziehen“. Ich addiere zu $childCount den Wert 1 (da der „Array“ des Strukturbaumes bei 0 und nicht bei 1 beginnt) und multipiziere ihn mit 2, da es ja einen Left- und einen Right-Order Wert gibt. Nun kommen wir zum eigentlichen Löschvorgang. Dieser stellt uns vor keine schwierige Aufgabe, da wir Left-Order und Right-Order Wert des Elternelements sowie die Regel zum ermitteln aller Kinder bereits kennen. Somit können wir den gesamten Löschvorgang in einem einzigen Query erledigen:

DELETE FROM tbl_tree WHERE left >= $parentNodeLft AND rgt <= $parentNodeRgt

Hinweis: Beachten Sie, dass der Vergleich im SQL Query hier mit >= bzw.bzw. < durchführen, würden Sie nur die Kinder des Knotens entfernen.

Der löchrige Baum

Nachdem wir nun mit dem DELETE Statement einen Ast aus dem Strukturbaum „geschnitten“ haben, entsteht ein „Loch“ in der Nummerierung der Knoten. Damit dieses Loch geschlossen wird und wieder ein sauberer Struktrubaum entsteht, müssen wir nun alle Knoten, die nach dem entfernten Ast liegen, nachziehen. Um diese Operation durchführen zu können, haben wir am Beginn unserer Funktion die Anzahl aller Elemente die gelöscht werden soll ermittelt und dadurch den Wert $removeItemCount errechnet. Diesen Wert müssen wir nun bei allen Elementen subtrahieren, deren Right-Order Wert GRÖSSER dem Right-Order Wert unseres zu löschenden Elements ist und deren Left-Order Wert GRÖSSER dem Left-Order Wert unseres zu löschenden Elements ist. Diese Operation müssen wir auf zwei getrennte SQL Queries aufteilen: Aktualisierung der Right-Order Werte:

UPDATE tbl_tree SET rgt = rgt - $removeItemCount WHERE rgt > $parentNodeRgt

Aktualisierung der Left-Order Werte:

UPDATE tbl_tree SET lft = lft - $removeItemCount WHERE lft > $parentNodeLft

Nun wäre unsere Funktion zum Löschen eines Astes eigentlich fertiggestellt, allerdings würde in der jetzigen Form noch keine Änderung an der Datenquelle zu sehen sein. Der Grund: Nachdem ich hier tranaktionsbasiert arbeite, müssen wir dem SQL Server noch ein COMMIT senden und die gesperrten Tabellen wieder freigeben. Erst dann werden alle SQL Queries in einem Zug verarbeitet.

Das war nun wirklich der letzte Schritt. Die gesamte Funktion sieht nun wie folgt aus:

Funktion zum Löschen eines Knotens (gesamt):

<?php
 /**
  * Created by PhpStorm.
  * User: mfuerst
  * Date: 10.08.2015
  * Time: 10:50
  */
 
 /**
  * Löscht den Knoten $nodeID sowie alle darunter liegenden Knoten aus dem Baum
  *
  * @param $nodeID [Int] = ID des zu löschenden Knotens
  * @return true=wenn Löschvorgang erfolgreich
  * @return false=wenn Löschvorang fehlgeschlagen
  */
 function deleteNode($nodeID)
 {
     // LEFT Value des zu löschenden Parent Nodes
     $parentNodeLft = 0;
 
     // RIGHT Value des zu löschenden Parent Nodes
     $parentNodeRgt = 0;
 
     // Anzahl der Kinder von $partenNodeID
     $childCount = 0;
 
     // Jener Wert, der von den folgenden Knoten subtrahiert werden muss Tabellen für Transaktion sperren und Transaktion starten
     $removeItemCount = 0;
 
     $sql = 'LOCK TABLES tbl_tree write ';
     $this->_db->query($sql);
     $sql = 'SET AUTOCOMMIT=0';
     $this->_db->query($sql);
     $sql = 'START TRANSACTION';
     $this->_db->query($sql);
 
     // Left-Order und Right-Order des zu löschenden Knotens ermitteln
     $sql = 'SELECT lft, rgt FROM `tbl_tree` WHERE `key`=\'' . $nodeID . '\'';
     $result = $this->_db->query($sql);
     $row = $result->fetchRow(DB_FETCHMODE_ASSOC);
     $parentNodeLft = $row['lft'];
     $parentNodeRgt = $row['rgt'];
 
     // Anzahl der Kinder von $nodeID ermitteln
     $sql = ' SELECT ' . ' COUNT(tbl_tree.`key`) AS `childcount` ' . ' FROM `tbl_tree` AS `tbl_tree` ' . ' WHERE tbl_tree.`lft`>\'' . $parentNodeLft . '\' ' . ' AND tbl_tree.`rgt`<\'' . $parentNodeRgt . '\' ' . ' LIMIT 0,1 ';
     $result = $this->_db->query($sql);
     $row = $result->fetchRow(DB_FETCHMODE_ASSOC);
     $childCount = $row['childcount'];
     $removeItemCount = ($childCount + 1) * 2;
 
     // Löschen des Knotens $nodeID sowie all seiner Kinder
     $sql = ' DELETE ' . ' FROM `tbl_tree` ' . ' WHERE `lft`>=\'' . $parentNodeLft . '\' ' . ' AND `rgt`<=\'' . $parentNodeRgt . '\' ';
     $result = $this->_db->query($sql);
 
     // "Nachziehen" aller nachfolgenden Elemente (Left-Order Wert)
     $sql = ' UPDATE ' . ' `tbl_tree` ' . ' SET ' . ' `rgt`=`rgt`-\'' . $removeItemCount . '\' ' . ' WHERE ' . ' `rgt`>\'' . $parentNodeRgt . '\' ';
     $result = $this->_db->query($sql);
 
     // "Nachziehen" aller nachfolgenden Elemente (Right-Order Wert)
     $sql = ' UPDATE ' . ' `tbl_tree` ' . ' SET ' . ' `lft`=`lft`-\'' . $removeItemCount . '\' ' . ' WHERE ' . ' `lft`>\'' . $parentNodeLft . '\' ';
     $result = $this->_db->query($sql);
     $sql = 'COMMIT';
     $this->_db->query($sql);
     $sql = 'SET AUTOCOMMIT=1';
     $this->_db->query($sql);
     $sql = 'ULOCK TABLES';
     $this->_db->query($sql);
 }

Sie erkennen anhand dieser Funktion sehr schön, wie wichtig ein korrektes Transaction Locking bei Nested Sets ist. Angenommen sie atomarisieren diesen Prozess nicht, und ein Stromausfall schickt Ihren Server genau nach dem Löschen des Knotens und vor dem Nachziehen der nachfolgenden Elemente ins elektronische Wachkoma, hätten Sie recht schnell sehr große Löcher in Ihrem Baum, die Sie anschließend von Hand wieder schließen müssten (was bei einem großen Baum in langer Zeichen- und Rechenarbeit endet).

Einfügen eines neuen Knotens

Kommen wir nun zum Einfügen eines neuen Knotens. Auch diese Operation kann man sich recht einfach in zwei Schritten vorstellen:

  • Äste / Knoten an jener Stelle „auseinanderschieben“, an der der neue Knoten eingefügt werden soll
  • Einfügen des neuen Knotens in die Struktur

Zuerst müssen wir unserer Methode zum Einfügen des neuen Knotens mitteilen, an welcher Stelle der Knoten eingefügt werden soll. Es gibt drei mögliche Positionen, an der man einen Knoten einfügen kann. Mit diesen Optionen erreichen wir jede beliebige Stelle im Baum.:

  • Links vom aktuellen Knoten
  • Rechts vom aktuellen Knoten
  • Unterhalb des aktuellen Knotens (neues Kind)

Um diese Funktionen in unser Beispiel einbinden zu können, fügen wir in die Methode zum Auslesen (getNestedSetsTree()) drei weitere Links ein. Diese benenne ich „Neuer Knoten davor“, „Neuer Knoten danach“ und „Neuer Knoten unterhalb“, da diese Deklaration bei der „klassischen“ Ansicht (von oben nach unten) sinnvoller ist (als „links“, „rechts“ und „unterhalb“).

Kommentar verfassen

Folge mir auf Twitter

Hol Dir kostenlos Tipps und Tricks zu Shopware, E-Commerce und andere Open-Source Produkte.

Folge @synonymousrocks