raffnix

hallo,

ich beschäftige mich seit einigen tagen mit dem nested set modell.
einfügen an beliebiger stelle, löschen, einzelne nodes verschieben geht alles ... war auch kein problem.

mein problem ist das verschieben von ganzen hierachien.

vom prinzip müsste ich so vorgehen (grob):

1. selektieren aller id´s im subtree
2. prüfen ob es zu einen bruder / schwester zu einem eintrage / node gibt
3. bis zu dem "geschwisternpaar und deren evtl. hierachie" den baum aufbauen
4. jede einzelne geschwisterhierachie nachbilden
5. löschen der alten einträge (nicht das problem)

bin ich da auf dem richtigen weg oder hab ich den holzweg eingeschlagen?
hat von euch jemand schon damit erfahrung (verschieben von ganzen hierachen / subtrees)?
hat jemand evtl. eine doku speziell zu dem thema verschieben von subtrees ...

wäre nett, wenn der eine oder andere (mädels natürlich auch) zeit haben und mir antworten.

danke schon einmal für eure mühe.

ps: ja, das nested set modell mach in meiner situation sinn, da 99,9% der sql anweisungen selects sind und mit rekursiver abfrage hier hohe kosten enstehen. der "baum / hierachie" wird evtl. 1 oder 2 mal am tag erweitert.

Mister Ad

DerDesian

Also für gewöhnlich ist der Vorteil an hierarchisch aufgebauten Relationen, dass man einen ganzen Subtree 'umhängen' kann in dem man nur eine einzige ID ändert.

sieht ja für gewöhnlich so aus (weiß narürlich nicht ob deine Tabelle so aussieht):pid ~ parent_id

und dann brauchst du nur die 'pid' zu ändern und gut.

__________________
Wenn dich was ankotzt, machs besser.

raffnix

erstmal danke für deinen beitrag.

beim nested set modell sieht die aufbau wie folgt aus:

anhand des left und dem right wird definiert, an welcher stelle sich der eintag befindet.

dies hat den vorteil, dass man bei selectionen keine rekursion anwenden muss, die sehr "kostenintensiv" sind.

um einen teilbaum (oder den ganzen) zu selektieren reicht beim nested set modell:

select * from table where left between xxx and yyyy
(wobei xxx der left wert und yyyy der right wert sind, ab dem datensatz von wo man die restlichen daten haben will.

da bei mir 99,9% selectionen anfallen, macht es viel sinn dieses modell zu wählen. nachteil des modelles sind die hohen "kosten" beim manipulieren des baumes (dies kommt aber nur 1 bis 2 mal am tag vor, wenn überhaupt).

DerDesian

Ich bin mir nicht sicher ob ich das 'Nested-Modell' richtig verstanden habe.
Wenn ich das richtig verstanden habe bedeutet dies, dass die reihenfolge der IDs eine Rolle spielt und dass diese in einem betimmten Wertebereich liegen müssen um in einem Teilbaum zu sein...

Fragen, die ich dazu hätte:
Stehen in 'left' IDs
Stehen in 'right' IDs
Wofür steht die 'root_id'
Nach welchen Kriterien werden 'left' bzw 'right' eingetragen?

__________________
Wenn dich was ankotzt, machs besser.

raffnix

bevor ich mir die finger wund schreibe, hier ein paar links :wink:

http://www.develnet.org/36.html
http://ffm.junetz.de/members/reeg/DS...00000000000000

gruß und danke

xabbuh

Macht meiner Meinung nach Sinn.

Bei den drei Schritten verstehe ich nicht, was genau du damit meinst.

Wozu willst du die Einträge löschen?

Wichtig wäre meiner Ansicht nach, dass zunächst left und right aller Einträge, die sich nicht in dem zu verschiebenen Subtree befinden, so angepasst werden, dass die beim Verschieben entstehende Lücke nicht auftritt.
Anschließend können die zu verschiebenen IDs durch Aktualisierung von left und right an der neuen Position eingefügt werden.
Zum Schluß müssen dann nur noch left und right für die weiter "rechts" im Baum positionierten Knoten angepasst werden.

Bei Bedarf kann ich auch gerne mal nachschauen, ob ich etwas älteren Code von mir wiederfinde, in dem ich entsprechende Aktionen umgesetzt hatte.

raffnix

ja ... punkt 2-4 stammen aus meinen vielen gedanken darüber

mittlerweile scheiter ich an der manipulation von lft und rgt
irgendwie stell ich mich bei der "berechnung" der lft und rgt werte des zu verschiebenden subtrees zu dumm an

das erhöhen des rechten baumes ist kein problem, das hab ich schon hinbekommen *g* nur eben das manipulieren des einzufügenden subtrees scheitert

>Bei Bedarf kann ich auch gerne mal nachschauen, ob ich etwas älteren >Code von mir wiederfinde, in dem ich entsprechende Aktionen >umgesetzt hatte.

das wäre cool ein ansatz würde mir schon viel helfen
ein paar bier wären dir sicher

axo

versuch's mal hiermit:
http://pear.php.net/package/DB_NestedSet
guck dir dabei die DB_NestedSet_DB::moveTree() - methode an.

grüße
axo

raffnix

danke für deinen tipp.


das hatte ich schon gefunden ... bin leider nicht daraus schlau geworden

axo

naja, wenn du den code nicht durchs durchlesen nachvollziehen kannst, solltest du evtl. einfach die pear-klasse verwenden, denn dann bist du noch nicht ganz soweit, um das problem selbst zu lösen.
das verwenden der klasse ist eh schon nicht ganz einfach, aber bei weitem einfacher als das selber-implementieren, und deinem wissensstand wohl eher angemessen.

die klasse ist mehr als nur gut dokumentiert, und alles was es dazu zu sagen gibt, haben die jungs als kommentare in den quellcode geschrieben. eine persönliche anleitung auf deutsch kannste dir knicken, das dauert zu lang, und du solltest eh schnell englisch lernen.

führe die klasse halt aus, sie hat sogar einen debug-modus, mithilfe dessen du wunderbar sehen kannst, was intern passiert.

[edit]
... und wenn du's brennend wissen willst:
http://www.amazon.com/gp/product/1558609202
soweit ich weiß, kann man das nur per amazon usa bestellen, dauert dementsprechend 4 wochen bis es da ist, aber es ist das einzige buch, das bäume in sql überhaupt behandelt (zumindest ist das mein wissensstand).
[/edit]

grüße
axo