Angenommen, Sie haben eine flache Tabelle, in der eine geordnete Baumhierarchie gespeichert ist:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
Hier ist ein Diagramm, wo wir haben [id] Name
. Wurzelknoten 0 ist fiktiv.
[0] Wurzel / \. [1] Knoten 1 [3] Knoten 2 / \ \ [2] Knoten 1.1 [6] Knoten 1.2 [5] Knoten 2.1 /. [4] Knoten 1.1.1
Welchen minimalistischen Ansatz würden Sie verwenden, um dies als korrekt geordneten, korrekt eingerückten Baum in HTML (oder Text) auszugeben?
Angenommen, Sie haben nur grundlegende Datenstrukturen (Arrays und Hashmaps), keine ausgefallenen Objekte mit übergeordneten / untergeordneten Referenzen, kein ORM, kein Framework, nur Ihre beiden Hände. Die Tabelle wird als Ergebnismenge dargestellt, auf die zufällig zugegriffen werden kann.
Pseudocode oder einfaches Englisch ist in Ordnung, dies ist eine rein konzeptionelle Frage.
Bonusfrage: Gibt es eine grundlegend bessere Möglichkeit, eine solche Baumstruktur in einem RDBMS zu speichern?
BEARBEITUNGEN UND ERGÄNZUNGEN
So beantworten Sie die Frage eines Kommentators ( Mark Bessey ): Ein Stammknoten ist nicht erforderlich, da er ohnehin nie angezeigt wird. ParentId = 0 ist die Konvention, um "diese sind die oberste Ebene" auszudrücken. In der Spalte Reihenfolge wird definiert, wie Knoten mit demselben übergeordneten Element sortiert werden.
Die "Ergebnismenge", von der ich gesprochen habe, kann als eine Reihe von Hashmaps dargestellt werden (um in dieser Terminologie zu bleiben). Denn mein Beispiel sollte schon da sein. Einige Antworten gehen die Extrameile und konstruieren es zuerst, aber das ist okay.
Der Baum kann beliebig tief sein. Jeder Knoten kann N untergeordnete Knoten haben. Ich hatte jedoch nicht genau einen Baum mit "Millionen von Einträgen" im Sinn.
Verwechseln Sie meine Wahl der Knotenbezeichnung ('Node 1.1.1') nicht mit etwas, auf das Sie sich verlassen können. Die Knoten könnten ebenso gut als "Frank" oder "Bob" bezeichnet werden, es ist keine Namensstruktur impliziert, dies diente lediglich dazu, sie lesbar zu machen.
Ich habe meine eigene Lösung veröffentlicht, damit ihr sie in Stücke reißen könnt.
Antworten:
Nachdem MySQL 8.0 rekursive Abfragen unterstützt , können wir sagen, dass alle gängigen SQL-Datenbanken rekursive Abfragen in Standardsyntax unterstützen.
Ich habe rekursive Abfragen in MySQL 8.0 in meiner Präsentation Recursive Query Throwdown im Jahr 2017 getestet .
Unten ist meine ursprüngliche Antwort von 2008:
Es gibt verschiedene Möglichkeiten, baumstrukturierte Daten in einer relationalen Datenbank zu speichern. Was Sie in Ihrem Beispiel zeigen, verwendet zwei Methoden:
Eine andere Lösung heißt Verschachtelte Mengen und kann auch in derselben Tabelle gespeichert werden. Weitere Informationen zu diesen Designs finden Sie unter " Bäume und Hierarchien in SQL für Smarties " von Joe Celko.
Normalerweise bevorzuge ich ein Design namens Closure Table (auch bekannt als "Adjacency Relation") zum Speichern von Daten mit Baumstruktur. Es erfordert eine andere Tabelle, aber das Abfragen von Bäumen ist ziemlich einfach.
Ich beschreibe die Closure Table in meinen Präsentationsmodellen für hierarchische Daten mit SQL und PHP und in meinem Buch SQL Antipatterns: Vermeiden der Fallstricke der Datenbankprogrammierung .
Speichern Sie alle Pfade in der Closure Table, in der es eine direkte Abstammung von einem Knoten zum anderen gibt. Fügen Sie für jeden Knoten eine Zeile ein, um auf sich selbst zu verweisen. Verwenden Sie beispielsweise den Datensatz, den Sie in Ihrer Frage angezeigt haben:
Jetzt können Sie einen Baum ab Knoten 1 wie folgt erhalten:
Die Ausgabe (im MySQL-Client) sieht folgendermaßen aus:
Mit anderen Worten, die Knoten 3 und 5 werden ausgeschlossen, da sie Teil einer separaten Hierarchie sind und nicht von Knoten 1 abstammen.
Betreff: Kommentar von e-satis zu unmittelbaren Kindern (oder unmittelbaren Eltern). Sie können der
path_length
Spalte " " eine Spalte hinzufügenClosureTable
, um die Abfrage eines unmittelbaren Kindes oder Elternteils (oder einer anderen Entfernung) zu vereinfachen.Anschließend können Sie Ihrer Suche einen Begriff hinzufügen, um die unmittelbaren untergeordneten Elemente eines bestimmten Knotens abzufragen. Dies sind Nachkommen, deren
path_length
1 ist.Kommentar von @ashraf: "Wie wäre es, den ganzen Baum [nach Namen] zu sortieren?"
Hier ist eine Beispielabfrage, um alle Knoten, die Nachkommen von Knoten 1 sind, zurückzugeben, sie mit der FlatTable zu verknüpfen, die andere Knotenattribute enthält, z. B.
name
und nach dem Namen zu sortieren.Kommentar von @Nate:
Ein Benutzer hat heute eine Bearbeitung vorgeschlagen. SO-Moderatoren haben die Bearbeitung genehmigt, aber ich mache sie rückgängig.
Die Bearbeitung schlug vor, dass ORDER BY in der letzten Abfrage oben sein sollte
ORDER BY b.path_length, f.name
, vermutlich um sicherzustellen, dass die Reihenfolge mit der Hierarchie übereinstimmt. Dies funktioniert jedoch nicht, da "Knoten 1.1.1" nach "Knoten 1.2" bestellt wird.Wenn Sie möchten, dass die Reihenfolge auf sinnvolle Weise mit der Hierarchie übereinstimmt, ist dies möglich, jedoch nicht einfach durch die Reihenfolge nach Pfadlänge. Siehe zum Beispiel meine Antwort auf die hierarchische Datenbank der MySQL Closure Table - So ziehen Sie Informationen in der richtigen Reihenfolge ab .
quelle
parent_id
) hat nur eine Zeile, um jede Eltern-Kind-Beziehung auszudrücken, aber Closure Table hat viele.Wenn Sie verschachtelte Mengen verwenden (manchmal auch als modifizierte Baumdurchquerung vor der Bestellung bezeichnet), können Sie die gesamte Baumstruktur oder einen darin enthaltenen Teilbaum in Baumreihenfolge mit einer einzigen Abfrage extrahieren, wobei die Kosten für Einfügungen nach Bedarf höher sind Verwalten Sie Spalten, die einen Pfad in der richtigen Reihenfolge durch Ihre Baumstruktur beschreiben.
Für django-mptt habe ich eine Struktur wie diese verwendet:
Welches beschreibt einen Baum, der so aussieht (mit
id
Darstellung jedes Elements):Oder als verschachteltes Mengen-Diagramm, das die Funktionsweise der
lft
undrght
-Werte deutlicher macht :Wie Sie sehen können, die gesamte Unterstruktur für einen bestimmten Knoten im Baum erhalten, können Sie einfach alle Zeilen wählen haben , die haben
lft
undrght
ihre Werte zwischenlft
undrght
Werte. Es ist auch einfach, den Stammbaum für einen bestimmten Knoten abzurufen.Die
level
Spalte ist vor allem der Einfachheit halber ein wenig denormalisiert, und in dertree_id
Spalte können Sie dielft
und dierght
Nummerierung für jeden Knoten der obersten Ebene neu starten , wodurch die Anzahl der Spalten, die von Einfügungen, Verschiebungen und Löschungen betroffen sind, so verringert wird, wie es die Spaltenlft
undrght
sein müssen entsprechend angepasst, wenn diese Operationen stattfinden, um Lücken zu schaffen oder zu schließen. Ich habe einige Entwicklungsnotizen gemacht, als ich versuchte, mich mit den für jede Operation erforderlichen Abfragen zu beschäftigen.Um tatsächlich mit diesen Daten zu arbeiten, um einen Baum anzuzeigen, habe ich eine
tree_item_iterator
Dienstprogrammfunktion erstellt, die für jeden Knoten ausreichend Informationen liefert, um die gewünschte Art von Anzeige zu generieren.Weitere Informationen zu MPTT:
quelle
lft
undrght
für Spaltennamen mehr verwenden. Ich meine, wie viele Zeichen mussten wir nicht eingeben? einer?!Es ist eine ziemlich alte Frage, aber da sie viele Ansichten hat, denke ich, dass es sich lohnt, eine alternative und meiner Meinung nach sehr elegante Lösung vorzustellen.
Um eine Baumstruktur zu lesen, können Sie rekursive Common Table Expressions (CTEs) verwenden. Es bietet die Möglichkeit, die gesamte Baumstruktur auf einmal abzurufen, Informationen über die Ebene des Knotens, seinen übergeordneten Knoten und die Reihenfolge innerhalb der untergeordneten Knoten des übergeordneten Knotens zu erhalten.
Lassen Sie mich Ihnen zeigen, wie dies in PostgreSQL 9.1 funktionieren würde.
Erstellen Sie eine Struktur
Schreiben Sie eine Abfrage
Hier sind die Ergebnisse:
Die Baumknoten sind nach einer Tiefe geordnet. In der endgültigen Ausgabe würden wir sie in den folgenden Zeilen präsentieren.
Für jede Ebene werden sie nach parent_id und node_order innerhalb des übergeordneten Elements sortiert. Hier erfahren Sie, wie Sie sie im Ausgangsverknüpfungsknoten in dieser Reihenfolge dem übergeordneten Knoten präsentieren.
Mit einer solchen Struktur wäre es nicht schwierig, eine wirklich schöne Präsentation in HTML zu erstellen.
Rekursive CTEs sind in PostgreSQL, IBM DB2, MS SQL Server und Oracle verfügbar .
Wenn Sie mehr über rekursive SQL-Abfragen erfahren möchten, können Sie entweder die Dokumentation Ihres bevorzugten DBMS überprüfen oder meine beiden Artikel zu diesem Thema lesen:
quelle
Ab Oracle 9i können Sie CONNECT BY verwenden.
Ab SQL Server 2005 können Sie einen rekursiven allgemeinen Tabellenausdruck (CTE) verwenden.
Beide geben die folgenden Ergebnisse aus.
quelle
Bills Antwort ist verdammt gut, diese Antwort fügt einige Dinge hinzu, die mich dazu bringen, SO unterstützte Thread-Antworten zu wünschen.
Auf jeden Fall wollte ich die Baumstruktur und die Order-Eigenschaft unterstützen. Ich habe in jeden aufgerufenen Knoten eine einzelne Eigenschaft eingefügt
leftSibling
, die dasselbe tutOrder
, was in der ursprünglichen Frage vorgesehen ist (Reihenfolge von links nach rechts beibehalten).Weitere Details und SQL-Code in meinem Blog .
Vielen Dank, Bill. Ihre Antwort war hilfreich für den Einstieg!
quelle
Wenn ich die Wahl hätte, würde ich Objekte verwenden. Ich würde ein Objekt für jeden Datensatz erstellen, in dem jedes Objekt eine
children
Sammlung hat, und sie alle in einem Assoc-Array (/ hashtable) speichern, in dem die ID der Schlüssel ist. Und blitzen Sie einmal durch die Sammlung und fügen Sie die Kinder zu den relevanten Kinderfeldern hinzu.Einfach.Aber weil Sie keinen Spaß daran haben, die Verwendung eines guten OOP einzuschränken, würde ich wahrscheinlich basierend auf Folgendem iterieren:
Bearbeiten: Dies ähnelt einigen anderen Einträgen, aber ich denke, es ist etwas sauberer. Eines möchte ich hinzufügen: Dies ist extrem SQL-intensiv. Es ist böse . Wenn Sie die Wahl haben, gehen Sie die OOP-Route.
quelle
Dies wurde schnell geschrieben und ist weder hübsch noch effizient (außerdem gibt es viele Autoboxen, konvertiert zwischen
int
undInteger
ist ärgerlich!), Aber es funktioniert.Es verstößt wahrscheinlich gegen die Regeln, da ich meine eigenen Objekte erstelle, aber hey, ich mache das als Ablenkung von der realen Arbeit :)
Dies setzt auch voraus, dass das resultSet / die Tabelle vollständig in eine Struktur eingelesen wird, bevor Sie mit dem Erstellen von Knoten beginnen. Dies wäre nicht die beste Lösung, wenn Sie Hunderttausende von Zeilen haben.
quelle
Es gibt wirklich gute Lösungen, die die interne btree-Darstellung von SQL-Indizes ausnutzen. Dies basiert auf einigen großartigen Forschungen, die um 1998 durchgeführt wurden.
Hier ist eine Beispieltabelle (in MySQL).
Die einzigen Felder, die für die Baumdarstellung erforderlich sind, sind:
Hier ist ein Beispiel für eine 24-Knoten-Population, geordnet nach tw:
Jedes Baumergebnis kann nicht rekursiv erstellt werden. Zum Beispiel, um eine Liste der Vorfahren des Knotens bei tw = '22 'zu erhalten.
Vorfahren
Geschwister und Kinder sind trivial - verwenden Sie einfach die Pa-Feldreihenfolge nach Tw.
Nachkommenschaft
Zum Beispiel die Menge (Verzweigung) von Knoten, die bei tw = 17 verwurzelt sind.
Zusätzliche Bemerkungen
Diese Methode ist äußerst nützlich, wenn eine weitaus größere Anzahl von Lesevorgängen vorliegt als Einfügungen oder Aktualisierungen.
Da zum Einfügen, Verschieben oder Aktualisieren eines Knotens in den Baum eine Anpassung des Baums erforderlich ist, muss die Tabelle gesperrt werden, bevor mit der Aktion begonnen wird.
Die Einfüge- / Löschkosten sind hoch, da die Werte für tw-Index und sz (Zweiggröße) auf allen Knoten nach dem Einfügepunkt bzw. für alle Vorfahren aktualisiert werden müssen.
Beim Verschieben von Zweigen wird der tw-Wert des Zweigs außerhalb des Bereichs verschoben. Daher müssen beim Verschieben eines Zweigs auch Fremdschlüsseleinschränkungen deaktiviert werden. Es sind im Wesentlichen vier Abfragen erforderlich, um einen Zweig zu verschieben:
Passen Sie Baumabfragen an
Das Öffnen / Schließen von Lücken im Baum ist eine wichtige Unterfunktion, die von Methoden zum Erstellen / Aktualisieren / Löschen verwendet wird. Deshalb füge ich sie hier ein.
Wir benötigen zwei Parameter - ein Flag, das angibt, ob wir verkleinern oder vergrößern, und den Tw-Index des Knotens. Also zum Beispiel tw = 18 (mit einer Zweiggröße von 5). Nehmen wir an, wir verkleinern (entfernen tw) - dies bedeutet, dass wir in den Aktualisierungen des folgenden Beispiels '-' anstelle von '+' verwenden.
Wir verwenden zuerst eine (leicht veränderte) Ahnenfunktion, um den sz-Wert zu aktualisieren.
Dann müssen wir das Tw für diejenigen anpassen, deren Tw höher ist als der zu entfernende Zweig.
Dann müssen wir das Elternteil für diejenigen anpassen, deren pa's tw höher ist als der zu entfernende Zweig.
quelle
Angenommen, Sie wissen, dass die Stammelemente Null sind, ist hier der Pseudocode, der in Text ausgegeben werden soll:
quelle
Sie können jede andere Datenstruktur mit einer Hashmap emulieren, das ist also keine schreckliche Einschränkung. Beim Scannen von oben nach unten erstellen Sie für jede Zeile der Datenbank eine Hashmap mit einem Eintrag für jede Spalte. Fügen Sie jede dieser Hashmaps zu einer "Master" -Hashmap hinzu, die auf der ID angegeben ist. Wenn ein Knoten ein "übergeordnetes Element" hat, das Sie noch nicht gesehen haben, erstellen Sie einen Platzhaltereintrag dafür in der Master-Hashmap und füllen Sie ihn aus, wenn Sie den tatsächlichen Knoten sehen.
Führen Sie zum Ausdrucken einen einfachen Tiefen-First-Durchlauf durch die Daten durch und verfolgen Sie dabei die Einrückungsstufe. Sie können dies vereinfachen, indem Sie für jede Zeile einen "untergeordneten" Eintrag beibehalten und ihn beim Scannen der Daten ausfüllen.
Ob es eine "bessere" Möglichkeit gibt, einen Baum in einer Datenbank zu speichern, hängt davon ab, wie Sie die Daten verwenden. Ich habe Systeme mit einer bekannten maximalen Tiefe gesehen, die für jede Ebene in der Hierarchie eine andere Tabelle verwendeten. Das ist sehr sinnvoll, wenn die Ebenen im Baum doch nicht ganz gleich sind (Kategorien der obersten Ebene unterscheiden sich von den Blättern).
quelle
Wenn verschachtelte Hash-Maps oder Arrays erstellt werden können, kann ich einfach die Tabelle von Anfang an durchgehen und jedes Element dem verschachtelten Array hinzufügen. Ich muss jede Zeile bis zum Wurzelknoten verfolgen, um zu wissen, in welche Ebene des verschachtelten Arrays sie eingefügt werden soll. Ich kann Memoization verwenden, damit ich nicht immer wieder denselben Elternteil nachschlagen muss.
Bearbeiten: Ich würde zuerst die gesamte Tabelle in ein Array einlesen, damit die Datenbank nicht wiederholt abgefragt wird. Dies ist natürlich nicht praktikabel, wenn Ihr Tisch sehr groß ist.
Nachdem die Struktur erstellt wurde, muss ich zuerst eine Tiefe durchlaufen und den HTML-Code ausdrucken.
Es gibt keinen besseren grundlegenden Weg, um diese Informationen in einer Tabelle zu speichern (ich könnte mich jedoch irren;) und würde gerne eine bessere Lösung sehen). Wenn Sie jedoch ein Schema erstellen, um dynamisch erstellte DB-Tabellen zu verwenden, haben Sie auf Kosten der Einfachheit und des Risikos der SQL-Hölle eine ganz neue Welt eröffnet;).
quelle
Wenn sich die Elemente in der Baumreihenfolge befinden, wie in Ihrem Beispiel gezeigt, können Sie etwa das folgende Python-Beispiel verwenden:
Dadurch wird ein Stapel verwaltet, der die aktuelle Position im Baum darstellt. Für jedes Element in der Tabelle werden Stapelelemente angezeigt (die übereinstimmenden Divs werden geschlossen), bis das übergeordnete Element des aktuellen Elements gefunden wird. Dann gibt es den Start dieses Knotens aus und schiebt ihn auf den Stapel.
Wenn Sie den Baum mit Einrückungen anstatt mit verschachtelten Elementen ausgeben möchten, können Sie einfach die print-Anweisungen überspringen, um die Divs zu drucken, und vor jedem Element eine Anzahl von Leerzeichen drucken, die einem Vielfachen der Größe des Stapels entsprechen. Zum Beispiel in Python:
Sie können diese Methode auch problemlos verwenden, um eine Reihe verschachtelter Listen oder Wörterbücher zu erstellen.
Bearbeiten: Ich sehe aus Ihrer Klarstellung, dass die Namen nicht als Knotenpfade gedacht waren. Das deutet auf einen alternativen Ansatz hin:
Dies konstruiert einen Baum von Tupelarrays (!). idx [0] repräsentiert die Wurzel (n) des Baums. Jedes Element in einem Array ist ein 2-Tupel, das aus dem Knoten selbst und einer Liste aller untergeordneten Elemente besteht. Nach der Erstellung können Sie an idx [0] festhalten und idx verwerfen, es sei denn, Sie möchten über ihre ID auf Knoten zugreifen.
quelle
Um die SQL-Lösung von Bill zu erweitern, können Sie dasselbe grundsätzlich mit einem flachen Array tun. Wenn Ihre Zeichenfolgen alle dieselbe Länge haben und Ihre maximale Anzahl von untergeordneten Zeichen bekannt ist (z. B. in einem Binärbaum), können Sie dies mit einer einzelnen Zeichenfolge (Zeichenarray) tun. Wenn Sie eine beliebige Anzahl von Kindern haben, erschwert dies die Dinge ein wenig ... Ich müsste meine alten Notizen überprüfen, um zu sehen, was getan werden kann.
Wenn Sie dann ein wenig Speicher opfern, insbesondere wenn Ihr Baum spärlich und / oder nicht ausgeglichen ist, können Sie mit ein wenig Indexmathematik zufällig auf alle Zeichenfolgen zugreifen, indem Sie Ihren Baum mit der Breite zuerst im Array wie folgt speichern (für eine Binärdatei) Baum):
Du kennst deine Saitenlänge, du weißt es
Ich bin jetzt auf der Arbeit, kann also nicht viel Zeit damit verbringen, aber mit Interesse kann ich ein bisschen Code abrufen, um dies zu tun.
Wir verwenden es, um in binären Bäumen zu suchen, die aus DNA-Codons bestehen. Ein Prozess, der den Baum erstellt hat, wurde dann abgeflacht, um nach Textmustern zu suchen. Wenn wir gefunden werden, erhalten wir den Knoten zurück, obwohl Indexmathematik (Umkehrung von oben) ... sehr schnell und effizient, hart, unser Baum hatte selten leere Knoten, aber wir konnten im Handumdrehen Gigabyte an Daten suchen.
quelle
Denken Sie daran, nosql-Tools wie neo4j für hierarchische Strukturen zu verwenden. zB eine vernetzte Anwendung wie LinkedIn verwendet Couchbase (eine andere NOSQL-Lösung)
Verwenden Sie nosql jedoch nur für Abfragen auf Data-Mart-Ebene und nicht zum Speichern / Verwalten von Transaktionen
quelle