Speichern von zusammengesetzten Mustern (hierarchischen Daten) in der Datenbank

Question

Welche Best Practices zum Speichern von zusammengesetzten Mustern in einer relationalen Datenbank?

Wir verwenden Modified Preorder Tree Traversal. Dies ist sehr schnell, um den gesamten Baum zu erstellen, aber es ist sehr langsam, neue Knoten einzufügen oder zu löschen (alle linken und rechten Werte müssen angepasst werden). Auch das Abfragen der Kinder eines Knotens ist nicht einfach und sehr langsam.

Eine andere Sache, die wir bemerkt haben, ist, dass Sie wirklich sicherstellen müssen, dass der Baum nicht unordentlich wird. Sie benötigen Transaktionssperren, sonst können die linken und rechten Werte beschädigt werden, und das Korrigieren einer beschädigten linken rechten Struktur ist keine leichte Aufgabe.

Es funktioniert sehr gut, aber die Modified Preorder Tree Traversal, aber ich frage mich, ob es bessere Alternativen gibt.

Answer 1

Während alle Nachkommen einer Reihe mit MPTT schnell gefunden werden, kann das Finden aller Kinder langsam sein. Allerdings sollten Sie das beheben können, indem Sie Ihrer Tabelle ein parent_id-Feld hinzufügen, das (ja, redundant) das Elternelement der Zeile aufzeichnet. Dann wird die Suche:

SELECT * 
FROM tbl 
WHERE parent_id = z 

Ja, parent_id redundante Informationen enthält, die möglicherweise Ihren Tisch Denormalisierung - aber da jede insert/update/delete bereits erfordert globale Änderungen, halten parent_id up-to-date ist nicht viel Extra bezahlen. Sie könnten alternativ ein level Feld verwenden, das den vertikalen Level der Zeile aufzeichnet, obwohl das tatsächlich mehr ist, das sich wahrscheinlich unter bestimmten Arten von Transformationen ändert (z. B. Verschieben eines Teilbaums an einen anderen Punkt im Baum).

Die gute alte link-to-Eltern-Darstellung (dh nur parent_id und keine left_pos oder right_pos), ist natürlich schneller für insert/update-hohe Arbeitsbelastung, aber die nur Abfragen effizient sind beantworten kann „Finde die Eltern von X "und" Finde die Kinder von X. " Die meisten Workloads beinhalten viel mehr Lesen als Schreiben, also ist MPTT normalerweise schneller - aber vielleicht müssen Sie in Ihrem Fall das Verschieben ("Zurück") zu Link-zu-Eltern verschieben?

Answer 2

Die beste Möglichkeit, Hierakial-Daten in einer Datenbank zu speichern, die ich gehört habe, ist die Verwendung eines String-Attributs, wobei der Inhalt die Liste der durch Trennzeichen getrennten Eltern ist, sagen wir Doppelpunkte.