Optimiertes SQL für Baumstrukturen

Es hängt wirklich davon ab, wie Sie auf den Baum zugreifen.

Eine clevere Technik besteht darin, jedem Knoten eine String-ID zu geben, wobei die ID des übergeordneten Elements ein vorhersagbarer Teilstring des untergeordneten Elements ist. Zum Beispiel könnte das übergeordnete Element '01' sein, und das untergeordnete Element wäre '0100', '0101', '0102' usw. Auf diese Weise können Sie eine gesamte Unterstruktur gleichzeitig aus der Datenbank auswählen:

SELECT * FROM treedata WHERE id LIKE '0101%';

Da das Kriterium eine erste Teilzeichenfolge ist, würde ein Index für die ID-Spalte die Abfrage beschleunigen.

Von allen Möglichkeiten, einen Baum in einem RDMS zu speichern, sind Adjazenzlisten und geschachtelte Mengen am häufigsten. Verschachtelte Sätze sind für Lesevorgänge optimiert und können einen gesamten Baum in einer einzigen Abfrage abrufen. Adjazenzlisten sind für Schreibvorgänge optimiert und können in einer einfachen Abfrage hinzugefügt werden.

Bei Adjazenzlisten hat jeder Knoten a eine Spalte, die sich auf den übergeordneten Knoten oder den untergeordneten Knoten bezieht (andere Verknüpfungen sind möglich). Auf diese Weise können Sie die Hierarchie basierend auf übergeordneten untergeordneten Beziehungen aufbauen. Wenn Sie die Tiefe Ihres Baums nicht einschränken, können Sie leider nicht das ganze Objekt in einer Abfrage ziehen. Das Lesen ist normalerweise langsamer als das Aktualisieren.

Mit dem geschachtelten Satzmodell ist die Umkehrung wahr, das Lesen ist schnell und einfach, aber Aktualisierungen werden komplex, da das Nummerierungssystem verwaltet werden muss. Das verschachtelte Mengenmodell codiert sowohl die Abstammungsreihenfolge als auch die Sortierreihenfolge, indem alle Knoten unter Verwendung eines auf Vorbestellungen basierenden Nummerierungssystems aufgelistet werden.

Ich habe das geschachtelte Mengenmodell verwendet, und obwohl es für das Lesen einer großen Hierarchie komplex ist, lohnt es sich. Wenn Sie einige Übungen zum Herausziehen des Baums und zum Nummerieren der Knoten durchgeführt haben, sollten Sie den Dreh raus haben.

Meine Forschung zu dieser Methode begann in diesem Artikel: Verwalten von hierarchischen Daten in MySQL .

In dem Produkt, an dem ich arbeite, haben wir einige Baumstrukturen in SQL Server gespeichert und verwenden die oben erwähnte Technik, um die Hierarchie eines Knotens im Datensatz zu speichern. d.h.

tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)

Das Beibehalten der Hierarchie ist natürlich das knifflige und verwendet Auslöser. Das Generieren beim Einfügen/Löschen/Verschieben ist jedoch nie rekursiv, da die Hierarchie des übergeordneten oder untergeordneten Objekts alle erforderlichen Informationen enthält.

sie können alle Nachkommen von Knoten auf diese Weise erhalten:

SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'

Hier ist der Insert-Auslöser:

--Setup the top level if there is any
UPDATE T 
SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
FROM tblTreeNode AS T
    INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)

WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
    BEGIN
        --Update those items that we have enough information to update - parent has text in Hierarchy
        UPDATE CHILD 
        SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
        FROM tblTreeNode AS CHILD 
            INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
        WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
    END

und hier ist der Update-Auslöser:

--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
    BEGIN
        --Update the changed items to reflect their new parents
        UPDATE CHILD
        SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
        FROM tblTreeNode AS CHILD 
            INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
            LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID

        --Now update any sub items of the changed rows if any exist
        IF EXISTS (
                SELECT * 
                FROM tblTreeNode 
                    INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
            )
            UPDATE CHILD 
            SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
            FROM tblTreeNode AS CHILD 
                INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
                INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID

    END

noch ein Bit, eine Check-Einschränkung, um einen Zirkelverweis in Baumknoten zu verhindern:

ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))

Ich würde auch Auslöser empfehlen, um mehr als einen Stammknoten (null-übergeordneter Knoten) pro Baum zu verhindern und zu verhindern, dass verwandte Knoten zu unterschiedlichen TreeIDs gehören (diese sind jedoch etwas trivialer als die oben genannten).

Sie sollten für Ihren speziellen Fall prüfen, ob diese Lösung akzeptabel ist. Hoffe das hilft!

Celko schrieb dazu (2000):

http://www.dbmsmag.com/9603d06.html

http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

und andere Leute fragten:

Zusammenfügen anderer Tabellen in Oracle-Baumabfragen

So berechnen Sie die Summe der Werte in einem Baum mithilfe von SQL

Wie speichere ich Verzeichnis/Hierarchie/Baumstruktur in der Datenbank?

Leistung rekursiver gespeicherter Prozeduren in MYSQL zum Abrufen hierarchischer Daten

Was ist der effizienteste/eleganteste Weg, einen flachen Tisch in einen Baum zu parsen?

schließlich können Sie die Rails-Plugins "Acts_as_tree" (read-heavy) und "Acts_as_nested_set" (write-heavy) betrachten. Ich habe keine gute Verbindung, die sie miteinander vergleicht.

Es gibt mehrere gängige Arten von Abfragen gegen eine Hierarchie. Die meisten anderen Arten von Abfragen sind Abweichungen davon.

1. Finden Sie von einem Elternteil alle Kinder.

   ein. Bis zu einer bestimmten Tiefe Angesichts meines unmittelbaren Elternteils werden beispielsweise alle Kinder bis zu einer Tiefe von 1 meine Geschwister sein.

   b. Bis zum Ende des Baumes.

2. Finde von einem Kind alle Eltern.

   ein. Bis zu einer bestimmten Tiefe Zum Beispiel ist mein unmittelbarer Elternteil Eltern bis zu einer Tiefe von 1.

   b. Bis zu einer unbegrenzten Tiefe.

Die (a) Fälle (eine bestimmte Tiefe) sind in SQL einfacher. Der Sonderfall (Tiefe = 1) ist in SQL trivial. Die Tiefe ungleich Null ist schwieriger. Eine endliche Tiefe, die nicht Null ist, kann über eine begrenzte Anzahl von Joins erfolgen. Die Fälle (b) mit unbestimmter Tiefe (nach oben, nach unten) sind wirklich hart.

Wenn dein BaumRIESIG(Millionen von Knoten) ist, dann bist du in einer Welt voller Schmerzen, egal was du versuchst zu tun. 

Wenn Ihr Baum weniger als eine Million Knoten umfasst, holen Sie ihn einfach in den Speicher und bearbeiten Sie ihn dort. Das Leben ist in einer OO-Welt viel einfacher. Holen Sie einfach die Zeilen ab und erstellen Sie den Baum, während die Zeilen zurückgegeben werden.

Wenn Sie einen RiesenBaum haben, haben Sie zwei Möglichkeiten.

• Rekursive Cursor für das unbegrenzte Abrufen. Dies bedeutet, dass die Struktur der Struktur O(1) ist - aktualisieren Sie einfach ein paar Knoten, und Sie sind fertig. Abrufen ist jedoch O (n * log (n)), da Sie für jeden Knoten mit untergeordneten Elementen einen Cursor öffnen müssen.

• Clevere "Heap-Nummerierungs" -Algorithmen können die Abstammung jedes Knotens kodieren. Sobald jeder Knoten richtig nummeriert ist, kann für alle vier Abfragetypen ein triviales SQL-SELECT verwendet werden. Änderungen an der Baumstruktur erfordern jedoch eine Neunummerierung der Knoten, wodurch die Kosten einer Änderung im Vergleich zu den Kosten für das Abrufen relativ hoch sind.

Wenn sich in der Datenbank viele Bäume befinden und Sie immer nur den gesamten Baum herausholen, würde ich eine Baum-ID (oder Stammknoten-ID) und eine übergeordnete Knoten-ID für jeden Knoten in der Datenbank speichern und alle Knoten für einen Knoten erhalten bestimmte Baum-ID und Prozess im Speicher.

Wenn Sie jedoch Teilbäume erhalten, können Sie nur einen Teilbaum einer bestimmten übergeordneten Knoten-ID abrufen. Sie müssen also entweder alle übergeordneten Knoten jedes Knotens speichern, um die obige Methode zu verwenden, oder mehrere SQL-Abfragen ausführen, wenn Sie in den tree (hoffentlich gibt es keine Zyklen in Ihrem Baum!), Sie können jedoch dieselbe Prepared-Anweisung (vorausgesetzt, dass Knoten vom gleichen Typ sind und alle in einer einzigen Tabelle gespeichert sind) wiederverwenden, um ein erneutes Kompilieren der SQL zu verhindern nicht langsamer sein, mit Datenbankoptimierungen, die auf die Abfrage angewendet werden, kann dies vorzuziehen sein. Vielleicht möchten Sie einige Tests durchführen, um das herauszufinden.

Wenn Sie nur einen Baum speichern, wird Ihre Frage nur zur Abfrage von Unterbäumen und die zweite Antwort wird angewendet.

Ich bin ein Fan der einfachen Methode, eine ID zu speichern, die ihrer parentID zugeordnet ist:

ID     ParentID
1      null
2      null
3      1
4      2
...    ...

Es ist leicht zu warten und sehr skalierbar.

Google für "Materialized Path" oder "Genetic Trees" ...

In Oracle gibt es die Anweisung SELECT ... CONNECT BY, um Bäume abzurufen. 

Nicht für alle Situationen geeignet, sondern beispielsweise mit einer Kommentarstruktur versehen:

ID | ParentCommentID

Sie könnten auch TopCommentID speichern, das den obersten Kommentar darstellt:

ID | ParentCommentID | TopCommentID

Wo TopCommentID und ParentCommentIDnull oder 0 sind, wenn es sich um den obersten Kommentar handelt. Für untergeordnete Kommentare zeigt ParentCommentID auf den Kommentar darüber und TopCommentID auf das oberste übergeordnete Element.

Dieser Artikel ist interessant, da er einige Abrufmethoden sowie eine Methode zum Speichern der Abstammungslinie als abgeleitete Spalte zeigt. Die Abstammungslinie bietet eine Abkürzungsmethode zum Abrufen der Hierarchie ohne zu viele Verknüpfungen.