Warum Nested Sets ?

[heinetz]

Hallo Forum,

ich habe mir vor langer Zeit für eine Website eine sehr
komplizierte Abbildung der Baustruktur der Inhalte
überlegt. Dass die sehr ungeeignet ist ist mir lange
bewusst. Denoch gab es daran etwas zu tun, was ich mit der
Hilfe von Vinzenz Mai auch lösen konnte.

http://forum.de.selfhtml.org/archiv/2010/3/t196053/

Er hat mich auf etwas gestossen, was ich sehr interessant fand:

Nested Sets ... zur Abbildung einer Baumstruktur

Ein faszinierende Modell! Damit habe ich nun etwas herumprobiert
und festgestellt, dass das Auslesen von Informationen sehr
elegant funktioniert. Das ändern der Struktur (einfügen von
Blättern, verschieben von Ästen, löschen usw.) erscheint mir
allerdings recht aufwendig.

Jetzt frage ich mich, ob en einfaches Parentmodell (jeder id
wird eine parent_id) zugeordnet für meinen Fall nicht doch
besser geeingent ist.

Mein Fall:
----------
Ich verwalte meine Seiten mit einem selfmade CMS. Darüber muss
es möglich sein, eine Seite an jede Stelle zu verschieben. Ich
müsste also für nur einen Datensatz die parent_id ändern, um
das zu tun. Das Auslesen der Struktur geschieht an nur zwei
Stellen: Das ist zum einen ein Menü über zwei Ebenen und zum
Anderen der Breadcrump, der mehr Ebenen, allerdings auch höchstens
6 haben kann.

Was meint ihr ? / Gibt es u.U. ein optimiertes Parent-Modell ?

danke fuer tipps und

beste gruesse,
heinetz

[dedlfix]

Hi!

Nested Sets ... zur Abbildung einer Baumstruktur
Ein faszinierende Modell! Damit habe ich nun etwas herumprobiert
und festgestellt, dass das Auslesen von Informationen sehr
elegant funktioniert. Das ändern der Struktur (einfügen von
Blättern, verschieben von Ästen, löschen usw.) erscheint mir
allerdings recht aufwendig.

Das zweite ist der Preis für das erste. Deswegen sollte man abwiegen, of die Nachteile nicht die Vorteile überwiegen. Das kann passieren, wenn deutlich mehr geschrieben als gelesen wird.

Jetzt frage ich mich, ob en einfaches Parentmodell (jeder id
wird eine parent_id) zugeordnet für meinen Fall nicht doch
besser geeingent ist.

Es kommt darauf an, was für Lesevorgänge du hast. Wenn du immer nur eine Ebene abfragst, reicht ein Parentvergleich. Wenn du allerdings auch alle Nachfahren benötigst, gibt es eigentlich nichts besseres. Die Alternative wäre, das DBMS mit rekursiven Anfragen zu überhäufen, oder stets den gesamten Datenbestand (so sich nicht anderweitig die Menge einschränken lässt) abzufragen und auf dem Client (PHP etc.) zu durchlaufen. Für kleine Strukturen/Datenmengen ginge auch noch ein Serialized LOB (auch nicht nachteilsfrei).

Lo!

[heinetz]

Hi,

Es kommt darauf an, was für Lesevorgänge du hast. Wenn du immer nur eine Ebene abfragst, reicht ein Parentvergleich. Wenn du allerdings auch alle Nachfahren benötigst, gibt es eigentlich nichts besseres. Die Alternative wäre, das DBMS mit rekursiven Anfragen zu überhäufen, oder stets den gesamten Datenbestand (so sich nicht anderweitig die Menge einschränken lässt) abzufragen und auf dem Client (PHP etc.) zu durchlaufen. Für kleine Strukturen/Datenmengen ginge auch noch ein Serialized LOB (auch nicht nachteilsfrei).

Die Lese und Schreibvorgänge sind konkret folgende (soweit ich
das überblicken kann):

Frontend:

Lesend wir auf jeder Unterseite die Struktur an zwei Stellen
abgefragt. Da wäre

a) das Menü, dass nur die erste Ebene (Also Select * from structure where parent_id=0) und die die darunterliegende
des aktuell ausgewählten Bereichs anzeigt.

b) der Breadcrump, also alle Elternelemente der aktuellen
Seite bis zur Wurzel. Die Tiefe ist allerdings höchstens
6, wozu mir tatsächlich gerade nur ein rekursives Abfragen
einfallen würde.

Backend:

Hier wird zwar lesend der ganze Baum abgefragt. Allerdings
würde ich dazu mit SQL erstmal die ganze Struktur in ein
Array schreiben und das dann mit PHP strukturieren.

Ergo:
-----
Tatsächlich ist die Nested-Lösung für das Auslesen das
geschmeidigste und ich würde die Last im Frontend daher
zu ungunsten des Backends gering halten.

beste gruesse,
heinetz

[Vinzenz Mai]

Hallo,

Hier wird zwar lesend der ganze Baum abgefragt. Allerdings
würde ich dazu mit SQL erstmal die ganze Struktur in ein
Array schreiben und das dann mit PHP strukturieren.

Tatsächlich ist die Nested-Lösung für das Auslesen das
geschmeidigste und ich würde die Last im Frontend daher
zu ungunsten des Backends gering halten.

stelle Dir die Frage, wie oft (im Normalbetrieb) das Verschieben eines Artikels vorkommt - vor allem im Vergleich zur Anzeige des Artikels.

Freundliche Grüße

Vinzenz

[heinetz]

Hallo,

stelle Dir die Frage, wie oft (im Normalbetrieb) das Verschieben eines Artikels vorkommt - vor allem im Vergleich zur Anzeige des Artikels.

Die Frage ist mir meiner Aussage:

Tatsächlich ist die Nested-Lösung für das Auslesen das
geschmeidigste und ich würde die Last im Frontend daher
zu ungunsten des Backends gering halten.

... eigentlich beantwortet. Die Site läuft für den User relativ
performant, beim Verschieben einer Seite für den Redaktuer
relativ langsamer.

Das spricht natürlich für das Nested Set.

Das was mir wirklich Sorge bereitet ist eher, ob und wie ich
meine Strktur im Backend um lft und rgt erweitern und die
Werte darin initial richtig setzen und bei Veränderung der
Struktur ändern kann.

beste gruesse,
heinetz

[dedlfix]

Hi!

Das was mir wirklich Sorge bereitet ist eher, ob und wie ich
meine Strktur im Backend um lft und rgt erweitern und die
Werte darin initial richtig setzen und bei Veränderung der
Struktur ändern kann.

Das finde ich keine gute Idee. Stattdessen würde ich für die Änderungsvorgänge Stored Procedures erstellen. Left und Right sind Werte, die im Prinzip nur das DBMS braucht, um das Nested-Sets-Muster zu realisieren. In der Anwendung würde ich sie nicht weiter rumschleppen als bis kurz nach der Abfrage, wenn die Daten in eine für die Anwendung brauchbare Struktur gebracht wurden.

Lo!

[heinetz]

Hi,

Das was mir wirklich Sorge bereitet ist eher, ob und wie ich
meine Strktur im Backend um lft und rgt erweitern und die
Werte darin initial richtig setzen und bei Veränderung der
Struktur ändern kann.

Das finde ich keine gute Idee. Stattdessen würde ich für die Änderungsvorgänge Stored Procedures erstellen. Left und Right sind Werte, die im Prinzip nur das DBMS braucht, um das Nested-Sets-Muster zu realisieren. In der Anwendung würde ich sie nicht weiter rumschleppen als bis kurz nach der Abfrage, wenn die Daten in eine für die Anwendung brauchbare Struktur gebracht wurden.

ich verstehe Dich schon wieder nicht ;)

Ich habe eine laufende Anwendung, für die in einer Tabelle eine
Baumstruktur abgebildet ist. Diese Baumstruktur soll nun
zukünftig anders abgebildet werden. Von daher müssen die
entsprechenden Informationen, die für die neu Abbildung  der Struktur benötigt werden irgendwie inititial erstellt und im Weiteren aktuell gehalten werden. Wie auch immer man das macht.
"Stored Procedures" klingt interssant, ich weiss nichtmal was das
ist und denke, ich muss mir, wenn ich die Abbildung meiner
vorhandenen Struktur (700 Knoten) umstellen will, erstmal darüber
klar werden, wie das grundsätzlich geht.

beste gruesse,
heinetz

[ChrisB]

Hi,

kannst du bitte die manuellen Umbrüche beim Posten unterlassen?
Die erschweren sowohl das Lesen, als auch das partielle Zitieren.

Ich habe eine laufende Anwendung, für die in einer Tabelle eine  Baumstruktur abgebildet ist. Diese Baumstruktur soll nun zukünftig anders abgebildet werden.

Was meinst du damit - „anders abgebildet“? Wieso willst du die Struktur ändern?

Normalerweise ändert sich der *Inhalt*, nicht die Struktur.

Von daher müssen die entsprechenden Informationen, die für die neu Abbildung  der Struktur benötigt werden irgendwie inititial erstellt und im Weiteren aktuell gehalten werden.

Die Datenstruktur muss erst mal gefüllt, und anschliessend regelmässig gewartet werden. Soweit doch nichts ungewöhnliches.

"Stored Procedures" klingt interssant, ich weiss nichtmal was das ist

Mehrteilige SQL-Operationen, die in einer Prozedur zusammengefasst werden.
Bspw. erfordert das Umhängen eines Knotens in einer Nested Set-Struktur mehr als eine einzelne, singuläre Operation.
Die fasst man dann sinnvoller Weise in einer Stored Procedure zusammen. Die kann u.a. garantieren, dass die Änderung nur übernommen wird, wenn alle Operationen fehlerfrei ausgeführt werden konnten (vermeidet Inkonsistenzen), und auch Nebenläufigkeitsprobleme verhindern (dass bspw. zwei aufeianderfolgende Operationen vom selben Datenbestand ausgehen, obwohl dieser nicht mehr vorliegt, weil sich eine andere Operation dazwischen gedrängt hat).

MfG ChrisB

[dedlfix]

Hi!

Die [Stored Procedure] kann u.a. garantieren, dass die Änderung nur übernommen wird, wenn alle Operationen fehlerfrei ausgeführt werden konnten (vermeidet Inkonsistenzen), und auch Nebenläufigkeitsprobleme verhindern (dass bspw. zwei aufeianderfolgende Operationen vom selben Datenbestand ausgehen, obwohl dieser nicht mehr vorliegt, weil sich eine andere Operation dazwischen gedrängt hat).

Nee, das macht eine Stored Procedure noch nicht von allein. Dazu braucht es immer noch Transactions und damit bei MySQL die InnoDB-Engine. Für die Nebenläufigkeitsproblemverhinderung reicht allerdings schon Locking, was auch mit MyISAM geht.

Lo!

[heinetz]

hi,

Was meinst du damit - „anders abgebildet“? Wieso willst du die Struktur ändern?

Normalerweise ändert sich der *Inhalt*, nicht die Struktur.

Damit meine ich, dass sowohl Inhalt als auch eine Struktur dieser bereits vorhanden ist. Redakteure haben die Möglichkeit, diese Struktur laufend erweitern/verändern und ich muss mir überlegen, wie ich diese Erweiterung/Veränderung dahingehend erweitere, dass diese Änderung jeweils in dem neuen "Nested Sets"-Muster übernommen wird bzw wie sich konkret die Werte für lft und rgt aus den Werten die mir aus der bestehenden Struktur zur Verfügung stehen, ableiten lassen.
Dazu gehören u.U. mehrere SQL-Satements und dafür dann Stored Procedures zu verwenden ist sicher eine gute Idee aber ich mache mir noch Gdanken darüber, wie sich einen Zusammenhang zwischen meiner bestehenden Struktur und dem neuen Muster herstellen lässt.

gruesse,
heinetz

[dedlfix]

Hi!

Das was mir wirklich Sorge bereitet ist eher, ob und wie ich meine Strktur im Backend um lft und rgt erweitern und die Werte darin initial richtig setzen und bei Veränderung der Struktur ändern kann.

Das finde ich keine gute Idee. Stattdessen würde ich für die Änderungsvorgänge Stored Procedures erstellen. Left und Right sind Werte, die im Prinzip nur das DBMS braucht, um das Nested-Sets-Muster zu realisieren. In der Anwendung würde ich sie nicht weiter rumschleppen als bis kurz nach der Abfrage, wenn die Daten in eine für die Anwendung brauchbare Struktur gebracht wurden.

ich verstehe Dich schon wieder nicht ;)

Was genau meintest du jetzt mit Backend? Das DBMS von PHP aus gesehen oder vom Anwender aus gesehen alles was im Server abläuft. Ich hatte letzteres im Sinne und nahm an, du meintest das Left-Right auch noch in den PHP-Strukturen abbilden zu wollen. Kannst du nun meine Antwort besser einsortieren und vielleicht auch als unbegründete Befürchtung abtun?

Diese Baumstruktur soll nun zukünftig anders abgebildet werden. Von daher müssen die entsprechenden Informationen, die für die neu Abbildung  der Struktur benötigt werden irgendwie inititial erstellt und im Weiteren aktuell gehalten werden.

Ja, das ist ein einmaliger Prozess. Wenn die Daten nicht zu viele sind, kann man das ja per Hand machen. Aber ich vermute, wenn du noch nicht selbst auf die Idee gekommen bist, oder sie bereits abgewiesen hast, dass es mehr sind.

Wie auch immer man das macht.

Ich würde zunächst die Verwaltungsroutinen schreiben, also "Datensatz als neues Kind anhängen" und "Datensatz als Geschwist einfügen" - egal ob als mehrere von PHP abgesendete Statements oder als Stored Procedure. Wenn die zur Zufriedenheit laufen, dann schriebe ich mir eine kleine Routine, die die Einsortiererei mit eben diesen Funktionen vornimmt.

Lo!