Baumstrukturen und SQL
Wer den Workshop bis jetzt genau verfolgt hat, der wird bei vergleichen mit den Seiten der Quellangaben (Bilder) festgestellt haben: hey, der schreibt ja fast das Gleiche wie dort.
Ok, dann paßt in diesem Abschnitt ebenso gut auf und ihr werdet feststellen, daß ich einige der SQL-Statements geändert habe.
Zunächst brauchen wir eine einfache Tabelle in unserer Datenbank und die legen wir ganz einfach wie folgt an:
Code:
CREATE TABLE node (
node_id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
root_id INT(10) UNSIGNED NOT NULL,
payload VARCHAR(64) NULL,
lft INT(10) UNSIGNED NOT NULL,
rgt INT(10) UNSIGNED NOT NULL,
PRIMARY KEY (node_id),
KEY root_id (root_id)
);
Damit dürfte niemand Probleme haben. Wer doch … der sollte zunächst einen anderen Workshop durcharbeiten.
Fangen wir mit der Erstellung einer Wurzel an. Im Teil I des Workshops haben wir gelernt: jeder Knoten hat links eine "1". Und jeder Wurzelknoten ohne Blätter hat auf der rechten Seite eine "2". Das haben viele gelesen, gelacht und gesagt: na der erklärt Sachen, die so offensichtlich logisch sind, daß man nicht drüber reden muß. Na gut, dann setzen wir das Ganze mal um!
Code:
INSERT INTO node (payload,lft,rgt)
VALUES ('Name der Wurzel',1,2);
SELECT @max_id := MAX(root_id)
FROM node;
UPDATE node
SET root_id = @max_id + 1
WHERE node_id = LAST_INSERT_ID();
Dieses Statement erzeugt eine Wurzel. Im Gegensatz zu anderen Statements erzeugt mein Script so viele Wurzeln, wie man möchte und muß lediglich später im Zusammenspiel mit der übergeordneten Programmiersprache mit einem entsprechenden Namen für die einzelnen Wurzeln versehen werden.
Es sei hier nochmals drauf hingewiesen, daß ich in diesem Teil ausschließlich auf MySQL eingehen werde. Wer auf fertige Codes und PHP wartet, der … muß sich noch ein wenig gedulden!
So, dann schauen wir doch mal, ob der Knoten auch da ist. Dafür lesen wir jetzt einfach alle Wurzeln aus (da das Auslesen aller Daten ja wohl kein Problem sein dürfte). Z.B. so:
Code:
SELECT payload
FROM node
GROUP BY root_id;
War eigentlich auch ein Kinderspiel. Jetzt müßtet Ihr folgendes sehen:
+---------+
| payload |
+---------+
| Wurzel 1 |
+---------+
Nach dem Einfügen weiterer Wurzeln werden auch diese in unserer Liste auftauchen. Doch warum nicht gleich alles ausgeben? Wir erinnern uns: es soll eine Baumstruktur werden.
Wir müssen also aus den Zahlen, die in der Datenbank stehen, lesen, welches Objekt in welcher Ebene eingeordnet wird. Doch wie soll das gehen? Ganz einfach so:
Code:
SELECT node1.payload, node1.node_id,
COUNT(*) AS level
FROM node AS node1,
node AS node2
WHERE node1.root_id = 1
AND node2.root_id = 1
AND node1.lft BETWEEN node2.lft AND node2.rgt
GROUP BY node1.lft
Das ist mal wieder ein Statement für Dennis. Wir machen aus einer Tabelle eine Megatabelle. Aber über das Thema kartesisches Produkt bei JOINS haben wir ja bereits diskutiert. Und hier geht es um 5 Spalten. Hey … das kann so schlimm nicht werden!
Hier erhalten wir eine Liste aller Objekte der Wurzel mit der root_id = 1. Leider werden hier nicht alle Wurzeln ausgegeben und ich muß auf dieses Thema im PHP-Teil zurückkommen. Denn bislang hab ich die Ausgabe aller Wurzeln (incl. ihrer Zweige und Blätter) nur mit einem zweiten Statement und einer while-Schleife lösen können. Sollte jemand eine reine SQL-Alternative finden, so schreibt mir.
Manipulieren von Bäumen
Ich hoffe, daß alle, die den Workshop bis hierher verfolgt haben, bereits erkennen, wohin die Sache geht. Wir haben Wurzeln und Zweige aufgebaut und ausgelesen. Aber damit können wir natürlich nicht zufrieden sein. Kommen wir darum jetzt zum Einfügen neuer Zweige und Blätter.
Die übergeordnete Programmiersprache muß später für unser folgendes Statement die nötigen Variablen bereitstellen:
- root_id der Wurzel bzw. des Zweiges, an dem das neue Element angefügt werden soll = ROOT_ID
- rechte Seite der Wurzel oder des Zweiges = RGT
- (sonst wird auch noch die linke Seite ausgelesen, doch die benötigen wir nicht)
Code:
UPDATE node
SET lft = lft + 2
WHERE root_id = ROOT_ID
AND lft > RGT;
UPDATE node
SET rgt = rgt + 2
WHERE root_id = ROOT_ID
AND rgt >= RGT;
INSERT INTO node (root_id,payload,lft,rgt)
VALUES (ROOT_ID,'neues Blatt',RGT,RGT+1);
Mit Hilfe diesen Statements könnt Ihr an jeder beliebigen Stelle einen neuen Zweig oder ein Blatt rechts vom gewählten Knoten einfügen. Alle linken und rechten Seiten (wir erinnern uns an die Abbildungen aus Teil I) werden automatisch korrigiert.
Na … is das was?! Der Hammer oder?! Macht das mal per Hand … und ohne Fehler! Oder auf einem Blatt Papier. Wie lange würdet Ihr brauchen?
Erinnern wir uns an die 4. Regel innerhalb von Bäumen aus Teil I: floor((RGT-LFT) / 2) = Anzahl der Knoten im Zweig.
Mit ihrer Hilfe können wir uns jetzt Folgendes anzeigen lassen:
Code:
SELECT node1.payload,
floor((node1.rgt – node1.lft) / 2) AS children
COUNT(*) AS level
FROM node AS node1,
node AS node2
WHERE node1.root_id = 1
AND node2.root_id = 1
AND node1.lft BETWEEN node2.lft AND node2.rgt
GROUP BY node1.lft;
Als Ergebnis erhalten wir eine Tabelle, welche alle Knoten der Wurzel mit der root_id = 1 incl. der Angabe über vorhandene Kindknoten und Ebene der Knoten.
Wer es bis hierher geschafft hat, wird auch den Rest noch "überstehen". Machen wir uns also an die noch fehlenden Funktionen: Knoten an bestimmten Positionen einfügen, löschen und ganze Teilbäume entfernen.
Da es jetzt etwas komplizierter wird, werde ich das Tempo etwas rausnehmen.
Wir wollen also in unseren vorhandenen Baum einen
neuen Knoten auf der gleichen Ebene einfügen. Dafür muß uns die übergeordnete Programmiersprache wieder die benötigten Variablen bereitstellen. Bei Seiten, bei denen mehrere User gleichzeitig das gleiche Script zur Manipulationen an Bäumen verwenden können, sollten die Tabellen für die Zeit der Änderung gesperrt werden. Bei den aktuellen SQL-Versionen kann das Sperren der Tabellen auch über die Verwendung entsprechender Tabellentypen gewährleistet werden (InnoDB).
Ich verzichte hier auf die Sperrung. Wer dazu noch Fragen hat, kann sich gerne melden.
Ich werde für mein Statement lediglich die node_id als von der übergeordneten Scriptsprache übergebenen Parameter annehmen. Wer mag, läßt die SQL-Variable raus und holt sich die Werte bereits vorher per PHP. Somit ließe sich eine Abfrage sparen.
Das folgende Statement fügt auf dem gleichen Level rechts eines vorhandenen Knotens einen neuen Knoten ein. Die Bezeichnung "Bruder" für diese Knoten gefällt mir so sehr, daß ich sie hier auch übernehmen werde.
Wir fügen also jetzt einen Bruder auf der rechten Seite ein:
Code:
SELECT @ROOT_ID := root_id, @BROTHER_RGT := rgt
FROM node
WHERE node_id = 'NODE_ID';
UPDATE node
SET lft = lft + 2
WHERE root_id = @ROOT_ID AND lft > @BROTHER_RGT;
UPDATE node
SET rgt = rgt + 2
WHERE root_id = @ROOT_ID AND rgt > @BROTHER_RGT;
INSERT INTO node (root_id, payload, lft, rgt)
VALUES (@ROOT_ID, 'my right little brother', @BROTHER_RGT+1, @BROTHER_RGT+2);
Bevor ich der zwingenden Logik folge und Euch das Einfügen eines Bruders auf der linken Seite zeige, will ich mal wieder ein wenig was für das grundlegende Verständnis tun.
An der Stelle hab ich länger gebraucht, weil es ohne Grafik (zumindest für mich) nicht ohne weiteres zu verstehen war.
Warum dieses links und rechts? Ist das nicht egal? ... Nö!
Abbildung1: Bruder rechts einfügen
Die Abbildung1 zeigt, wo der Knoten rechts eines vorhandenen eingefügt wird.
Sehen wir uns das Einfügen auf der linken Seite an:
Code:
SELECT @node_id := root_id, @lft := lft
FROM node
WHERE node_id = NODE_ID;
UPDATE node
SET lft = lft + 2
WHERE root_id = @node_id AND lft > @lft;
UPDATE node
SET rgt = rgt + 2
WHERE root_id = @root_id AND rgt > @lft";
INSERT INTO node (root_id, payload, lft, rgt)
VALUES (@root_id, 'my left little brother' @lft, @lft + 1);
Hätten wir das mit den bisherigen Statements hinbekommen?
Nach dieser rethorischen Frage nochmal was fürs Auge:
Abbildung2: Bruder links einfügen
Eine Struktur wie in Abbildung2 zu manipulieren, schaffen wir nur noch mit einem guten Script und sauberen Statements.
Was, wenn wir jetzt ein einzelnes Blatt löschen wollen? Alle Zahlen müssen für den Preorder-Walk neu geordnet werden. Doch ist das Blatt wirklich ein Blatt? Wie war das noch mit den Blättern? Regel 2: rechte minus linke Seite gleich 1?! Richtig! Wir prüfen also zuvor, ob es sich wirklich um ein Blatt handelt. Doch das merken wir uns für den nächsten Teil, denn da brauchen wir etwas Hilfe von PHP.
Wir gehen also davon aus, daß wir uns über die Identität des Blattes sicher sind. Dann löschen wir es doch einfach:
Code:
SELECT @rgt := rgt, @root_id := root_id
FROM node
WHERE node_id = NODE_ID;
DELETE FROM node
WHERE node_id = NODE_ID;
UPDATE node
SET lft = lft - 2
WHERE root_id = @root_id
AND lft > @rgt;
UPDATE node
SET rgt = rgt - 2
WHERE root_id = @root_id
AND rgt > @rgt;
Nach dem Löschen des Blattes müssen wieder alle verbleibenden rechten und linken Seiten in die richtige numerische Reihenfolge gebracht werden.
Ok, das ist nicht mehr so ganz leicht. Darum mach ich nur noch ein Statement und dann ist erstmal Schluß. Puhh ... Erleichterung!
Was ist bei dem Fall, daß wir einen gesamten Teilbaum löschen wollen? Ein Board wird geschlossen, ein Teil eins Unternehmens verkauft oder ausgegliedert ... praktisch denkbare Fälle gibts es da viele.
Doch wie reagiert unser Datenbank oder anders gefragt: wie muss unser Statement aussehen, damit alle linken und rechten Seiten so nachgerueckt werden, daß der Preorder-Walk wieder funktioniert?
Für diesen Teil hab ich mal wieder ein Statement geschrieben, welches ohne zusätzliche Hilfe der Programmiersprache auskommt:
Code:
SELECT DISTINCT @NODES := floor((RGT-LFT)/2), @STEPS := 2 * (1 + @MOVE), @root_id = root_id
FROM node
WHERE rgt = RGT;
# wir erinnern uns: alle RGT und LFT Werte sind eindeutig!
DELETE FROM node
WHERE root_id = @root_id
AND lft BETWEEN LFT
AND RGT;
UPDATE node
SET lft = lft - @STEPS
WHERE root_id = @root_id
AND lft > RGT;
UPDATE node
SET rgt = rgt - @STEPS
WHERE root_id = @root_id
AND rgt > RGT;
Zuerst ermitteln wir also die Anzahl der Knoten im Zweig. Aus ihr ermitteln wir die Schritte, um die die verbleibenden Knoten korrigiert werden müssen, damit unser Preorder-Walk wieder funktioniert.
Danach löschen wir alle Knoten des Zweiges und ändern dann alle linken und rechten Seiten.
So ... ich hoffe die Fraktion der Nested-sets-Ablehner ist nach diesem Teil nicht noch größer geworden.
Für das Durcharbeiten laß ich Euch jetzt ein paar Tage länger Zeit und dann machen wir mit PHP weiter. Wir bauen eine Seite mit Nested sets auf und ich zeig Euch dann gleich dazu noch einen Treemanager, mit dem Ihr die Navigation administrieren könnt.
Viel Spaß beim Testen und Üben.
Wenn Ihr Fragen haben solltet ... ich bin hier bzw. im icq (113-763-544) zu erreichen.
Hardy
PS: Ein netter Moderator hat mich darauf hingewiesen, daß ich doch noch einen Satz zu SQL und MySQL anfügen sollte.
Die Statements beziehen sich alle auf MySQL und können in anderen Datenbanksystemen (vor allem die Variablen) ganz anders aussehen. Den Sinn hinter den Statements sollte jeder nachvollziehen können. Die Schreibweise aber gegebenenfalls anpassen.
![[Workshop] Nested Sets](http://www.traum-projekt.com/forum/iconimages/workshops-und-tutorials/workshop-nested-sets.gif){kind=small}
... Habe eine kleine Ergänzung an folgender Stelle
