Mysql
 sql >> Datenbank >  >> RDS >> Mysql

Was sind die bekannten Möglichkeiten, eine Baumstruktur in einer relationalen DB zu speichern?

Wie immer gilt:Die beste Lösung gibt es nicht. Jede Lösung macht verschiedene Dinge einfacher oder schwieriger. Die richtige Lösung für Sie hängt davon ab, welche Operation Sie am häufigsten durchführen werden.

Naiver Ansatz mit Eltern-ID:

Vorteile:

  • Einfach zu implementieren

  • Einfaches Verschieben eines großen Teilbaums zu einem anderen Elternteil

  • Insert ist billig

  • Erforderliche Felder, auf die direkt in SQL zugegriffen werden kann

Nachteile:

  • Das Abrufen eines ganzen Baums ist rekursiv und daher teuer

  • Alle Eltern zu finden ist auch teuer (SQL kennt keine Rekursionen...)

Modified Preorder Tree Traversal (Einsparung eines Start- und Endpunkts):

Vorteile:

  • Das Abrufen eines ganzen Baums ist einfach und kostengünstig

  • Es ist billig, alle Eltern zu finden

  • Erforderliche Felder, auf die direkt in SQL zugegriffen werden kann

  • Bonus:Sie speichern auch die Reihenfolge der untergeordneten Knoten innerhalb des übergeordneten Knotens

Nachteile:

  • Das Einfügen/Aktualisieren kann sehr teuer sein, da Sie möglicherweise viele Knoten aktualisieren müssen

Pfad in jedem Knoten speichern:

Vorteile:

  • Es ist billig, alle Eltern zu finden

  • Das Abrufen eines ganzen Baums ist billig

  • Einfügen ist billig

Nachteile:

  • Einen ganzen Baum zu bewegen ist teuer

  • Je nachdem, wie Sie den Pfad speichern, können Sie ihn nicht direkt in SQL bearbeiten, also müssen Sie ihn immer abrufen und parsen, wenn Sie ihn ändern möchten.

Abschlusstabelle

Vorteile:

  • Einfach zu implementieren

  • Es ist billig, alle Eltern zu finden

  • Einfügen ist billig

  • Das Abrufen ganzer Bäume ist billig

Nachteile:

  • Benötigt eine zusätzliche Tabelle

  • Nimmt im Vergleich zu anderen Ansätzen viel Platz ein

  • Das Verschieben eines Teilbaums ist teuer

Ich würde eines der letzten beiden bevorzugen, je nachdem, wie oft sich die Daten ändern.

Siehe auch:http://media.pragprog.com/titles/bksqla/trees. pdf