[Zum einlesen die erste Folge]

Zur Einführung ein Bild, das in dieser Folge als grafisches Hilfsmittel dienen soll.

Erstellt wurde es mit dem Content Management System ConstructrCMS in der Version 3.01.4 Beta (kostenlos erhältlich unter http://constructr.phaziz.com - GPLv3).

Wir werden uns heute mit dem Löschen von Seiten beschäftigen. Was muss getan werden um Seiten zu löschen, ohne das der gesamte Baum verschruddelt wird?

Es muss festgestellt werden, an welcher Stelle im Baum die Seite gelöscht werden soll. Aus folgendem Grund: weil ab da der Baum nach dem eigentlichen Löschvorgang reorganisiert werden muss (die Zähler LFT -> Left und RGT -> Right).

Würde der Baum ab der gelöschten Seite nach dem Löschvorgang nicht reorganisiert werden, enstünde eine Lücke. Diese Lücke würde das weitere Pflegen des Bäumchens behindern - so ein Baum soll ja mal groß und stark werden.

Es muss also schon vor dem Löschen bekannt sein, welchen linken und rechten Zähler die zu löschende Seite inne hat. Außerdem benötigen wir die Information, ob nur die eigentliche Seite gelöscht werden soll, oder ob ein eventuell vorhandener Teilbaum gelöscht werden soll (Unterseiten zur Seite die gelöscht werden soll).

Nehmen wir zum Beispiel die Seite 1.2 aus dem oben gezeigten Bild. Was soll nach dem Löschen mit der Unterseite 1.2.1 geschehen? Soll die Unterseite mit gelöscht werden, oder soll die Seite an die Stelle der gelöschten Seite treten - soll die Seite in der Ebene nach oben wandern?

Wir wollen die Seite 1.2 mit allen evtl. vorhandenen Unterseiten löschen (also den gesamten Teilbaum, der die Seite 1.2 zur Wurzel hat):

Wir benötigen folgende Informationen vor dem Löschvorgang:

- ID der Seite die gelöscht werden soll
- LFT-Wert der Seite die gelöscht werden soll
- RGT-Wert der Seite die gelöscht werden soll

Die erste Maßnahme ist das löschen der Seite, mit den vorhandenen Unterseiten:

DELETE FROM TABELLE
WHERE LFT BETWEEN 16 AND 19

Warum jetzt nicht das löschen per ID (DELETE FROM TABELLE WHERE ID = ‘10′)? Weil wir mit dieser DELETE-Anweisung schon die Seite erfassen, die gelöscht werden soll - inklusive aller Unterseiten evtl. vorhandnen Unterseiten. Alle Unterseiten zu einer Seite, besizten LFT- und RGT-Werte innerhalb der LFT- und RGT-Werte dieser Seite -> das ist eine feste Regel im Konzept der Nested Set´s.

Wir haben es also geschafft den Teilbaum ab Seite 1.2 inklusive der Seite 1.2.1 zu löschen. Die Seite 1.2.1 besitzt die LFT- und RGT-Werte 17 und 18. Diese liegen innerhalb (BETWEEN) der LFT- (16) und RGT-Werte (19) der Seite 1.2.

Doch jetzt haben wir mit der Axt eine Lücke geschlagen und müssen schleunigst zusehen, das wir die entstandene Lücke versorgen. Wir reorganisieren die LFT-Werte der Seiten, die der Seite 1.2 folgten (1.3, 1.3.1 und 1.3.2):

UPDATE TABELLE
SET
LFT = LFT - ((19-16)+1)
WHERE LFT > 19

Wir reorganisieren den Baum ab der nun gelöschten Seite 1.2 wie folgt: Die LFT-Werte die größer sind als der RGT-Wert der Seite 1.2 (weil das der äußerste Zähler im gelöschten Teilbaum ist), verringern sich um den Wert 4 (mit dem Wert 4 haben wir hier zwei Seiten abgedeckt -> 1.2 und 1.2.1).
Generell ließe sich das mit dem Ausdruck ...SET LFT = LFT - ((DELETE_RGT - DELETE_LFT)+1) beschreiben, wobei DELETE_RGT und DELETE_LFT die Werte der zu löschenden Seite darstellen. Wir erinnern uns: RGT - LFT ergibt die Anzahl der Unterseiten (feste Regel). Daher auch die Addition mit 1 für die eigentliche Seite die gelöscht werden soll (1.2).

Fehlt uns noch die reorganisation der RGT-Werte:

UPDATE TABELLE
SET
RGT = RGT - (19-16+1)
WHERE RGT > 19

Diese bewirkt das auch die RGT-Werte der folgenden Seiten im Gesamtbaum (1.3, 1.3.1 und 1.3.2) verringert werden [...SET RGT = RGT - ((DELETE_RGT - DELETE_LFT)+1)].

Das Ziel ist erreicht:

• Wir haben eine beliebige Seite gelöscht.
• Wir haben die eventuell vorhandenen Unterseiten gelöscht.
• Und wir haben verhindert das die Ordnung unseres gesamten Baumes durcheinander kommt, indem wir die LFT- und RGT-Werte unserer Folgeseiten reorganisiert haben.

Rekursives Löschen in einem NestedSet´s-Baum mit allgemeingültigen Regeln.

Tags: nested sets, programmierung, strukturen
Posted in programming

Wer kennt Sie nicht, der sich schon mit hirachischen Strukturen beschäftigen musste: Arne Klempert, dieses oder jenes Tutorial, virtuelle MySQL-Kurse, …

Alles auch sehr hilfreich, aber…

… aber irgendwie hören alle in der Mitte auf. Wie geht das denn nun mit dem verschieben von Teilbäumen rauf und runter in der Struktur im Konzept der NestedSet´s, hä?

Verwiesen wird auf die Pear-Klassen, sonstige Klassen und Frameworks - auf die Details und Feinheiten geht niemand ein. Das versuche ich jetzt nachzuholen. ConstructrCMS liegt vor in Version 1.01.3 Beta und komplette Teilbäume (Seiten mit Unterseiten) können in der Struktur beliebig nach dem NestedSet´s-Konzept verschoben werden. Das war noch das Sahnehäubchen was dort fehlte.

Visit ConstructrCMS

Um das gesamte Konzept zu erläutern fehlt mir heute Abend die Zeit, aber ich fange an und mache auch weiter ;-). Das wird jetzt durchgezogen - bis zum bitteren Ende!

Einführung: Was sind Nested Sets?

Ein Bild sagt mehr als tausend Worte, da ich hier mehrere Bilder zeige ist das schon ein recht langer Artikel ;-). Erläuterung zu den folgenden Bildern: Alle Bilder zeigen die identische hirachische Struktur einer Anordnung von Seiten in einer geordneten Struktur (Seitenbaum):

Im einfachsten Fall genügt also eine Datenbanktabelle mit drei Feldern: PK, LFT und RGT - für eine Feinheit nehmen wir noch ein weiteres Feld hinzu, auf das ich später eingehen werde - eine Art temporären Marker.

PK: Der PrimaryKey der Datenbanktabelle

LFT: Der linke Zähler

RGT: Der rechte Zähler

TMP_MARKER (int, oder char, oder sonst was… ist egal)

Mehr benötigt man nicht um eine solche NestedSet´s-Struktur in einer Datenbanktabelle darzustellen. Für ein - sagen wir mal - Content Management System kämen noch ein paar Felder dazu (Seitenname, Sichtbarkeit, …), aber zum darstellen reicht die Struktur vollkommen aus.

1) Anlegen von Seiten

Befindet sich noch keine Seite in der Tabelle, erstellen wir durch das Anlegen einer neuen Seite den Mutter-Knoten (Root). Dieser Grundstein hat als linken Wert (LFT) immer die 1 - feste Regel. Der Rechte Wert (RGT) ergibt sich aus der Anzahl der vorhandenen Unter- oder Folge-Seiten.

Jetzt legen wir in MySQL die Mutter (Root) an:

INSERT INTO TABELLE (PK,LFT,RGT,TMP_MARKER) VALUES (1,1,2,”);

Sind schon Seiten vorhanden, wird beim Anlegen einer neuen Seite automatisch eine Unterseite erstellt (es kann immer nur einen Wurzel -> Root geben - ist wie bei Highlander).

Benötigt wird für das Anlegen einer neuen Unterseite der RGT- und LFT-Wert der zuletzt eingefügten Seite - des Vorgängers im Seiten-Baum. In unserem Fall also die Werte der Root-Seite -> LFT = 1 und RGT = 2, mehr Seiten gibt es noch nicht.

Der LFT-Wert der neuen Unterseite ergibt sich aus dem LFT-Wert des Vorgängers addiert mit 1 (1+1=2). Der LFT-Wert der ersten Unterseite ist also 2. An der Stelle hätten wir aber ein Problem mit der Mutter-Seite: diese hat bis jetzt der Wert 2 als RGT-Wert inne -> muss also geändert werden.

Vor dem Einfügen der ersten Unterseite, wird also bei Mutti ein wenig Platz geschaffen (der Platz für exakt eine einzige Unterseite - mehr wird aktuell nicht benötigt):

UPDATE TABELLE  SET RGT = RGT+2  WHERE RGT >= NEW_LFT;

Wie vergrößern dadurch den RGT-Wert der Mutti. Dadurch ergeben sich die neuen Werte der Mutter-Seite wie folgt:

Aus LFT 1 wird LFT 1 -> weil die Mutti immer die 1 als linken Zähler hat!!!

Aus RGT 2 wird RGT 4 -> damit in die Lücke von 2 bis 4 die neue Seite mit den Werten LFT:2 und RGT:3 passt. Wir fügen die neue Unterseite gefahrenlos ein:

INSERT INTO TABELLE (PK,LFT,RGT,TMP_MARKER) VALUES (2,2,3,”);

War doch net so wild. Wir haben erfolgreich eine Mutter-Seite angelegt und eine Unter-Seite. Das Spiel könnte man nun weiterspielen, bis wir den Seiten-Baum aus den oben gezeigten Bildern nachgebildet haben:

…Jetzt ist Feierabend mit Folge 1, die nächste folgt bald!

Tags: nested sets, programmierung, strukturen
Posted in programming