✔ Baumstruktur in Datenbank eintragen

[Sturmrider]

Guten Abend zusammen,
ich beschäftige mich schon seit längerem mit Bäumen und stehe nun vor einem Problem, auf welches ich leider noch keine zufriedenstellende Antwort gefunden habe
Die gängigen Ausgabe-Methoden eines Baums aus einer Datenbank (wie z.B. in diesem Tutorial: http://www.tutorials.de/forum/php-tutorials/27144-menusystem-mit-php-und-mysql.html) funktionieren ab einem bestimmten Fall nicht mehr:
id | childid | text
1 | 0 | ...
2 | 1 | ...
3 | 1 | ...
4 | 8 | ...
5 | 2 | ...
6 | 1 | ...
7 | 6 | ...
8 | 7 | ...

nämlich, wenn die childIds, parentIds oder wie man sie nennen möchte nicht mehr in einer Reihenfolge sind dies kann ja ziemlich schnell passieren, wenn man beispielsweise eine verschieben-Funktion hat, die ganze Zweige oder einfache Elemente verschieben kann...
Wie gestalte ich daher eine eingabe/verschieben-Funktion am besten so, dass der Eintrag an die richtige Position der childIds gesetzt wird?
Prinzipiell würde ich dies folgendermaßen machen (jedoch ergibt dies eine regelrechte Query-Flut und scheint mir wenig sinnvoll...):


-> einen Zweig (Z1) mit einer hohen childId (C1) einer id (Z2) mit einer viel niedrigeren childId (C2) zuordnen
1. C1 von Z1 durch C2 von Z2 ersetzen (damit bekommen wir oben angeführtes Problem)
2. nachfolgende ids nach Z2 alle mit der Anzahl der Elemente von Z1 addieren, sowie ihre childids anpassen (dies in einer rekursiven-Funktion (Query-Flut) -> dabei beachten, dass man nicht mit der id von Z1 kollidiert, diese also überspringt
3. alle Elemente von Z1, sowie ihren childids C1 in die entstandene Lücke aus 2. setzen und natürlich wieder childIds anpassen
4. die entstandene Lücke weiter hinten in den Ids aus 2., wo ja beachtet wurde, dass keine Kollision statt findet, mit evtl. nachfolgenden Ids stopfen und ihre childIds erneut anpassen... -> da bei mehrfachem verschieben sonst zu viele große Lücken entstehen und die Datenbank unübersichtlich wird...


Dies ist aber doch keine akzeptable Lösung...bei einem großen Baum bekomme ich so evtl. sogar ein buffer-overflow...

Wie habt/würdet ihr dieses Problem lösen? Habe ich vielleicht etwas übersehen?

 

[chainy]

Ich hab mich vergangene Woche erst mit Baumstrukturen auseinandergesetzt, bei der Lösung meines Problems hab ich auf die Nested-Set-Methodik gesetzt. Falls du als Grundlage das Zend Framework verwendest, könnte ich dir auch mein Model zur Verfügung stellen.

 

[Sturmrider]

*seufz* ohje, da muss ich mir wohl alle Funktionen die irgendwie mit dem Baum zu tun haben neu schreiben... naja, die Lösung mit den Levels ist echt clever! Auch wenn ich noch nicht ganz verstanden habe, wie sie festgelebt werden... aber wenn ich mir etwas Zeit nehme werde ich das sicher verstehen (ist ja schon spät ^^) -> aber du bist sicher, dass deine vorgeschlagene Methode auch bei meinem oben angeführtem beispiel funktioniert?
(ich möchte mich nicht stundenlang damit beschäftigt haben und am Ende erneut vor dem selben Problem stehen denn der Aspekt im Falle des Verschiebens eines Zweigs oder Element wird dort ja leider nicht behandelt vielleicht habe ich deswegen auch noch nicht ganz verstanden, wie dann die Levels noch bestimmt kann, wenn die ids und childIds wild durcheinander gemischt sind)

Danke für deine bisherige Hilfe das Problem scheint ja doch um einiges besser lösbar zu sein

 

[chainy]

Ich bin mir sicher, dass du mit der Methodik alle Baumfunktionen umsetzen kannst, die du benötigen wirst. Die Verschiebung eines Teilbaums wird in dem Artikel nicht behandelt, aber das ist auch nicht schwer, zur Not kann ich es dir auch erklären. Was ganz wichtig ist, sind die left und right Werte, die geben die Position des Knotens im Baum an und auch, ob der Knoten Kinder hat oder nicht.

 

[Sturmrider]

okay, vielen Dank dann werde ich mich damit auch mal befassen. Falls ich Fragen habe "öffne" ich diesen Thread wieder und schicke dir eine PN, wenn das i.o. ist
Vielen Dank nochmal! ^^

 

[chainy]

Kannst du gerne machen - ob ich dir auch antworte ist halt ne andere Frage. Nein Scherz, ist kein Problem

 

[splasch]

Die Lösung ist ganz einfach.Du muß dabei aber auch wissen wie Parent funktioniert.Es ist nicht nur ein sinlose Wort, sondern hinter dem Begriff steht einen eigene Technik.
Fals dir die nicht bekannt ist bescheid sagen und ich Erklär dir diese.

Das verschieben läst sich leicht machen über einen einfachen sql befehl dazu brauchst du aber in deiner Tabele eine weitere Spalte:

id | menu_name| Parent | Sort
0 |clan | 0| 5
1| sone|0|2

unsw,

Ich hoffe dir ist das Schema klar wenn nicht einfach. Fragen und ich werd versuchen dir das zu Erklären.

Mfg Splasch

 

[Sturmrider]

Danke für die Rückmeldung. Ich weiß, dass man normalerweise parentId verwendet, jedoch ist childId eben so richtig, da es vom Betrachtungsstandpunkt abhängig ist, jedoch prinzipiell das gleiche meint (zumindest bin ich so letztens mit einem Freund der im 5.Semester Wirtschaftsinformatik studiert und seinen Bachelor macht, verblieben)
Deinen Vorschlag habe habe ich ursprünglich genau so umgesetzt gehabt, ihn jedoch verworfen, da er einige unnötige Query´s voraussetzt
Ich kann nur jedem empfehlen sich UNBEDINGT einmal das Nested-Set-Modell, dass Chainy Vorgeschlagen hat anzuschauen Das ist einfach super genial und hat eine sehr gute Performance (es kommt deinem Vorschlag mit den positions [sort] übrigens nahe, ist in der Handhabung jedoch um einiges leichter und eleganter ^^)
Trotzdem danke

EDIT: Wobei ich mir nicht ganz sicher bin dich richtig verstanden zu haben, denn dein Schemata lässt ehrlich gesagt etwas zu wünschen übrig...

 

[splasch]

Also unötige querys were mir dabei noch net aufgefallen. Ich hab das in einem Onlineshop von mir so gemacht und der läuft performecs mässig einbahnfrei.

1 Sql befehl reicht zum Abfragen aus welche querys solln da unötig sein?

Ich kann nur jedem empfehlen sich UNBEDINGT einmal das Nested-Set-Modell, dass Chainy Vorgeschlagen hat anzuschauen Das ist einfach super genial und hat eine sehr gute Performance (es kommt deinem Vorschlag mit den positions [sort] übrigens nahe, ist in der Handhabung jedoch um einiges leichter und eleganter )

Also ich hab mir mal das Nested-Set-Modell angeschaut bwz. durch gelesen.
Die Handhabung ist weit aus komplizierter und keines wegs einfach.
Zur Performec ist zu sagen das bei Änderungen viel langsamer werden muß als jedes andere system. Schon allen weil immer alle Datensätze in der Tabelle umgeschrieben werden müssen.
Und die lese Performenc halt ich für ein Gerücht. Lieg rein an dem wie der Sql befehl gestaltet bzw geschrieben wird. (ORDER BY ist immer schneller als nur ein Select mit Where)
Im ganzen würd ich von so einen System abraten.Wenn ein Schreibfehler bassiert ist die ganze Baumstruktur zerstört.

Stell dir vor der Server stürzt während einer Änderung ab und speichert nur die hälfte aller Änderungen.
Die Seite würde erst dann wieder laufen wenn ein Admin in der lage war den fehler zu korregieren.
Mir fallen da noch so viele etliche Nachteile ein.So das ich es nicht weiter Empfehlen könnte.

Sorry aber Genial ist was anderes!

Mfg Splasch

 

[chainy]

Also ich hab mir mal das Nested-Set-Modell angeschaut bwz. durch gelesen.
Die Handhabung ist weit aus komplizierter und keines wegs einfach.

Dann scheinst du das Modell nicht verstanden zu haben..

Zur Performec ist zu sagen das bei Änderungen viel langsamer werden muß als jedes andere system.
Schon allen weil immer alle Datensätze in der Tabelle umgeschrieben werden müssen.
Und die lese Performenc halt ich für ein Gerücht.
Lieg rein an dem wie der Sql befehl gestaltet bzw geschrieben wird. (ORDER BY ist immer schneller als nur ein Select mit Where)

Zur Info, es heisst "Performance" - Wieso ist das Nested-Set-Modell bei Änderungen viel langsamer?
Nur weil bei Änderungen an mehreren Datensätzen die left und right Werte angepasst werden müssen?
Sorry, aber das ist je nach Änderungsgrad mit zwei SQL-Befehlen erledigt.
Sei dir sicher, dass die Performance beim Lesen weitaus schneller ist, als bei der verwendeten Technik im "Menusystem mit PHP und MySQL" - Tutorial

Im ganzen würd ich von so einen System abraten.Wenn ein Schreibfehler bassiert ist die ganze Baumstruktur zerstört.
Stell dir vor der Server stürzt während einer Änderung ab und speichert nur die hälfte aller Änderungen.
Die Seite würde erst dann wieder laufen wenn ein Admin in der lage war den fehler zu korregieren.

Wenn du sauber programmierst und das solltest, egal auf welchem Fundament dein Baum aufbaut, dann wird dir auch kein "Schreibfehler" passieren.
Stell dir vor, bei deiner Technik stürzt der Server ab - dein Baum würde ebenso fehlerhafte Daten aufweisen. Also ist dein Argument nur von den Haaren herbeigezogen und fällt somit nicht ins Gewicht.

Mir fallen da noch so viele etliche Nachteile ein.

Na, dann lass mal hören, ich bin gespannt..