Ab wann rentieren sich Nested Sets?

Hallo,

ich habe, basiert auf dieser Vorlage:

http://myiosoft.com/?1.151.0.0

Ein wenig mit Tree-Basierter Navigation rumprobiert, da ich diese in
einem Eigenbau-CMS umsetzen möchte.

Das Beispiel basiert darauf, dass jeder Eintrag lediglich ein Feld
"Parent" hat, welches auf das übergeordnete Element referenziert.

Das Beispiel liest zur Anzeige des Baumes zunächst alle Elemente aus dem
SQL aus, um diese dann über eine rekursive Funktion aufzubauen.

Ich habe das ganze zunächst testhalber so umgerüstet, dass, statt "alles
auslesen", für jede Ebene ein SQL-Query abgesetzt wird. Es hat sich mit
dieser Lösung aber schnell herausgestellt, dass ab einer Tiefe von 4 bis
5 Ebenen die "alles lesen und mit PHP ausgeben"-Lösung deutlich
schneller war.

Mehrere SQL-Abfragen sind also schlecht.

Um zum einen den Code für mich leserlicher zu gestalten, aber auch um zu
testen, ob sich das noch performanter machen lässt, habe ich den
PHP-Teil einmal ganz neu geschrieben und dabei bevorzugt mit Hash-Arrays
gearbeitet, um spätere Suchvorgänge auf den gelesenen Daten zu
beschleunigen.

Das Ergebnis ist nicht schlecht. Die 500 Testknoten werden in ca. 0.007
bis 0.009 Sekunden aufgebaut.

Frage: Was genau spricht gegen dieses "alles lesen und mit PHP
aufbauen"-Prinzip? Der einzige Nachteil, der mir eingefallen ist, wäre
der höhere Speicherverbrauch, da hier ja immer alle Knoten geladen
werden, obwohl ja nur die paar gebraucht werden, die der Nutzer später
auch sieht.

CU

Manuel

--
Privatsphäre bald Geschichte? Vorratsdatenspeicherung, Bundestrojaner, ...
Informieren, bevor es zu spät ist! Es sind auch deine Rechte!
www.vorratsdatenspeicherung.de www.der-bundestrojaner.de
www.againsttcpa.com www.privatkopie.net www.foebud.org

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer!

> Frage: Was genau spricht gegen dieses "alles lesen und mit PHP
> aufbauen"-Prinzip?

Eigentlich nichts...

Du fragst nach Nested Sets. Um einen kompletten Baum auszugeben, würdest
du ihn auch mit Nested Sets auf einmal lesen. Nur der Teil "mit PHP
aufbauen" wird einfacher, da die DB die Struktur des Baums schon gratis
mitliefern kann.

Aber solang du alles ausgeben willst, musst du logischerweise auch alles
lesen, und das dauert mehr oder weniger immer gleichlang.

Die Vorteile von Nested Sets liegen anderswo, z.B. ist die Suche in einem
Teilbaum deutlich einfacher zu formulieren und generell kann beim Lesen
oft auf Rekursion verzichtet werden.


Gruß
Daniel

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer wrote:
> Das Beispiel basiert darauf, dass jeder Eintrag lediglich ein Feld
> "Parent" hat, welches auf das übergeordnete Element referenziert.

Das hat mit "Nested Sets" aber nichts zu tun.

Lies dazu mal
http://www.klempert.de/nested_sets/artikel/

Mit echten Nested Sets kannst du einzelne Äste eines Baums aus der Datenbank
auch ohne rekursive Datenbankabfragen und unabhängig von der
Verschachtelungstiefe einlesen.

Re: Ab wann rentieren sich Nested Sets?

Daniel Fischer wrote:
> Aber solang du alles ausgeben willst, musst du logischerweise auch alles
> lesen, und das dauert mehr oder weniger immer gleichlang.

Ich will aber nicht alles lesen, sondern nur, wie im angesprochenen
Demo, den aktuellen Pfad zum gewählten Punkt in der Navi aufklappen.

Allerdings scheinen gerade hier Nested Sets leicht ungeeignet. Der
Aufbau einer solchen Ansicht ist wohl mit etwas Aufwand verbunden:

http://boardunity.de/sub-tree-abfrage-mit-nestedset-model-t2 938.html

Was mir bei meiner "Alles aus DB lesen aber nur einen Teil
Ausgeben"-Lösung aber nicht gefällt ist, dass für einen Bruchteil einer
Sekunden der gesamte Datenbank-Inhalt mindestens einmal im Speicher
liegt (da ich der Einfachkeit halber zwei Hash-Arrays erzeuge liegen die
Daten sogar doppelt im Speicher).

CU

Manuel

--
Privatsphäre bald Geschichte? Vorratsdatenspeicherung, Bundestrojaner, ...
Informieren, bevor es zu spät ist! Es sind auch deine Rechte!
www.vorratsdatenspeicherung.de www.der-bundestrojaner.de
www.againsttcpa.com www.privatkopie.net www.foebud.org

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer schrieb:
> Was mir bei meiner "Alles aus DB lesen aber nur einen Teil
> Ausgeben"-Lösung aber nicht gefällt ist, dass für einen Bruchteil einer
> Sekunden der gesamte Datenbank-Inhalt mindestens einmal im Speicher
> liegt (da ich der Einfachkeit halber zwei Hash-Arrays erzeuge liegen die
> Daten sogar doppelt im Speicher).

Wenn's nur ein paar hundert Sätze sind, spielt das keine wirklich große
Rolle.
Wenn die Anwendung auf ein paar zig- bis hunderttausend Sätze skalieren
soll, dann natürlich schon. Dann würd mich allerdings interessieren, was
für Daten das sind, abgesehen von industriellen Stücklisten fallen mir
eigentlich keine hierarchischen Datensammlungen mit nennenswertem Umfang
ein :-)

Grüße
Jo

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer schrieb:
>> Aber solang du alles ausgeben willst, musst du logischerweise auch alles
>> lesen, und das dauert mehr oder weniger immer gleichlang.
>
> Ich will aber nicht alles lesen, sondern nur, wie im angesprochenen
> Demo, den aktuellen Pfad zum gewählten Punkt in der Navi aufklappen.

Also willst du einfach nur den Unterbaum bzw. die nächste Ebene lesen.
Mit einem Nested Set ist das eine simple Abfrage, die dir genau die
gewünschten Zeilen liefert. Und zwar in der gewünschten Reihenfolge und
mit immer der gleichen Abfrage (von der Parent-ID mal abgesehen). Egal,
ob du nur die nächste Ebene oder alle Unterebenen lesen möchtest.

> Allerdings scheinen gerade hier Nested Sets leicht ungeeignet. Der
> Aufbau einer solchen Ansicht ist wohl mit etwas Aufwand verbunden:

Nein, das ist gerade der klassische Fall, in dem Nested Sets sinnvoll
sind. Immer dann, wenn du eine Baumstruktur (und ein Menü ist ja nichts
anderes) in der DB ablegen willst, ist das Nested Set ein interessantes
Modell.
Ob das Nested Set das Mittel der Wahl ist, hängt aber auch noch davon
ab, wie das Verhältnis zwischen Lesen und Verändern des Baums ist. Eine
grobe Näherung wäre, 1/4 Änderung zu 3/4 Lesen, damit das Nested Set
sich lohnt. In der Realität wird aber entweder etwa gleich oft gelesen,
wie geschrieben, oder es gibt ein vielfach häufigeres Lesen, als
Schreiben (meine Erfahrungswerte).
Zu beachten: Ich rede hier von Ändern bzw. Lesen der Struktur, nicht der
darin gespeicherten Nutzdaten. Bei den Nutzdaten ist es fast egal,
welches Modell man verwendet. Aber das Ändern der Baumstruktur ist
tatsächlich viel Aufwand (jedenfalls für die DB).

Grüße,
Dominik

Re: Ab wann rentieren sich Nested Sets?

Dominik Echterbruch wrote:
> Also willst du einfach nur den Unterbaum bzw. die nächste Ebene lesen.
> Mit einem Nested Set ist das eine simple Abfrage, die dir genau die
> gewünschten Zeilen liefert. Und zwar in der gewünschten Reihenfolge und
> mit immer der gleichen Abfrage (von der Parent-ID mal abgesehen). Egal,
> ob du nur die nächste Ebene oder alle Unterebenen lesen möchtest.

Nein, nicht ganz.

Ich möchte *genau* *das*, was auch im ersten Posting des Threads unter

http://boardunity.de/sub-tree-abfrage-mit-nestedset-model-t2 938.html

gefordert ist.

Bekannt ist nicht die Parent-ID, sondern die Node-ID des Nodes, der vom
Benutzer gerade angesehen wird. Der Pfad zu diesem Knoten soll komplett
angezeigt werden. Aber eben nur der kürzeste Weg zum Knoten und die
"direkt anliegenden Nachbarn" der einzelnen Ebenen (siehe besagtes
Posting).

Diskutiert habe ich das Thema jetzt schon mehrfach. Allerdings bin ich
in diesem Forum zum ersten Mal fündig geworden, wie man genau das mit
*zwei* Abfragen hinbekommen kann.

> Ob das Nested Set das Mittel der Wahl ist, hängt aber auch noch davon
> ab, wie das Verhältnis zwischen Lesen und Verändern des Baums ist. Eine
> grobe Näherung wäre, 1/4 Änderung zu 3/4 Lesen, damit das Nested Set
> sich lohnt. In der Realität wird aber entweder etwa gleich oft gelesen,
> wie geschrieben, oder es gibt ein vielfach häufigeres Lesen, als
> Schreiben (meine Erfahrungswerte).

Es soll mal ein einfaches CMS werden. Es wird also definitiv häufiger
gelesen wie geschrieben.

Wie schaut es eigentlich aus, wenn man bei Nested Sets einen Fehler
baut? Einmal einen Left oder Right-Wert falsch gesetzt und eine Tabelle
mit hunderten Einträgen kann defekt sein, oder?

Gibt es fertige Klassen, die das Nested Set Modell leichter beherrschbar
machen? Zumindest im Adminbereich, in dem die Tabelle geändert wird,
hätte ich da doch gerne etwas, das sich in der Praxis bewährt hat. Ich
dachte da zunächst an PEAR, allerdings wurde die Nested Set-Klasse dort
zuletzt vor Jahren geändert.

Da wo es auf Sicherheit ankommt (bei der Anzeige) erstelle ich die
SQL-Abfragen aber lieber selber und ohne "Fremde" Klassen. Werden ja
maximal zwei SQL-Queries.

CU

Manuel

--
Privatsphäre bald Geschichte? Vorratsdatenspeicherung, Bundestrojaner, ...
Informieren, bevor es zu spät ist! Es sind auch deine Rechte!
www.vorratsdatenspeicherung.de www.der-bundestrojaner.de
www.againsttcpa.com www.privatkopie.net www.foebud.org

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer meinte:

> Ich möchte *genau* *das*, was auch im ersten Posting des Threads unter
>
> http://boardunity.de/sub-tree-abfrage-mit-nestedset-model-t2 938.html
>
> gefordert ist.
>
> Bekannt ist nicht die Parent-ID, sondern die Node-ID des Nodes, der vom
> Benutzer gerade angesehen wird. Der Pfad zu diesem Knoten soll komplett
> angezeigt werden. Aber eben nur der kürzeste Weg zum Knoten und die
> "direkt anliegenden Nachbarn" der einzelnen Ebenen (siehe besagtes
> Posting).

In meinen Nested Sets trage ich Ebene, Parent und Root beim Schreiben
gleich mit ein - minimaler Aufwand und den gesamten Pfad zu deinem Node
kriege ich damit auch über eine einzelne Query.

> Es soll mal ein einfaches CMS werden. Es wird also definitiv häufiger
> gelesen wie geschrieben.

Umso besser für eine Nested-Sets-Lösung.

> Wie schaut es eigentlich aus, wenn man bei Nested Sets einen Fehler
> baut? Einmal einen Left oder Right-Wert falsch gesetzt und eine Tabelle
> mit hunderten Einträgen kann defekt sein, oder?

Naja, entsprechende Routinen sind ja nicht kompliziert, und vorheriges
Testen wird wohl drin sein.

> Gibt es fertige Klassen, die das Nested Set Modell leichter beherrschbar
> machen? Zumindest im Adminbereich, in dem die Tabelle geändert wird,
> hätte ich da doch gerne etwas, das sich in der Praxis bewährt hat. Ich
> dachte da zunächst an PEAR, allerdings wurde die Nested Set-Klasse dort
> zuletzt vor Jahren geändert.

Naja, meine alte, prozedural geschriebene Nested-Sets-Funktionssammlung
hat den Umfang von (kreisch!) 121 Codezeilen. Wenn dich das Thema
interessiert: Warum nicht selber sowas machen?

> Da wo es auf Sicherheit ankommt (bei der Anzeige) erstelle ich die
> SQL-Abfragen aber lieber selber und ohne "Fremde" Klassen. Werden ja
> maximal zwei SQL-Queries.

Das hätte man damit auch gleich erledigt.

Gregor


--
http://www.gregorkofler.at ::: Landschafts- und Reisefotografie
http://www.licht-blick.at ::: Forum für Multivisionsvorträge
http://www.image2d.com ::: Bildagentur für den alpinen Raum

Re: Ab wann rentieren sich Nested Sets?

Manuel Reimer schrieb:
>> Also willst du einfach nur den Unterbaum bzw. die nächste Ebene lesen.
>> Mit einem Nested Set ist das eine simple Abfrage, die dir genau die
>> gewünschten Zeilen liefert. Und zwar in der gewünschten Reihenfolge
>> und mit immer der gleichen Abfrage (von der Parent-ID mal abgesehen).
>> Egal, ob du nur die nächste Ebene oder alle Unterebenen lesen möchtest.
>
> Nein, nicht ganz.
> Ich möchte *genau* *das*, was auch im ersten Posting des Threads unter

Sorry, ich bin etwas zu faul, mir das Ding durchzulesen. Aber wie auch
immer. Selbst dieses Problem

> Bekannt ist nicht die Parent-ID, sondern die Node-ID des Nodes, der vom
> Benutzer gerade angesehen wird. Der Pfad zu diesem Knoten soll komplett
> angezeigt werden. Aber eben nur der kürzeste Weg zum Knoten

ist mit einer einfachen Abfrage zu erschlagen. Notfalls kommt halt noch
ein zweiter Selfjoin hinzu, aber das ist ja nun wirklich ein Kinderspiel
im Vergleich zu dem, was nötig ist, um einen solchen Pfad mit nur einer
Parent-ID pro Knoten zu bauen.

> und die
> "direkt anliegenden Nachbarn" der einzelnen Ebenen (siehe besagtes
> Posting).

Das könnte dann evtl. ein bißchen Aufwand bedeuten, aber dafür müßte ich
jetzt etwas länger nachdenken. Dafür ist es jetzt einfach zu spät.
Vielleicht morgen wieder :)

> Diskutiert habe ich das Thema jetzt schon mehrfach. Allerdings bin ich
> in diesem Forum zum ersten Mal fündig geworden, wie man genau das mit
> *zwei* Abfragen hinbekommen kann.

Ich kann mir gut vorstellen, daß mit einem Nested Set alle Daten in
einem Rutsch fix und fertig mit der Ebene, an der der jeweilige Eintrag
steht, ausgelesen werden kann. Ohne sinnlose Eliminierung überflüssiger
Erebniszeilen etc. Aber wie gesagt, dazu brauche ich ein bißchen...

> Wie schaut es eigentlich aus, wenn man bei Nested Sets einen Fehler
> baut? Einmal einen Left oder Right-Wert falsch gesetzt und eine Tabelle
> mit hunderten Einträgen kann defekt sein, oder?

Ja, aber genau dafür gibt es Transaktionen und Funktionen, die die
nötigen Operationen kapseln bzw. Änderungen rückgängig machen, wenn
nicht alles erfolgreich war.

> Gibt es fertige Klassen, die das Nested Set Modell leichter beherrschbar
> machen? Zumindest im Adminbereich, in dem die Tabelle geändert wird,
> hätte ich da doch gerne etwas, das sich in der Praxis bewährt hat. Ich
> dachte da zunächst an PEAR, allerdings wurde die Nested Set-Klasse dort
> zuletzt vor Jahren geändert.

Die älteste Doku zum Nested Set Modell, die ich kenne, stammt von 1994.
Das Thema ist also alles andere als neu. Außerdem ist das Nested Set nur
eine Verrenkung für's Hirn. Wenn man es mal wirklich verstanden hat, ist
es ziemlich simpel. Und ebenso simpel ist die Klasse, die sich um die
Struktur des Baumes kümmert. Da muß min nich tjahrelang basteln und
testen, um sicher zu sein, daß nichts mehr passieren kann. Gut, wenn
seit Jahren nichts mehr an der Klasse gemacht wurde, verwendet sie
vermutlich keine Transkationen, sondern stellt die Konsistenz der Daten
anders sicher. Aber was soll's...

Grüße,
Dominik

Re: Ab wann rentieren sich Nested Sets?

Dominik Echterbruch schrieb:
> wenn
> seit Jahren nichts mehr an der Klasse gemacht wurde, verwendet sie
> vermutlich keine Transkationen, sondern stellt die Konsistenz der Daten
> anders sicher. Aber was soll's...

Ich hab was von "LOCK TABLE" gelesen.

Transaktion wär natürlich besser, dann ist auch der Fall abgedeckt, dass
der Server mitten im Schreibvorgang abschmiert (Platte voll,
Stromausfall, Platte kaputt...)
Wenn solche Ausfallszenarien ein Faktor sind, kann man die Aufrufe immer
noch in eine Transaktion verpacken.