Was ist der effizienteste/elegante Weg, um eine flache Tabelle in einen Baum zu parsen?

Question

Angenommen, Sie haben eine flache Tabelle, die eine geordnete Baumhierarchie speichert:

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, in dem wir Folgendes haben [id] Name . Der Wurzelknoten 0 ist fiktiv.

                       \[0\] ROOT
                          /    \\ 
              \[1\] Node 1          \[3\] Node 2
              /       \\                   \\
    \[2\] Node 1.1     \[6\] Node 1.2      \[5\] Node 2.1
          /          
 \[4\] Node 1.1.1

Welchen minimalistischen Ansatz würden Sie verwenden, um das in HTML (oder Text, was das betrifft) als korrekt geordneten, korrekt eingerückten Baum auszugeben?

Nehmen wir weiter an, Sie haben nur einfache Datenstrukturen (Arrays und Hashmaps), keine ausgefallenen Objekte mit Parent-Children-Referenzen, kein ORM, kein Framework, nur Ihre beiden Hände. Die Tabelle wird als Ergebnismenge dargestellt, auf die nach dem Zufallsprinzip zugegriffen werden kann.

Pseudocode oder einfaches Englisch ist in Ordnung, dies ist eine rein konzeptionelle Frage.

Bonusfrage: Gibt es eine grundsätzlich bessere Möglichkeit, eine Baumstruktur wie diese in einem RDBMS zu speichern?

---

BEARBEITUNGEN UND ERGÄNZUNGEN

Um die Frage eines Kommentators ( Mark Bessey ) Frage: Ein Root-Knoten ist nicht notwendig, da er ohnehin nie angezeigt wird. ParentId = 0 ist die Konvention, um auszudrücken, dass dies die oberste Ebene ist. Die Spalte Order definiert, wie Knoten mit demselben Parent sortiert werden sollen.

Die "Ergebnismenge", von der ich sprach, kann man sich als ein Array von Hashmaps vorstellen (um in dieser Terminologie zu bleiben). In meinem Beispiel sollte sie bereits vorhanden sein. Einige Antworten gehen die extra Meile und konstruieren es zuerst, aber das ist okay.

Der Baum kann beliebig tief sein. Jeder Knoten kann N Kinder haben. Ich hatte allerdings nicht unbedingt einen Baum mit "Millionen von Einträgen" im Sinn.

Verstehen Sie meine Wahl der Knotenbenennung ("Knoten 1.1.1") nicht als etwas, auf das Sie sich verlassen können. Die Knoten könnten genauso gut "Frank" oder "Bob" heißen, es wird keine Namensstruktur impliziert, dies diente lediglich der besseren Lesbarkeit.

Ich habe meine eigene Lösung gepostet, damit ihr sie in Stücke reißen könnt.

Answer 1

Nun, da MySQL 8.0 unterstützt rekursive Abfragen können wir sagen, dass alle gängigen SQL-Datenbanken unterstützen rekursive Abfragen in der Standardsyntax.

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

In meiner Präsentation habe ich rekursive Abfragen in MySQL 8.0 getestet Rekursive Abfrage Throwdown im Jahr 2017.

Nachstehend finden Sie meine ursprüngliche Antwort aus dem Jahr 2008:

---

Es gibt mehrere Möglichkeiten, baumstrukturierte Daten in einer relationalen Datenbank zu speichern. In dem von Ihnen gezeigten Beispiel werden zwei Methoden verwendet:

• Adjacency List (die "übergeordnete" Spalte) und
• Aufzählung der Pfade (die gepunkteten Zahlen in Ihrer Namensspalte).

Eine andere Lösung heißt Verschachtelte Gruppen und sie kann auch in derselben Tabelle gespeichert werden. Lesen " Bäume und Hierarchien in SQL for Smarties " von Joe Celko finden Sie viele weitere Informationen zu diesen Entwürfen.

Ich bevorzuge in der Regel ein Design namens Verschluss-Tabelle (auch bekannt als "Adjacency Relation") zur Speicherung baumstrukturierter Daten. Sie erfordert eine weitere Tabelle, aber dann ist die Abfrage von Bäumen ziemlich einfach.

Ich behandle die Abschlusstabelle in meiner Präsentation Modelle für hierarchische Daten mit SQL und PHP und in meinem Buch SQL-Antipatterns: Vermeiden der Fallstricke der Datenbankprogrammierung .

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Speichern Sie alle Pfade in der Abschlusstabelle, bei denen es eine direkte Abstammung von einem Knoten zu einem anderen gibt. Fügen Sie eine Zeile für jeden Knoten ein, um auf sich selbst zu verweisen. Beispiel: Verwenden Sie den Datensatz, den Sie in Ihrer Frage gezeigt haben:

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

Jetzt können Sie einen Baum erhalten, der bei Knoten 1 beginnt, wie folgt:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

Die Ausgabe (im MySQL-Client) sieht wie folgt aus:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

Mit anderen Worten: Die Knoten 3 und 5 sind ausgeschlossen, da sie Teil einer separaten Hierarchie sind und nicht von Knoten 1 abstammen.

---

Re: Kommentar von e-satis über unmittelbare Kinder (oder unmittelbare Eltern). Sie können ein "" hinzufügen path_length " in die Spalte ClosureTable um die Abfrage speziell nach einem unmittelbaren Kind oder Elternteil (oder einer anderen Entfernung) zu erleichtern.

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

Dann können Sie in Ihrer Suche einen Begriff hinzufügen, um die unmittelbaren Kinder eines bestimmten Knotens abzufragen. Dies sind Nachkommen, deren path_length ist 1.

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

---

Zu dem Kommentar von @ashraf: "Wie wäre es, den gesamten Baum [nach Namen] zu sortieren?"

Hier ist eine Beispielabfrage, um alle Knoten zurückzugeben, die Nachfahren von Knoten 1 sind, und sie mit der FlatTable zu verbinden, die andere Knotenattribute enthält wie name und sortieren Sie nach dem Namen.

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

---

Zu dem Kommentar von @Nate:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

---

Ein Benutzer hat heute eine Änderung vorgeschlagen. Die SO-Moderatoren haben die Änderung genehmigt, aber ich mache sie rückgängig.

Die Bearbeitung schlug vor, dass das ORDER BY in der letzten Abfrage oben lauten sollte ORDER BY b.path_length, f.name , vermutlich um sicherzustellen, dass die Reihenfolge mit der Hierarchie übereinstimmt. Dies funktioniert jedoch nicht, da es "Knoten 1.1.1" nach "Knoten 1.2" anordnen würde.

Wenn Sie möchten, dass die Reihenfolge sinnvoll mit der Hierarchie übereinstimmt, ist das möglich, aber nicht einfach durch die Reihenfolge nach der Pfadlänge. Siehe zum Beispiel meine Antwort auf MySQL Closure Table hierarchische Datenbank - Wie man Informationen in der richtigen Reihenfolge herauszieht .

Answer 2

Wenn Sie geschachtelte Sets verwenden (manchmal auch als Modified Pre-order Tree Traversal bezeichnet), können Sie die gesamte Baumstruktur oder einen beliebigen Teilbaum darin in Baumreihenfolge mit einer einzigen Abfrage extrahieren, allerdings zu dem Preis, dass Einfügevorgänge teurer sind, da Sie Spalten verwalten müssen, die einen Pfad in Reihenfolge durch die Baumstruktur beschreiben.

Für django-mptt habe ich eine Struktur wie diese verwendet:

id  parent\_id  tree\_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

Das beschreibt einen Baum, der wie folgt aussieht (mit id die jedes Element darstellen):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

Oder als verschachteltes Mengendiagramm, das deutlicher macht, wie die lft y rght Werte arbeiten:

 \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
|  Root 1                                                                  |
|   \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_    \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   \_\_\_\_\_\_\_\_\_\_\_    \_\_\_\_\_\_\_\_\_\_\_   |  |   \_\_\_\_\_\_\_\_\_\_\_    \_\_\_\_\_\_\_\_\_\_\_   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3\_\_\_\_\_\_\_\_\_\_\_4  5\_\_\_\_\_\_\_\_\_\_\_6  7  8  9\_\_\_\_\_\_\_\_\_\_\_10 11\_\_\_\_\_\_\_\_\_\_12 13 14
|  |\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_|  |\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_|  |
|\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_|

Wie Sie sehen können, müssen Sie, um den gesamten Teilbaum für einen bestimmten Knoten in Baumreihenfolge zu erhalten, einfach alle Zeilen auswählen, die lft y rght Werte zwischen seinen lft y rght Werte. Es ist auch einfach, den Baum der Vorfahren für einen bestimmten Knoten abzurufen.

El level Spalte ist eher eine Denormalisierung aus Gründen der Bequemlichkeit, und die tree_id Spalte können Sie das System neu starten lft y rght Nummerierung für jeden Knoten der obersten Ebene, wodurch die Anzahl der von Einfügungen, Verschiebungen und Löschungen betroffenen Spalten reduziert wird, da die lft y rght Spalten müssen entsprechend angepasst werden, wenn diese Vorgänge stattfinden, um Lücken zu schaffen oder zu schließen. Ich habe einige Entwicklungshinweise zu der Zeit, als ich versuchte, mir die für jeden Vorgang erforderlichen Abfragen vorzustellen.

Für die eigentliche Arbeit mit diesen Daten, um einen Baum anzuzeigen, habe ich eine tree_item_iterator die Ihnen für jeden Knoten genügend Informationen liefert, um die von Ihnen gewünschte Anzeige zu erstellen.

Mehr Informationen über MPTT:

• Bäume in SQL
• Hierarchische Daten in einer Datenbank speichern
• Hierarchische Daten in MySQL verwalten

Answer 3

Es handelt sich um eine recht alte Frage, aber da sie schon oft gestellt wurde, 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 gemeinsame Tabellenausdrücke (CTEs). Es bietet die Möglichkeit, die gesamte Baumstruktur auf einmal abzurufen und Informationen über die Ebene des Knotens, seinen übergeordneten Knoten und die Reihenfolge der Kinder des übergeordneten Knotens zu erhalten.

Ich möchte Ihnen zeigen, wie dies in PostgreSQL 9.1 funktioniert.

1. Eine Struktur schaffen

   CREATE TABLE tree (
       id int  NOT NULL,
       name varchar(32)  NOT NULL,
       parent_id int  NULL,
       node_order int  NOT NULL,
       CONSTRAINT tree_pk PRIMARY KEY (id),
       CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
         REFERENCES tree (id) NOT DEFERRABLE
   );
   
   insert into tree values
     (0, 'ROOT', NULL, 0),
     (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);

2. Schreiben Sie eine Anfrage

   WITH RECURSIVE 
   tree_search (id, name, level, parent_id, node_order) AS (
     SELECT 
       id, 
       name,
       0,
       parent_id, 
       1 
     FROM tree
     WHERE parent_id is NULL
   
     UNION ALL 
     SELECT 
       t.id, 
       t.name,
       ts.level + 1, 
       ts.id, 
       t.node_order 
     FROM tree t, tree_search ts 
     WHERE t.parent_id = ts.id 
   ) 
   SELECT * FROM tree_search 
   WHERE level > 0 
   ORDER BY level, parent_id, node_order;

   Hier sind die Ergebnisse:

    id |    name    | level | parent_id | node_order 
   ----+------------+-------+-----------+------------
     1 | Node 1     |     1 |         0 |         10
     3 | Node 2     |     1 |         0 |         20
     2 | Node 1.1   |     2 |         1 |         10
     6 | Node 1.2   |     2 |         1 |         20
     5 | Node 2.1   |     2 |         3 |         10
     4 | Node 1.1.1 |     3 |         2 |         10
   (6 rows)

   Die Baumknoten sind nach einer Tiefenstufe geordnet. In der endgültigen Ausgabe würden wir sie in den folgenden Zeilen darstellen.

   Für jede Ebene sind sie nach parent_id und node_order innerhalb der übergeordneten Ebene geordnet. Daraus ergibt sich, wie sie in der Ausgabe dargestellt werden sollen - Verknüpfung der Knoten mit den übergeordneten Ebenen in dieser Reihenfolge.

   Mit einer solchen Struktur wäre es nicht schwierig, eine wirklich schöne Präsentation in HTML zu erstellen.

   Rekursive CTEs sind verfügbar in PostgreSQL, IBM DB2, MS SQL Server und Oracle .

   Wenn Sie mehr über rekursive SQL-Abfragen lesen möchten, können Sie entweder in der Dokumentation Ihres bevorzugten DBMS nachsehen oder meine beiden Artikel zu diesem Thema lesen:

   • Machen Sie es in SQL: Rekursiver Baum-Traversal
   • Lernen Sie die Leistungsfähigkeit von rekursiven SQL-Abfragen kennen

Answer 4

Ab Oracle 9i können Sie CONNECT BY verwenden.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

Ab SQL Server 2005 können Sie einen rekursiven gemeinsamen Tabellenausdruck (CTE) verwenden.

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Beide werden die folgenden Ergebnisse ausgeben.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

Answer 5

Bills Antwort ist verdammt gut, diese Antwort fügt einige Dinge hinzu, die mich wünschen lassen, SO würde Thread-Antworten unterstützen.

Auf jeden Fall wollte ich die Baumstruktur und die Eigenschaft Order unterstützen. Ich fügte eine einzelne Eigenschaft in jeden Knoten ein, die leftSibling die das Gleiche tut Order in der ursprünglichen Frage gemeint ist (Beibehaltung der Reihenfolge von links nach rechts).

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto\_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto\_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

Weitere Details und SQL-Code in meinem Blog .

Danke Bill, deine Antwort war hilfreich für den Anfang!