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.



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.



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.