Verschieben von Nodes in Nested Sets

Hallo,

ich habe eine Baumstruktur per Nested Sets Model in einer MySQL-DB
abgelegt. Nun bin ich auf der Suche nach einem Algoritmus, welcher Nodes
(und dessen Kinder) verschiebt.

Bisher habe ich nur sehr Performance lastige (PHP-)Scripts gefunden, die
diese Aufgabe erfüllen. Besser wären natürlich ein paar Queries, wie sie
es auch für das Hinzufügen, Anzeigen und Löschen von Nodes gibt.

Hat so etwas schon mal jemand programmiert oder hat einen Link für mich,
wo ich geeignete Queries finden kann?

Gruß Fabian

Re: Verschieben von Nodes in Nested Sets

Fabian Wolter wrote:
>
> ich habe eine Baumstruktur per Nested Sets Model in einer MySQL-DB
> abgelegt. Nun bin ich auf der Suche nach einem Algoritmus, welcher Nodes
> (und dessen Kinder) verschiebt.

Ah, Bäume. Mein Lieblingsthema :)
Prinzipiell ist das mit ein paar wenigen Abfragen erledigt. Die Frage,
die du dir stellen mußt, ist: "Wie soll das ganze ablaufen?". Die
Antwort auf diese Frage liefert dir auf fast direktem Weg die Antwort.

Hier die wichtigsten Schritte:
- Node mit Kindern durch Reorganisation des Baumes aus der logischen
Struktur entfernen (NICHT LÖSCHEN!).
- Baum so reorganisieren, daß an der neuen Stelle eine Lücke entsteht.
- Node mit Kindern durch Reorganisation dieses Teilbaums an der neuen
Stelle wieder in die logische Struktur aufnehmen.

Ein kleines Beispiel:
Gegeben sei ein Baum mit einem Wurzelelement, zwei Kindern und 2 Enkeln,
die zu Kind1 gehören. In Klammern der jeweilige Rechts- und Linkswert.

Wurzel (1|10)
/ \
Kind1 (2|7) Kind2 (8|9)
/ \
Enkel1 (3|4) Enkel2 (5|6)

Nun möchtest du, daß Kind1 mit den beiden Enkeln rechts steht. Also
entfernen wir Kind1 zunächst aus der Struktur durch Reorganisation des
restlichen Baumes. Dazu mußt du zunächst bei allem, was rechts von Kind1
steht, den Links- und Rechtswert um rechts - links + 1 des Kindes
erniedrigen (also bei allen Elementen, deren Rechts- und Linkswert
größer ist, als der Rechtswert von Kind1). In unserem Fall also um 6.

Anschließend mußt du noch den Rechtswert von allen übergeordneten um den
gleichen Betrag erniedrigen (also von allen Elementen, deren Rechtswert
größer ist, als der Rechtswert von Kind1 und der Linkswert kleiner ist,
als der Linkswert von Kind1). Der Baum sieht nun so aus:

Wurzel (1|4)
|
Kind2 (2|3)

Kind1 (2|7)
/ \
Enkel1 (3|4) Enkel2 (5|6)

Schon gar nicht mal so schlecht. Der Baum ist korrekt organisiert und
dir ist der zu Verschiebende Teilbaum verblieben.

Wichtig ist in diesem Zusammenhang, daß du unbedingt bei allen
Operationen deinen Teilbaum von Kind1 abwärts unverändert läßt. Wie du
das anstellst, überlasse ich mal deiner Phantasie. Aber negierte Rechts-
und Linkswerte wären IMHO ein brauchbares Mittel.

Der nächste Schritt ist das Reintegrieren des Teilbaums in das Große
Ganze. Dazu muß alles, was rechts von der Einzufügenden Stelle steht,
weiter nach rechts geschoben werden, indem sowohl der Rechts-, als auch
der Linkswert um die berühmten 6 erhöht werden.

In diesem einfachen Beispiel gibt es das nicht, deshalb machen wir
gleich mit dem nächsten Schritt weiter und erhöhen allen Elementen, die
über der einzufügenden Stelle liegen, den Rechtswert nach bekanntem
Schema. Unser Baum sieht nun wie folgt aus:

Wurzel (1|10)
|
Kind2 (2|3)

Kind1 (2|7)
/ \
Enkel1 (3|4) Enkel2 (5|6)

Es hat sich nicht viel getan, außer daß die Wurzel genügend Platz hat,
um drei weitere Elemente aufzunehmen. Diese Chance sollten wir nutzen,
um deinen Teilbaum wieder in die Struktur aufzunehmen.

Dazu erniedrigst du die Links- und Rechtswerte deines Kind1-Teilbaums um
den Linkswert von Kind1 und erhöhst sie um den Rechtswert + 1 der
einzufügenden Stelle. Wir erhalten einen wunderbaren Baum, der wie folgt
aussieht:

Wurzel (1|10)
/ \
Kind2 (2|3) Kind1 (4|9)
/ \
Enkel1 (5|6) Enkel2 (7|8)

Ich glaube, damit könnte man zufrieden sein, oder? Die Verschiebung nach
links, das Behandeln der problematischen Fälle (z.B. Unberührtheit des
Teilbaums), sowie das Umschiffen der zweiten Reorganisation des
Gesamtbaumes (das kostet wohl die meiste Zeit) durch geschickte
Bedingungen bei der ersten Reorganisation überlasse ich dir mal als Übung.

Ach ja, LOCK TABLES ist in diesem Fall ein unverzichtbarer Freund.

Grüße,
Dominik
--
Norbert Melzer in d.c.d.mysql:
F: Wie verstehe ich diese FAQ am besten?
A: Studieren Sie Datanbank-Design und lesen Sie anschliessend alles nochmal

Re: Verschieben von Nodes in Nested Sets

Hallo Dominik,

Dominik Echterbruch schrieb:
> Ah, Bäume. Mein Lieblingsthema :)
> Prinzipiell ist das mit ein paar wenigen Abfragen erledigt. Die Frage,
> die du dir stellen mußt, ist: "Wie soll das ganze ablaufen?". Die
> Antwort auf diese Frage liefert dir auf fast direktem Weg die Antwort.

Vielen Dank für deine wirklich sehr ausführliche Antwort. Ich habe mir
anhand deinen Ausführungen ein paar Queries zusammengestrickt mit denen
das Verschieben einwandfrei funktioniert.

Sobald ich meine Hompage fertig habe, werde ich die Abfragen dort
veröffentlichen.

Gruß Fabian