Bäume und Datenbanken
-
Habe mir das heute mal wieder überlegt, wie sich hierarchische Strukturen in einer DB unterbringen lassen.
Es gibt 2 Ansätze, einmal nested sets, und jeweils die Parentid pro Datensatz mit zu geben:
Nested Sets:
http://phpperformance.de/nested-sets-hierarchische-strukturen-und-baeume-in-mysql/Parentid Ansatz:
http://scriptfreaks.de/stuff/mysql_tree.txtFrage mich nun, was ihr wieso und wann für besser haltet.
Ich finde beide Ansätze nicht schlecht, gerade der ParentID Ansatz ist wohl unabhängig ob man ihn mag oder nicht, häufig vorzufinden.phlox
-
Dann solltest du vllt dazuschreiben für was du das verwenden willst, wieviele Knoten, Häufigkeit Inserts vs Updates vs Selects, welches DBMS, Möglichkeit Stored Procs zu verwenden ...
-
Die Nested Sets Variante finde ich sehr unübersichtlich. Würde ich nicht verwenden, es sei denn es geht wirklich nicht anders (weil alles andere zu langsam ist oder was auch immer).
Ich schätze da würde ich noch eher versuchen mit Dotted Strings zu arbeiten statt mit so Nested Sets...
-
witte schrieb:
Dann solltest du vllt dazuschreiben für was du das verwenden willst, wieviele Knoten, Häufigkeit Inserts vs Updates vs Selects, welches DBMS, Möglichkeit Stored Procs zu verwenden ...
Zur Zeit habe ich da keinen Anwendungsfall, mich würde interessieren wie ihr das bisher löst, was es evtl. an Alternativen gibt.
DBMS könnte MySQL sein, evtl. auch ein anderes.
-
mich würde interessieren wie ihr das bisher löst
Gottseidank brauchen wir nur an einer Stelle einen Baum, und dort verwenden wir einfach Parent IDs.
was es evtl. an Alternativen gibt.
Wie schon erwähnt: Dotted Strings als Keys verwenden:
SELECT * FROM [Artikel] WHERE [ID] LIKE 'Lebensmittel.Obst.%' ORDER BY [ID](Man beachte dass LIKE mit ausschliesslich rechtsseitiger Trunkierung üblicherweise über einen Index optimiert werden kann, und daher üblicherweise recht flott ist. Kann das verwendete DBMS diese Optimierung nicht, kann man Dotted Strings IMO vergessen.)
Das Prinzip ist sogar das gleiche wie mit den "Nestes Sets", nur mit Strings statt Integer-Ranges. Wodurch das Erzeugen von "Zwischenwerten" beliebig möglich wird, und bestehende Werte nicht dauernd angepasst werden müsssen.
+ einfach zu verstehen (daher weniger (programmier-)fehleranfällig)
+ übersichtlich, intuitiv
+ relativ schnell
+ schneller zu editieren, da bestehende Keys bei INSERT nicht angepasst werden müssen
- vermutlich nicht ganz so schnell wie Integer-Ranges
- braucht mehr Platz als Integer-Ranges
- sehr tiefe Bäume lassen sich nicht darstellen (irgendwann ist das Limit des DBMS erreicht - Maximale Länge eines Strings der in einem Index vorkommen kann)Schreib mir was du davon hältst, würde mich interessieren.
-
Ich denke das NestedSets immer dann das beste ist, wenn man nicht viel Veränderungen im Baum hat, oder den Baum dann jeweils im ganzen einspielen kann.
Mein erster Link verlinkt hierauf:
http://www.klempert.de/nested_sets/artikel/Da gibts auch was zur Performance, was aber evtl. auch von vornerein die Nested Sets bevorzugt (z.b. in dem die Tests so gewählt werden).
Ausserdem werden für ParentIDs nicht LEFT JOINs benutzt, wie mein 2. Link zu dem Thema rät (habt ihr aber sicher schon gelesen ;)).
Allerdings wird dann ab einer gewissen Tiefe eine Tabelle zurückgegeben, welche auf den "unbesetzen" Ebenen NULL enthält. Was ich unschön finde, aber auch ok ist.Gerade bei dieser Diskrepanz (rekursive/iterative SELECTS vs. LEFT JOIN bei der Performance) würde mich interessieren, was nun die Praxiserfahrung bevorzugt, und wie die Performance von ParentID wirklich ist.
DottetStrings ist für mich nur bei kleinen Bäumen eine wirkliche Alternative.
Problem bei vielen Bäumen ist jedoch, das man ihre Größe nicht wirklich einschränken kann, d.h. der Baum wird dann irgendwann einfach zu groß.
Auch die Speicherbelegung ist hier alles andere als optimal.phlox
