Baumstrukturen in einem RDBMS

Baumstrukturen in einem RDBMS (8 Beiträge, 135 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

^ Forum Programmierung #995685
	Baumstrukturen in einem RDBMS

Psychopath

21.08.2003, 21:08:38

Hallo,

Altbekanntes Problem: Man moechte eine Baumstruktur (Kategorien und Unterkategorien, ein Diskussionsforum, einen Verzeichnisbaum - was auch immer) moeglichst praktisch in einem RDBMS abbilden. Einiges habe auch schon gegoogled und gelesen, trotzdem noch fragen.

Im grossen und ganzen scheint es zwei Ansaetze zu geben:

Speichern mit parentID: D.h. jeder Eintrag hat eine eindeutige ID und weiters ein Attribut parentID, das auf die ID des uebergeordnetes Eintrages verweist. Eine Abfrage, in die richtige Reihenfolge wird das ganze dann mit der verwendeten Programmiersprache gebracht (Alternative dazu waere Rekursion, d.h. fuer jeden Eintrag eine eigene Abfrage => langsam). Beispiel: Threadbasiertes Forum mit PHP und MySQL.
Vorteile:
- Einfache, auch fuer Nicht-Informatiker zu ueberblickende DB-Struktur.
- Einfuegen von neuen Eintraegen schnell und einfach mit einer Anfrage.
Nachteile:
- Braucht angeblich (lt. Google) relativ viel Speicher in der Programmiersprache.
- Einwand von mir: Wieso sollte ich als Programmierer die ganze Sortierarbeit machen, die doch die RDBMS-Entwickler sicher viel besser koenn(t)en?
Nested Sets: Dabei wird fuer jeden Eintrag left und right gespeichert. (Informatiker und aehnliche werden diese Baeume wohl gut kennen und verstehen, ich tu's nicht.). Beispiel: Das 'Nested Sets' Modell - Bäume mit SQL.
Vorteil:
- Eine einfache Abfrage und das RDBMS liefert einem gleich das, was man haben will.
Nachteile:
- Fuer Laien doch schwieriger zu verstehen (d.h. es koennen auch leichter Fehler passieren..)
- Einfuegen von neuen Eintraegen relativ aufwendig und nicht wirklich performant.

So weit so gut. Jetzt frage ich mich aber, ob man es mit einer ggf. bisschen erweiterten Methode 1 nicht auch schaffen koennte, die Daten mehr oder weniger so vom RDBMS zu bekommen, wie man sie haben will: Zusaetzlich zu ID und parentID wird ein Attribut level eingefuehrt. Da drin steht einfach, "wie tief eingerueckt" der Eintrag ist. (Da sehe ich das erste Problem: Redundanz. Oder war es Nicht-Normalisierung?)
Das zweite Problem: Ich weiss dann schon nicht weiter... - aber ich frage mich halt, ob das nicht irgendwie moeglich waere

Danke sehr fuer's Lesen...!
Gruss,
Psycho, der dafuer ist, dass der

Smiley (auch) mit :-? funktioniert. Waere doch passender. Wieso denn ein froehlich dreinschauender Mund, wenn man verzweifelt-ratlos ist?
Psycho@Home
--
The only antidote to mental suffering is physical pain. -- Karl Marx

Was verstehst Du an den Nested Sets nicht?

Weil, ganz ehrlich, es ist für derartige Tabellen in denen SEHR viel gelesen und SEHR wenig geschrieben wird die beste Lösung.

________________________________________________________________________
Der einfachste Weg einer Plagiatsklage aus dem Weg zu gehen ist, bei so vielen Quellen zu klauen, dass man es nicht mehr auf eine einzige zurückführen kann.

Naja, ich muesste mich einfach mehr damit beschaeftigen, mit den Nested Sets. Tu ich gern - nur nicht, wenn man mir morgen sagt, dass es anders viel einfacher und schneller auch noch geht

Also ist mein.. ehm.. "Ansatz" mit parentid und level wohl nichts, richtig?

Danke..!
Psycho@Home
--
The only antidote to mental suffering is physical pain. -- Karl Marx

ein Diskussionsforum, einen Verzeichnisbaum - was auch immer

Ich würde mal behaupten, das genau diese Frage durchaus nicht so nebensächlich ist; ein Verzeichnisbaum ist nur ein Baum, ein Forum eher ein ganzer Wald.

Die Nested-Set Methode schaut wirklich hochinteressant aus, muß ich sagen. Vollkommen verstanden hab ichs zwar beim ersten überfliegen auch noch nicht, aber Beispielquerys sind für alle wesentlichen Operationen vorhanden und schauen alle recht einfach aus.

Zusaetzlich zu ID und parentID wird ein Attribut level eingefuehrt.

Könnten es nicht auch 2 zusätzliche Attribute sein; eins nennen wir left und das andere right?

Da sehe ich das erste Problem: Redundanz.

Darum wird bei den nested-sets die 'parentID' auch weggelassen, denn die alleine würde ja die Baumstruktur festlegen; aber eine gewisse Art Redundanz bleibt trotzdem noch, schließlich wird die Baumstruktur nun durch 2 Werte pro Knoten definiert, obwohl einer (parentID) ja reichen würde.

Aber diese Redundanz ist in dem Fall eben eher Nebensache, zumindest wenn man von z.B. 90% Lesezugriffe ausgeht; das ist der Preis dafür, daß wir den ganzen Baum fix-fertig sortiert und mit 'level' Angabe mit einer einzigen Query ermitteln können. Außerdem müssen sowieso besondere Vorkehrungen getroffen werden, um die Konsistenz der DB sicherzustellen.

Insoferne könnte man in einer Test&Experimentierphase ja auch die parentID zusätzlich im Datensatz lassen; dann wären die nested-sets eigentlich eine mögliche Umsetzung Deines Ansatzes, nämlich zusätzliche Attribute einführen, um den ganzen Baum in einem Rutsch abfragen zu können!

Einfuegen von neuen Eintraegen relativ aufwendig und nicht wirklich performant.

Das wird sicher nur dann zum Problem, wenn wenige Lesezugriffe auf eine Einfügeoperation kommen, denk ich.

Wenn das Einfügen von Einträgen zum Performance-Problem wird, ließe sich dem vermutlich durch eine Art 'Einfügen auf Vorrat' kompensieren; der Aufwand mehrere Knoten einzufügen sollte nicht wesentlich höher sein als der für einen Knoten.

Außerdem könnte man die Strukturdaten (rootID, nodeID, left, right) von den eigentlichen Nutzdaten (nodeID, payload) trennen und die ersteren in einer Tabelle ablegen, die im RAM gehalten wird, womit auch der Update-Aufwand gewaltig reduziert wird. Speichert man zusätzlich mit den Nutzdaten auch noch die parentID ab, dann kann diese Strukturdaten-Tabelle bei jedem Neustart frisch erzeugt werden. So hat man dann das Beste aus beiden Welten!

lg
mIstA

Hi!

Danke fuer Eure Antworten. Ich werde mich wohl doch noch mit den Nested Sets auseinandersetzen, sprich versuchen, sie wirklich zu verstehen.
Mit einem ordentlichen DBMS (Juhuu - gestern habe ich entdeckt, dass es jetzt einen - zwar nicht ganz aktuellen - native Windows-Port von PostgreSQL gibt!

) macht, sollte die Performance auch halbwegs passen (statt 3-5 einzelne Queries abzusetzen, eine stored procedure)

Gruss,
Psycho
Psycho@Home
--
The only antidote to mental suffering is physical pain. -- Karl Marx

So, jetzt habe ich aber ein neues Problem.
Ich habe ja die Nested Sets verwendet - also kein Attribut àla parentid. Nur - wie komme ich jetzt an die parentid, wenn ich eine id habe?

Psycho@Home
--
The only antidote to mental suffering is physical pain. -- Karl Marx

^ Forum Programmierung #998485
	Re(3): Baumstrukturen in einem RDBMS

Psychopath

24.08.2003, 01:48:14

Also bisher habe ich das:
SELECT p1.id FROM posts AS p1, posts AS p2 WHERE p2.lft > p1.lft AND p2.lft < p1.rgt AND p2.id = $id ORDER BY p1.rgt LIMIT 1

Wobei $id die ID des Eintrages ist, dessen parentid man haben will.
Ich habe es mit einigen Eintraegen ueberprueft, bin mir aber absolut nicht sicher, ob das so passt

Psycho@Home
--
The only antidote to mental suffering is physical pain. -- Karl Marx

Hmm

ja schaut brauchbar aus!

Wenn ich das jetzt korrekt verstehe, wählst zuerst alle Vorfahren des fraglichen Eintrags aus; von diesen müßte derjenige der direkte 'Elter' sein, der den größten 'lft' oder eben den kleinsten 'rgt' Wert hat - sollte passen! (Zumindest wenn sich das 'LIMIT' nicht auf eventuelle interne Optimierungen der Abfrage auswirkt.)

Wie schon gesagt, wennst in der Testphase die 'parentID' in den Datensätzen drin läßt, kannst in solchen Fällen auf Nummer sicher gehen; also die fargliche Abfrage bei einem 'ausgewachsenen Baum' automatisiert testen!

lg
mIstA

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung