¶ Database Nested Sets
Das Nested Sets Modell ist ein Modell mit dem man Bäume in relationalen Datenbank ablegen kann.
¶ referenzielle Integrität
- beim Löschen des Elternknoten kann die DB die Kinderknoten nicht mitweglöschen, da solche Referenzen "kompliziert" dargestellt sind
- ergo kann man das nicht der DB überlassen, sondern muss das per Hand machen
- beim löschen kein Problem, man sucht einfach alle die zwischen left und right des zu löschenden Objektes liegen
¶ Root Knoten einfacher erkennbar
- der Root Knoten hat halt links=1
- im Parent Modell muss man gucken, welches Objekt als Parent sich selbst hat, das ist nicht nur eine etwas kompliziertere Abfrage, sondern führt auch dazu, das man erst den Root Knoten einfügen muss, und dann erst die Referenzen aktivieren kann
¶ neue Knoten hinzufügen
- das ist natürlich schwieriger, da man erstmal Platz schaffen muss
- es muss erst das Parentobjekt geupdated werden
- wobei da ein neues Problem auftaucht: will man einen Kindknoten einfügen, müssen im worstcase alle Knoten die den selben Level wie den des Elternknoten haben, geändert werden (ich lese gerade, das das sogar auf der Seite steht)
- vermutlich wird sich das beim Scripten so ergeben, das man immer erst noch ein SELECT auf den Parent macht, um rechts zu bekommen
¶ Rekursive Strukturen auslesen
- das geht natürlich sehr viel einfacher, da man seinen Vorgänger und Nachfolger einfach ermitteln kann (entweder links - 1 oder rechts + 1)
- das ganze erinnert an doppelt verkettete Listen, nur eben für Bäume angepasst
¶ Non Rekursive Strukturen auslesen
- geht eigentlich gar nicht
- egal was man für ein SELECT schreibt, es ist immer rekursiv
- da muss man denn ein Levelfeld hinzufügen und entsprechend mit WHERE beackern
¶ kleine Entwicklerhinweise
- left und right sind in MySQL Keywords
- beim Verändern des Baumes Transaktionen verwenden
¶ ein paar SQL Queries
¶ objekt einfügen
UPDATE object SET r = r + 2 WHERE r >= 2;
UPDATE object SET l = l + 2 WHERE l > 2;
INSERT INTO object (l, r, title, longtitle, typ) VALUES (2, 2 + 1, '2nd folder', 'blah blah blah', 2);
¶ Weg nach unten
der weg nach unten mit relativen level (kann bentutz werden, um alle Kindknoten der nächsten Eeben zu SELECTen)
SELECT o.*, COUNT(p.id) - 1 AS level FROM object AS n, object AS p, object AS o WHERE o.l BETWEEN p.l AND p.r AND o.l BETWEEN n.l AND n.r AND n.id = 2 AND p.l >= n.l GROUP BY o.l ORDER BY o.l;
¶ Alle Kinderknoten
FIXME
alle Kindknoten der nächsten Ebene (s.o.)
SELECT o.*, COUNT(p.id) - 1 AS level FROM object AS n, object AS p, object AS o WHERE o.l BETWEEN p.l AND p.r AND o.l BETWEEN n.l AND n.r AND n.id = 2 AND p.l >= n.l GROUP BY o.l HAVING COUNT(p.id) - 1 = 1 ORDER BY o.l;
¶ der weg nach oben
SELECT p.* FROM object n, object p WHERE n.l BETWEEN p.l AND p.r AND n.id = 3 ORDER BY n.l;
¶ der weg nach unten mit level
SELECT o.title, COUNT(p.id) - 1 AS level FROM object AS n, object AS p, object AS o WHERE o.l BETWEEN p.l AND p.r AND o.l BETWEEN n.l AND n.r AND n.id = 2 GROUP BY o.l ORDER BY o.l;
¶ der weg nach unten ohne level
SELECT o.* FROM object AS o, object AS p WHERE o.l BETWEEN p.l AND p.r AND p.id = 2;
¶ kompletter baum mit level
SELECT n.title, COUNT(*) - 1 AS LEVEL FROM object AS n, object AS p WHERE n.l BETWEEN p.l AND p.r GROUP BY n.l ORDER BY n.l;