Baumstrukturen

Hi,



ich habe hier ein Problem, mit der DB-Abfrage einer Baumstruktur.

Mein Tabellenaufbau sieht so aus, dass ich eine inkrementelle ID als
Primärschlüssel verwende. Diese als Eltern-Id bei untergeordneten Elementen
verwende.



Der Abruf und Aufbau des Baumes ist im Allgemeinen kein Problem. Ich moechte
jedoch die Elemente verschiebbar halten, und genau hier faengt mein Problem
an, da die ID des Eltern Elementes groesser sein kann, als die des Kindes.
Wie loese ich das am besten?



Beispiel bei einer Sortierung nach parent_id:

Id | parent_id

1 0

2 0

5 1

3 4

6 5

4 5



Mein Problem ist einfach, das im obigen Beispiel id 3 als Elternteil ID 3
hat, welche zu dem Zeitpunkt noch nicht bekannt ist. Ich koennte bei der
UPDATE Anweisung eine neue ID vergeben, muesste diese jedoch dann wieder bei
allen untergeordneten Elementen als parent_id ebenfalls aendern, daher
wuerde ich darauf gerne verzichten.



Gibt es eine Sortiermoeglichkeit per SQL, die ich gerade nicht sehe? Oder
bleibt mir nichts anderes ueber, als das spaeter zu sortieren bzw. die
Datenbank mehrmals zu bemuehen?



Gruss Andreas

Re: Baumstrukturen

Hi Andreas

Andreas wrote:
> ich habe hier ein Problem, mit der DB-Abfrage einer Baumstruktur.
> Mein Tabellenaufbau sieht so aus, dass ich eine inkrementelle ID als
> Primärschlüssel verwende. Diese als Eltern-Id bei untergeordneten Elementen
> verwende.

Wenn du das so machen willst, musst du rekusive Funktionen zum Aufbau
des Baumes verwenden. Deine Idee mit der Sortierung ist nett,
funktioniert aber, wie du erkanntest, nicht.

Verwende stattdessen Nested Sets. Die Suchmaschine deiner Wahl hilft dir
weiter.

HTH, Johannes

Re: Baumstrukturen

> Verwende stattdessen Nested Sets. Die Suchmaschine deiner Wahl hilft dir
> weiter.

Dummerweise lieferte sie u.a. auch das als Ergebnis zurueck, was fuer mich
ein KO Kriterium war, das auf diesem Wege zu loesen. Sprich die UPDATE und
DELETE Anweisungen werden recht teuer, daher mein Versuch das auf diesem
Wege zu realisieren.

Gruss Andreas

Re: Baumstrukturen

Andreas wrote:
>>Verwende stattdessen Nested Sets. Die Suchmaschine deiner Wahl hilft dir
>>weiter.
>
> die UPDATE und
> DELETE Anweisungen werden recht teuer, daher mein Versuch das auf diesem
> Wege zu realisieren.

Die Frage ist bei Bäumen immer: Wie wird er verwendet? Wird
hauptsächlich geschrieben, oder hauptsächlich gelesen? Ich kenne nur
ganz wenige Fälle, in denen tatsächlich etwa genauso oft geschrieben wie
gelesen wird. Öfter schreiben als lesen, habe ich bisher noch nirgendwo
gesehen.

Je mehr Ebenen du hast, desto effektiver wird das Nested Set, weil du
für eine Löschung zwar ein DELETE und zwei UPDATEs brauchst (da ist ein
UPDATE mehr, als in deinem Modell), aber beim Selektieren immer nur
genau einen JOIN und keine Rekursion.

Einzig das Verschieben von Knoten ist wirklich relativ teuer, weil du
hier mindestens 4 UPDATES brauchst, in deinem Modell aber evtl. mit nur
einem UPDATE auskommst (aber auch nicht immmer).

Kurz und gut: Das Nested Set ist gar nicht so teuer, wie allgemein
angenommen. Ein richtig gesetzter Indec wirkt hier wahre Wunder. Meine
Erfahrung ist: Wer also mindestens so viel liest, wie schreibt, sollte
zum Nested Set greifen. Es sei denn, es spielen noch andere
Randbedingungen mit rein, die dir das verbieten.


Grüße,
Dominik
--
Norbert Melzer in d.c.d.mysql:
F: Wie verstehe ich diese FAQ am besten?
A: Studieren Sie Datanbank-Design und lesen Sie anschliessend alles nochmal

Re: Baumstrukturen

Johannes Vogel schrieb:
> Verwende stattdessen Nested Sets. Die Suchmaschine deiner Wahl hilft dir
> weiter.

Ich spiel mal Suchmaschine und empfehl

http://www.develnet.org/36.html

Is meiner Meinung nach eine der besten (wenn nicht die beste) Anleitung
zu dem Thema, und vor allem auf Deutsch :)

Das NestedSet Modell is zwar nicht einfach zu verstehen (oder ich war zu
blöd), aber irgendwann machts klick, und ab da isses einfacher/flexibler
als z.B. mit Pfaden oder ParentIds :)


MfG
A.Falk

Re: Baumstrukturen

A.Falk wrote:
>
> Das NestedSet Modell is zwar nicht einfach zu verstehen (oder ich war zu
> blöd), aber irgendwann machts klick, und ab da isses einfacher/flexibler
> als z.B. mit Pfaden oder ParentIds :)

Ich kann dich beruhigen. Es ist tatsächlich erst mal nicht ohne weiteres
zu verstehen, wenn man nicht gerade Mathematik und Datenbanktheorie
studiert hat ;)


Grüße,
Dominik
--
Norbert Melzer in d.c.d.mysql:
F: Wie verstehe ich diese FAQ am besten?
A: Studieren Sie Datanbank-Design und lesen Sie anschliessend alles nochmal