Diskussion:Datenstruktur: Nested Sets

Der Baum wird gepflanzt und wächst

Bevor wir unseren ersten Knoten (die Baumwurzel) erzeugen können, müssen wir zunächst die Datenbank-Tabelle anlegen. Streng genommen benötigt eine Baumstruktur nach dem Nested Sets-Modell lediglich zwei Felder (lft und rgt). Wir gönnen den Knoten unseres Baumes aber auch noch eine eindeutige id und ein kurzes Textfeld (name).

CREATE TABLE tree (

   id    INT(12)      UNSIGNED NOT NULL AUTO_INCREMENT,
   name  VARCHAR(50)  NOT NULL,
   lft   INT(12)      UNSIGNED NOT NULL,
   rgt   INT(12)      UNSIGNED NOT NULL,
   PRIMARY KEY (id),
   key lft (lft),
   key rgt (rgt),

);

Beim Aufbau des bereits aus den obigen Ausführungen vertrauten Baumes muss zunächst der Wurzelknoten eingefügt werden. Wir erinnern uns, dass für die Wurzel per Definition LFT=1 gilt. Da der Knoten (noch) keine Nachfahren hat, ergibt sich: RGT = 2. Folglich lautet unser Statement zum Erstellen der Wurzel:

INSERT INTO tree (name,lft,rgt) VALUES ('Säugetiere',1,2);

Genießen Sie den Anblick dieses einfachen Statements, denn die folgenden Operationen werden teilweise erheblich komplexer. Halten Sie aber dennoch durch; denn Ihre Mühen werden mit ein paar wirklich faszinierenden Select-Abfragen belohnt. Im nächsten Schritt fügen wir das erste Kind des Wurzelknotens ein. Hierzu müssen wir zunächst ein wenig Platz zwischen dem LFT- und dem RGT-Wert der Wurzel schaffen. Genaugenommen müssen alle Vorfahren unseres neuen Knotens (in diesem Fall nur die Wurzel) einen um zwei erhöhten RGT-Wert erhalten. Ist der Platz geschaffen können wir anschließend gefahrlos den neuen Knoten einfügen:

UPDATE tree SET rgt=rgt+2 WHERE rgt = 2; INSERT INTO tree (name,lft,rgt) VALUES ('Primaten',2,3);

Fügen wir als nächstes den Bruder "Nagetiere" ein. Hierfür benötigen wir zunächst wieder den LFT- und den RGT-Wert des Vorfahren (erneut der Wurzelknoten), für die im folgenden die Variablen $LFT und $RGT verwendet werden. Für den Wurzelknoten gilt zur Zeit $LFT = 1 und $RGT = 4.

UPDATE tree SET rgt=rgt+2 WHERE rgt >= $RGT; INSERT INTO tree (name,lft,rgt) VALUES ('Nagetiere', $RGT, $RGT+1);

Wie bereits beim Einfügen des ersten Kindes erhöhen wir wieder den rechten Wert des Vorfahrens um zwei. Der neue Knoten erhält als linken Wert den ehemaligen rechten seines Vorfahrens und der rechte Wert ist um eins höher als der linke.

Weitere Infos gibts unter http://www.klempert.de/nested_sets/