SQL Kategorien: Rekursion vs. Nested Sets

[Eagle-PsyX-]

Hi,

wir alle machen ja hoffentlich im Laufe der Zeit fortschritte und auch finde endlich etwas wieder Zeit einen Punkt in meinem CMS zu ändern, dass mich schon sehr lange nervt:
Ein Kategorien-System.

Bis dato gab es nur eine Möglichkeit eine "Kategorie" und eine "Unterkategorie" zu definieren, wie hier damals angedeutet.

Jetzt will ich ein System mit unendlich vielen Verschachtelung umsetzen und mir stellts sich jetzt die Kernfrage, ob ich auf die klassische Rekursion (mit Partent ID etc.) setzen soll oder auf das mir moderner scheinende Nested Sets?

Bei beidem liegen durch diverse Seiten und Blogs genügend Query-Befehle vor, so dass ich hier nicht um die Aufwendigkeit der Queries sprechen will.

Sondern was ist eurere Ansicht nach leistungspotenter? Hat jemand damit schon Erfahrungen gemacht? Bei beiden gilt natürlich die richtige Vorraussetzung (Indizen etc.).

Ein Leistungsvorteil sollte es sein, das bei mehr und mehr Verschachtelungen der Leistungsverbrauch bei Rekurion linear sein sollte, während der von Nested Sets eher logarithmisch verlaufen sollte (beim Abfragen aller Kategorien inkl. Unterkategorien). Da beim Letzten, immer nur eine Query abgeschickt wird.

Hilfreiche Links für alle Nested Sets Interessierten:
http://www.klempert.de/nested_sets/
http://mjsarfatti.com/sandbox/nestedSortable/

 

[nein23]

Wie bei jeder implementierung ist die wahl der besten bzw. potentesten heuristic abhängig vom anwendungsfall. von welcher dimension von datenbank sprechen wir bei deinem projekt?

 

[Eagle-PsyX-]

Da es sich um das technisches CMS handelt ist es schwer eine Zahl zu nennen, da dies von Projekt zu Projekt varieren wird.

 

[ice-breaker]

Sondern was ist eurere Ansicht nach leistungspotenter? Hat jemand damit schon Erfahrungen gemacht? Bei beiden gilt natürlich die richtige Vorraussetzung (Indizen etc.).

Das ist eigentlich ganz einfach

Was passiert in beiden Modellen wenn du eine Kategorienübersicht mit 10 Verschachtelungen laden willst? Bei dem Parent-Modell sind es mindestens 10 Abfragen und nochmal mehr Logik um die Daten wieder zusammenzusetzen oder für jeden Ast eine Abfrage. Bei NestedSets ist es eine Abfrage. Ein effizienter von Indexen nutzbarer Range-Query, das war es schon.

Komplizierter wird es wenn es um die Bearbeitung der Kategorien geht, bzw. neue hinzufügen/löschen/verschieben, die Operation ist im Parent-Modell natürlich sehr einfach, nur irgendwo eine ParentID modifzieren und fertig. Im NestedSet-Modell hingegegen müssen dann natürlich die ganzen link-rechts-Zeiger eines ganzen Astes modifiziert werden, sehr performancelastig. Man kann dort jedoch auch die "Gap-Optimization" einsetzen, statt die left-right-Nummern direkt ohne Lücken zu vergeben, lässt man zwischen jedem Knoten Lücken und kann so auch einfach mal einen Knoten dazwischenschieben ohne den ganzen Baum modifizieren zu müssen, sehr effizient, benötigt aber mehr Programmlogik.


Sind deine Bäume (Kategorien) read-only bzw. read-most dann hast du mit dem NestedSet-Modell eine der effizientesten Möglichkeiten gefunden, muss aber dauerhaft der Baum geändert werden (Mailingliste z.B.) ist das pure NestedSet-Modell durch die sehr kostspieligen Modifikationen sicherlich fehl am Platz, kann mit einer guten Gap-Optimierung aber auch eine gute Wahl werden.
Es hängt eben stark von den Anforderungen ab, wie immer gibt es in der DB-Optimierung keine feste Aussage, es ist komplett von dem Nutzungsverhalten abhängig.


Als Tipp: Denk daran dass im NestedSet-Modell du mehrere Querys brauchst um eine Modifikation vollständig durchzuführen, solltest du 2 Scripte haben die gleichzeitig den Baum ohne Synchronisierung modifizieren, so hast du dir diesen sehr schnell zerschossen, also setze auf Transaktionen oder irgendeine Art eines Locks.

 

[Eagle-PsyX-]

Danke für die Antwort.
Den erster Abschnitt war etwas unnötig, da mir der Unterschied der beiden Modelle bekannt ist :-)

Ich sehe gerade erst jetzt, dass auf der verlinkten Seite oben im Nachhinein ein Benchmark auch dargestellt wurde. Das sagt eigentlich schon alles aus :-)

Das Pfad-Modell ist auch recht interessant...aber zu sehr eingeschränkt, schade.

 

[AlbertLast]

ich wirde wissen wollen welche rdbms benutzt werden soll,
nested set sind in mein augen das ältere verfahren?
man muss auch kein nested benutzen so lange man kein mysql benutzt
glaube ich

 

[Eagle-PsyX-]

Benutze jedoch MySQL :-)

 

[AlbertLast]

naja dann stellt sich die frage garnicht weil du keine wahl hast
und nested set benutzen musst.