MySQL + Baumstruktur

[Nocta]

Hey.
Ich habe eine Frage bezüglich Baumstrukturen in Datenbanken. Dass es sich um MySQL handelt, spielt denke ich mal keine große Rolle.

Gegeben ist beispielweise folgende Datenstruktur (nur das wichtige):

Code: Alles auswählen

id	parent
--------------
1	0
2	1
3	2
4	2
5	1
6	0

Anders/grafisch dargestellt, nur noch mal zur Verdeutlichung:

Code: Alles auswählen

1 =>	2 => 	3
  ..	  =>	 4
  =>	5
6 

Frage: Wenn ich jetzt 3 oder 4 als Knoten habe, aber auch alle übergeordneten Knoten (also 2, 1) haben will (zum Beispiel für eine Navigation), wie kriege ich die am besten/performantesten raus?
Ich könnte natürlich jetzt so oft eine SQL Abfrage an die Datenbank schicken, bis ich bei 0 (also der obersten Ebene) angekommen bin, aber das würde ja bedeuten, dass ich immer n Abfragen brauche, um alle übergeordneten Knoten rauszukriegen, wobei n die Ebene ist, auf der ich mich befinde.
Auf das Beispiel bezogen: Ich befinde mich auf Knoten 3, über die Parent ID krieg ich raus, dass darüber der Knoten 2 is. Und dann muss ich den Knoten 2 abfragen, um rauszufinden, dass er 1 untergeordnet ist und dann wiederum 1 abzufragen, um rauszufinden, dass dieser keinem Knoten untergeordnet ist (0).
Aber so eine rekursive Angehensweise ist glaube ich nicht so performant.

[/me]

Ich habe eine Frage bezüglich Baumstrukturen in Datenbanken. Dass es sich um MySQL handelt, spielt denke ich mal keine große Rolle.

Schau dir mal Nested Sets an. Man muss es nur einmal verstehen, dann läuft's wie von selbst.

Eine gute Einstiegsseite: http://www.klempert.de/nested_sets/

[Nocta]

Danke für die Antwort
Und damit kann ich dann direkt die ganzen "Urgroßväter" bis zur obersten Ebene hin ermitteln?

Ich werd's mir dann morgen mal durchlesen.

[Hyperion]

Eine gute Einstiegsseite: http://www.klempert.de/nested_sets/

Interessante Sache - kannte ich noch nicht. Danek für den Link.

Wobei ich doch mal eines anmerken würde: Für eine Baumstruktur einer Navigation auf einer Webseite würde ich es mir einfach machen und einfach alle Zeilen einlesen. Das geht als Abfrage verdammt schnell und ich kann dann im Speicher eine geeignete Baumstruktur der Elemente aufbauen. Sollte also bei dem Anwendungsfall die Anzahl der Elemente im Baum stark begrenzt sein, so würde ich auf so eine simple Vorgehensweise zurückgreifen.

[Nocta]

Nested Sets kannte ich schon ansatzweise, habe es aber immer für etwas sehr viel abstrakteres gehalten. Aber ich denke mit einem konkreten Anwendungsfall sieht die Sache auch wieder anders aus.

Sicher kann man bei begrenzten Bäumen einfach auf die Performance sch*****, aber wenn's doch eine schöne, saubere Lösung gibt, nehm ich lieber die. Allein schon aus Prinzip

[Hyperion]

Sicher kann man bei begrenzten Bäumen einfach auf die Performance sch*****,

Die Performance sollte durchaus recht hoch sein - ich habe mir die Queries aus dem nested sets Artikel noch nicht genau angeguckt, aber simpler als eine simple select-Abfrage werden Sie nicht sein "Teuer" ist es da eher, die Struktur nachträglich aufzubauen - aber da das im Speicher abläuft, würde ich mir da bei kleinen Strukturen keine Sorgen machen.

aber wenn's doch eine schöne, saubere Lösung gibt, nehm ich lieber die. Allein schon aus Prinzip

Wobei das Einfügen von Knoten bei dieser Struktur teuer ist. Sollte das Lesen häufiger als das Schreiben vorkommen, lohnen sich somit nested sets. Man muss hier also vorher abwägen, was für die Anwendung entscheident ist Aber vom Prinzip ist es sicherlich interessant, mal so etwas zu realisieren!

[Nocta]

Die Performance sollte durchaus recht hoch sein

Ja, ich habe mich falsch ausgedrückt Ich meinte nur die Differenz zwischen der Performance von Nested Sets und dem Parent Modell. Also dass einem diese Differenz bei kleinen Bäumen nicht zu interessieren braucht, weil sie ohnehin fast nichts ausmacht.

ich habe mir die Queries aus dem nested sets Artikel noch nicht genau angeguckt, aber simpler als eine simple select-Abfrage werden Sie nicht sein

Sind sie auch nicht. Aber man braucht nur eine einzige Abfrage und das ist denke ich ein Vorteil gegenüber der Tatsache, dass man sonst immer n Abfragen, für jede Ebene eine, machen muss, um den "Pfad" zu ermitteln.

"Teuer" ist es da eher, die Struktur nachträglich aufzubauen - aber da das im Speicher abläuft, würde ich mir da bei kleinen Strukturen keine Sorgen machen.

Ja das hab ich auch gelesen. Aber bevor mein Rechner (oder ein beliebiger Server) da Probleme kriegt, müsste der Baum doch schon tausende Knoten haben, oder?

Sollte das Lesen häufiger als das Schreiben vorkommen, lohnen sich somit nested sets. Man muss hier also vorher abwägen, was für die Anwendung entscheident ist

Naja, Navigationen haben es wohl so an sich, dass man sie recht oft liest und eher selten erstellt

Außerdem könnte man ja bestimmt noch Teilbäume erstellen oder sowas, um nur gewisse zusammenhängende Bereiche voneinander abhängig zu machen, was die Performance beim Ändern erhöhen sollte, oder? Also so stell ich mir das zumindest vor.

[Hyperion]

Sind sie auch nicht. Aber man braucht nur eine einzige Abfrage und das ist denke ich ein Vorteil gegenüber der Tatsache, dass man sonst immer n Abfragen, für jede Ebene eine, machen muss, um den "Pfad" zu ermitteln.

Naja, ich habe bei meinen früheren Projekten die Baumstruktur innerhalb von Python aufgebaut! Deshalb brauchte ich auch nur eine SQL-Abfrage.

Desweiteren gibt es auch Möglichkeiten in SQL rekursive Abfragen zu erstellen (ok, ob das zum Standard gehört kann ich grad nicht sagen, aber ich habe da def. einmal was für Oracle gesehen...).

Ich fände es vor allem spannend, ob es innerhlab von SQLAlchemy eine Abstraktion für solch eine Baumstruktur gibt oder einen Aufsatz darauf. Denn das wäre dann wirklich komfortabel und man müßte sich darüber keine großen Dedanken mehr machen