Hierarchical Data Models: Adjazenzliste vs. Nested Sets

Question

Ich habe einen Produktkatalog. Jede Kategorie besteht aus unterschiedlicher Zahl (in tief) der Unterkategorien. Die Anzahl der Ebenen (tief) ist unbekannt, aber ich ganz sicher, dass es nicht von 5,6 Niveaus überschreiten wird. Die Datenänderungen sind viel seltener dann liest.

Die Frage ist: welche Art von hierarchischen Datenmodell ist besser geeignet für eine solche Situation. Das Projekt basiert auf Django Framework und es ist Eigentümlichkeiten (admin i-Gesicht, Modelle Handhabung ...) sollten berücksichtigt werden.

Vielen Dank!

Answer 1

Nested sets sind besser für die Leistung, wenn Sie nicht häufige Updates oder hierarchische Ordnung brauchen.

Wenn Sie eine Baum-Updates oder hierarchische Ordnung brauchen, ist es besser parent-child Datenmodell zu verwenden.

Es ist leicht in Oracle und SQL Server 2005+ konstruiert, und nicht so leicht (aber immer noch möglich) in MySQL.

Answer 2

würde ich den Modified Preorder Baum-Traversal-Algorithmus verwenden, MPTT, für diese Art von hierarchischen Daten. Dies ermöglicht eine große Leistung auf den Baum durchquert und Kinder zu finden, wenn Sie nicht ein bisschen eine Strafe auf Änderungen an der Struktur ausmacht.

Zum Glück Django hat eine große Bibliothek für diesen django-MPTT . Ich habe dies in einer Reihe von Projekten mit großem Erfolg eingesetzt. Es gibt auch django-treebeard , die mehrere alternative Algorithmen bietet, aber ich habe nicht verwendet es (und es ist nicht so populär wie MPTT scheint sowieso).

Answer 3

Nach diesem Artikel:

http://explainextended.com/ 2009/09/24 / adjacency-list-vs-nested-sets-postgresql / http://explainextended.com/2009/09 / 29 / adjacency-list-vs-nested-sets-mysql /

„MySQL ist das einzige System der großen vier (MySQL, Oracle, SQL Server, PostgreSQL), für die die verschachtelte Sätze Modell ordentliche Leistung zeigt und kann auf die gespeicherten hierarchischen Daten in Betracht gezogen werden.“

Answer 4

http://www.sqlsummit.com/AdjacencyList.htm

Answer 5

Die Adjazenzliste ist viel einfacher zu pflegen und verschachtelte Sätze viel schneller abgefragt werden.

Das Problem war immer, dass auf Nested Sets eine Adjazenzliste Umwandlung Art und Weise zu lange dank eine wirklich böse „Push-Stack“ -Verfahren genommen hat, die mit RBAR geladen wird. So können die Leute tun einige wirklich schwierige Wartung in Nested Sets am Ende oder nicht mit ihnen.

Jetzt können Sie Ihren Kuchen haben und ihn auch essen! Sie können nodesin weniger als 4 Sekunden auf 100.000 die Umwandlung zu tun und auf eine Million Zeilen in weniger als einer Minute! Alles in T-SQL, übrigens! Bitte beachten Sie die folgenden Artikel.

Hierarchies auf Steroiden # 1: Konvertieren einer Adjazenzliste zu Nested Sets

Hierarchies auf Steroiden # 2: Ein Ersatz für Nested Sets Berechnungen