Nested Sets Tutorial

[zagibu]

In diesem Tutorial habe ich gelesen, wie man einen Binärbaum mit Nested Sets in einer DB geschickt abspeichern kann. Es wird am Anfang erwähnt, dass das vorgestellte Modell auch für Bäume mit beliebig vielen direkten Kindknoten angewendet werden kann. Leider wird nicht gezeigt, wie das funktionieren soll. Konkret möchte ich solche Bäume mit einer konstanten Zahl von SQL Abfragen auslesen können:

Knoten1
|-Knoten1.1
| |-Knoten1.1.1
| |-Knoten1.1.2
| | |-Knoten1.1.2.1
| |-Knoten1.1.3
|-Knoten1.2
|-Knoten1.3
| |-Knoten1.3.1
|-Knoten1.4

Im Tutorial werden ja die Kindknoten direkt als Felder der (Eltern-) Knoten implementiert. Dies führt ja aber zu einer fixen Anzahl, welche eben in meiner Situation nicht nützlich ist.

[zagibu]

Ich habe nun eine Lösung hingebastelt und bitte um Kommentar:

CREATE TABLE nested_set (
   set_id INT UNSIGNED PRIMARY KEY,
   top_id INT UNSIGNED,
   next_id INT UNSIGNED,
   sub_id INT UNSIGNED,
   ...);

Vielleicht ist die Syntax nicht ganz richtig. Aber egal. So eine Tabelle erlaubt das Speichern eines Baumes, welcher pro Knoten beliebig viele Unterknoten haben kann. Die set_id dient ganz einfach als Tabellenid. Die top_id speichert die Tabellenid (set_id) des obersten Knotens eines Unterbaumes (zum schnellen Auslesen von Unterbäumen mittels einer einzigen SELECT Abfrage). Die next_id zeigt auf den nächsten Nachbarknoten. Bleibt noch die sub_id, welche auf den ersten Unterknoten zeigt.

Folgender Baum:

Knoten 1
|- Knoten 1.1
|  |- Knoten 1.1.1
|- Knoten 1.2
|- Knoten 1.3

könnte also so gespeichert werden:

Name          set_id top_id next_id sub_id
Knoten 1      1      1      -       2
Knoten 1.1    2      1      4       3
Knoten 1.1.1  3      1      -       -
Knoten 1.2    4      1      5       -
Knoten 1.3    5      1      -       -

Ein Algorithmus zum rekursiven Durchlaufen des Baumes würd dann z.B. so aussehen:

Funktion verarbeiteKnoten(knoten_id)
   // Soweit als möglich in die Blätter absteigen (depth first)
   if(knoten_id.sub_id != NULL)
      verarbeiteKnoten(knoten_id.sub_id);
   // Code zum verarbeiten des Knotens
   bla;
   // Den nächsten, gleichberechtigten Knoten verarbeiten
   if(knoten_id.next_id != NULL)
      verarbeiteKnoten(knoten_id.next_id);

[Coragon Rivito]

welcher art sollte der kommentar denn sein ?

[zagibu]

Jeglicher Kommentar ist erwünscht...ich habe das nur so auf Papier entwickelt, noch nicht getestet, und da ich nicht gerade ein Datenbank-Profi bin, erwarte ich eigentlich Verbesserungsvorschläge. Aber du kannst mich auch lobpreisen, wenn du willst . Nein, im Ernst, ich wäre schon froh, wenn man mir sagen würde, ob ich mich verständlich ausgedrückt habe...

[Coragon Rivito]

deine struktur hat imho nichts mit nested sets zu tun, und auch wenn du durch deine top_id nur eine query zum abfragen alles kindsknoten hast brauchst du eine rekursive funktion um diese zu verarbeiten

lies dir mal diesen thread hier durch
http://php-resource.de/forum/showthr...threadid=40604

speziell meinen post auf der 2ten seite ..
wie du siehst ist einiges möglich - bei meinem 3ten bin ich in den zweig 'produkte' abgetaucht, wähle daher diese aus
allerdings will der user sicher die möglichkeit direkt auch die hauptelemente der navigation anspringen zu können, daher auch diese elemente, was die IN() operation (ausdruck, was immer, ..) ermöglicht: " IN ('/', '/produkte') "

wie du siehst lass ich mir auch den virtuellen pfad zurückgeben, das erleichtert ein mod_rewrite ungemein ..

also spiel dich etwas, solltest du noch was am herzen haben, nur zu ..

[zagibu]

Warum hat die Struktur nichts mit Nested Sets zu tun? Im Tutorial wird ja genau die gleiche Struktur verwendet, nur eben mit fixen Feldern für die Kindelemente (was das speichern beliebig-dimensionaler Bäume eben verunmöglicht).

Und ich habe ja eine rekursive Funktion. Mit meiner Struktur kann ich mit einer einzigen SELECT Anweisung einen gesamten Unterbaum auslesen. PHP kann den dann rekursiv durchlaufen. Wie das anders gehen soll, kann ich mir gar nicht vorstellen (ausser vielleicht mit verschachtelten SELECTs).

Wenn man noch ein bisschen mehr Komfort braucht, kann man doch noch die parent_id für jeden Knoten abspeichern. Da liesse sich doch dann so einiges machen mit, z.B. schnell prüfen, ob ein Knoten ein Nachfahre eines anderen Knoten ist (quasi den Baum rückwärts über die parent_id durchlaufen).

Dein Post mit den komplizierten SQL Anweisungen verwirrt mich etwas. 0.22 Sekunden für ein Resultat von 8 Zeilen? Selbst wenn die Zeit dieser Abfrage linear zur Anzahl der abgefragten Elemente steigt, ist das für mich absolut unbrauchbar, da ich Bäume mit hunderten von Knoten auslesen muss.

[asp2php]

Original geschrieben von zagibu
[B]Warum hat die Struktur nichts mit Nested Sets zu tun? Im Tutorial wird ja genau die gleiche Struktur verwendet, nur eben mit fixen Feldern für die Kindelemente [color=blue](was das speichern beliebig-dimensionaler Bäume eben verunmöglicht)[/color].

lese bitte genau durch, bevor du sowas behauptest . Deine Struktur ist die s.g. id->parentid Struktur und hat nichts mit NS zu tun. Aber deine Struktur ist auch 'ne verkorste. Denn du hast 2 rekursive Aufrufe in der Funktion selbst und das ist u.U. tödlich für den Stack.

Und ich habe ja eine rekursive Funktion. Mit meiner Struktur kann ich mit einer einzigen SELECT Anweisung einen gesamten Unterbaum auslesen. PHP kann den dann rekursiv durchlaufen. Wie das anders gehen soll, kann ich mir gar nicht vorstellen (ausser vielleicht mit verschachtelten SELECTs).

mit einer anderen DBMS, z.B. MS SQL 2005 kannst du rekursive Abfrage ganz dem DBMS überlassen

Nested Sets eignet sich für nicht sehr oft veränderliche Struktur, denn Einfügen/Löschen bedeutet auch, dass man eventuell die ganze Tabelle updaten muss. Doch auslesen nur mit einer einfachen Abfrage und darin liegt die Stärke des Models. Und man kann beliebig tief verschachtelte Struktur damit aufnehmen.

id->parentid dagegen eignet sich besonders gut für oft veränderliche Strukturen, denn man kann ohne Weiteres ein neues Element hinzufügen, ohne die ganze Tabelle zu verändern. Der Nachteil ist das Auslesen. Durch rekursive Aufrufe besteht die Gefahr eines Stack-Overflows und daher kann nicht beliebig tief verschachtelt werden.

[zagibu]

Anscheinend verstehe ich wirklich etwas nicht. Wie kann man denn im Tutorial gezeigten Modell einen Baum mit 3 Unterknoten pro Knoten speichern?

Und wenn mein Modell für Schreibzugriff optimiert ist, dann passt mir das wunderbar, denn ich muss tatsächlich sehr oft reinschreiben (etwa jeder dritte Zugriff wird ein Schreibzugriff sein).

Und bisher hatte ich in PHP nie Probleme mit rekursiven Funktionen, die sich zwei mal in sich selbst aufrufen. Sehe auch nicht genau ein, wo da das Problem sein soll, schliesslich kommen die Selbstaufrufe nur nacheinander vor.

[asp2php]

Original geschrieben von zagibu

Und bisher hatte ich in PHP nie Probleme mit rekursiven Funktionen, die sich zwei mal in sich selbst aufrufen. Sehe auch nicht genau ein, wo da das Problem sein soll, schliesslich kommen die Selbstaufrufe nur nacheinander vor.

Dann erzählt mir mal wo das System die Rücksprungadresse ablegt! Du weisst anscheinend auch nicht so genau, wie das intern mit rekursive Aufrufe geregelt wird.

[zagibu]

Original geschrieben von asp2php
Dann erzählt mir mal wo das System die Rücksprungadresse ablegt! Du weisst anscheinend auch nicht so genau, wie das intern mit rekursive Aufrufe geregelt wird.

Nein, das weiss ich tatsächlich nicht. Aber ich habe schon oft Rekursion in PHP Skripts benutzt; bisher ohne Probleme. Ich danke dir aber für den Hinweis, und werde dies bestimmt als erste Fehlerquelle erwägen, wenn was schief geht.

Naja, da ja mein Vorschlag nicht so gut angekommen ist, möchte ich noch fragen, wie man sowas denn besser lösen könnte. Wie gesagt muss ein Baum mit beliebig vielen Kindern pro Knoten abgespeichert werden, welcher oft ausgelesen und nicht viel weniger oft beschrieben werden soll.

[Coragon Rivito]

vlt ne mischung aus beiden modellen ? gibts denn eine möglichkeit deinen baum in mehrere aufzuteilen, also teilbereiche in etwa ..