Nested-Sets sind für normale Baumstrukturen super, aber wenn man etwas flexibler sein möchte und z.B. ein Item in mehreren Kategorien haben möchte oder eine Kategorie auch als Kind-Element von z.B. einer Angebots-Kampanie, ist man schon nicht mehr bei einem Baum sondern bei einem Netz. Nun hier Eltern-Elemente zu finden und zu wissen in welchen Kategorien ein Item sich befindet ist etwas aufwendiger.
CREATE TABLE exp_structure(
ID int(11) UNSIGNED NOT NULL AUTO_INCREMENT,
NAME VARCHAR(255) NOT NULL,
TYPE VARCHAR(255) NOT NULL,
PRIMARY KEY(ID)
);
CREATE TABLE exp_links(
ID_PARENT int(11) UNSIGNED NOT NULL,
ID_CHILD int(11) UNSIGNED NOT NULL,
IS_SHADOW_LINK int(1) DEFAULT 0,
REFCOUNT int(1) DEFAULT 0,
PRIMARY KEY(ID_PARENT, ID_CHILD)
);
Damit man nun schnell herausfinden kann wird, beim Anlegen eines Items in der Struktur wird nicht nur ein Link auf das direkte Parent-Element gesetzt sondern werden auch rekursiv alle weiteren Parent-Element aufgerufen und ein Shadow-Link darauf gesetzt. Dieser Shadow-Link besagt, dass das Item nicht direkt am Parent-Element hängt sondern Subelement zugeordnet ist. In der Oberfläche sind mit Shadow-Links verlinkte Items also nicht anzuzeigen.
Ist ja erst einmal ganz einfach. Wenn ich nun aber z.B. ein Item mit 2 Parent-Elementen habe, muss man wenn man weiter nach oben in die Hierarchie kommt darauf achten, dass man nicht mehrere Shadow-Links setzt. Das ist an sich auch kein großes Problem. Schwierig wird wenn man ein Item entfernt und die Shadow-Links entfernen muss. Bei jedem Shadow-Link müsste man prüfen, ob er durch einen weiteren Pfad noch verwendet wird oder nicht. Dafür gibt die REFCOUNT... ja genau.. wie im Garbage Collector. Wenn man ein Shadow-Link setzten soll, dieser aber schon existiert zählt man Counter hoch. Beim Entfernen zählt man einfach alle Shadow-Links des Pfades runter und entfernt dann alle die auf 0 stehen, weil man dann sicher ist, dass dieser Shadow-Link nicht noch von einem anderen Pfad verwendet wird.
Tree-Strukturen in einer Relationalen-DB:
Alternative zu einfachen Child-Parent Strukturen oder Nested-Sets. Der Vorteil würde darin liegen, dass die Inserts im Vergleich zu Nested-Sets bedeutent schneller sind und dass dabei aber nur wenige Vorteile dabei verloren gehen. Trotzdem sind Änderungen noch immer langsamer und das Problem bei Fehlern die Struktur wieder herzustellen bleibt auch in einem gewissen Rahmen. Im Vergleich zu Nested-Sets kann die Struktur aber nicht bei einfachen Inserts zerstört werden, sondern nur wenn Änderungen innerhalb der vorhandenen Struktur vorgenommen werden und dabei eine Transaktion abbricht. Aber auch hier ist das Rekonsturieren sehr viel einfacher, weil die verbliebenen Einträge vor dem Abbruch meistens ausreichen sollten um die Transaction an der abgebrochenen Stelle wieder aufnehmen
zu können.
Das Prinzip basiert auf einer seperaten Tabelle, die alle Relationen der Nodes untereinander (wenn sie Parent oder
Child sind) beinhaltet.
nodeId | parentId | distance
_______|__________|_________
12 | 1 | 3
12 | 3 | 2
12 | 7 | 1
Der Node mit der Id 12 ist also ein direktes Child von dem Node mit der Id 7. Node 7 ist ein Child von Node 3 und Node 3 ist ein Child von Node 1. Node 1 ist das Root-Element.
Direkte Children von Node 3 erhölt man also wenn parentId=3 ist und distance=1. Den direkten Patren von Node 3 mit nodeId=3 und distance=1. Alle Parent mit nodeId=3 und die Sortierung wird über distance vorgenommen.
Inserts sind auch leichter als man erstmal denkt. Wir fügen an Node 12 eine Zusätzliche Node mit der Id 13 an.
Dafür kopieren wir und den Teil der Table für Node 12 und ersetzen die Id von 12 und erhöhen die distance jeweils um 1. Am Ende fügen wir den fehlenden letzten Eintrag einfach hinzu, da dieser keinerlei Berechnung benötigt.
nodeId | parentId | distance
_______|__________|_________
12->13 | 1 | 3+1
12->13 | 3 | 2+1
12->13 | 7 | 1+1
13 | 12 | 1
damit haben wir alle Einträge für 13 ohne Rekursion oder dem Ändern anderer Einträge vorgenommen.
Auch das Umhängen eines Nodes innerhalb des Trees ist ähnlich benötigt aber etwas Vorarbeit. Wir hängen z.B. Node 7 an Node 4
Es müssen alle Nodes bei denen Node 7 in den parentId's steht aus gelesen werden und aufsteigend nach distance sortiert werden. Nun werden alle Einträge von Node 7 gelöscht und wie beim Insert neu eingetragen. Danach folgen die direkten Children nach dem selben Muster. Deren Eintrag mit der distance 1 verrät immer noch den Parent und solange der bekannt und vorhanden ist, lassen sich die Tabelleneniträge wie beim Insert schnell wieder aufbauen.
Beim löschen eines Node werden auch alle Children entfernt. Da bedeutet alle Nodes bei denen die parentId gleich der Id des zu entfernden Nodes ist. Dabei spielt die distance keine Role, da solche Einträge nur existieren, wenn der Node ein direktes oder indirektes Child ist.
Dieses Verfahren benötigt natürlich mehr Joins auf DB-Ebene. Aber da sind heutige DBs wohl ausreichend schnell für.
Das einzige wirkliche Problem wäre, dass diese Tabelle sehr schnell sehr sehr groß werden würde. Abhängih von der Tiefe des Baumes kann es ohne Probleme dazu kommen, dass die Tabelle 10x so viele Einträge hat wie die eigentliche
Node-Tabelle.