Frage Welche Möglichkeiten gibt es, um hierarchische Daten in einer relationalen Datenbank zu speichern?


Gute Übersichten

In der Regel entscheiden Sie zwischen schnellen Lesezeiten (z. B. verschachtelte Menge) oder schnellen Schreibzeiten (Adjazenzliste). In der Regel erhalten Sie eine Kombination der unten aufgeführten Optionen, die am besten zu Ihren Bedürfnissen passen. Im Folgenden finden Sie einige detaillierte Informationen:

Optionen

Ich bin mir bewusst und allgemeine Merkmale:

  1. Adjazenzliste:
    • Spalten: ID, ParentID
    • Einfach zu implementieren.
    • Günstiger Knoten wird verschoben, eingefügt und gelöscht.
    • Teuer, um das Level, Abstammung und Nachkommen, Pfad zu finden
    • Vermeiden Sie N + 1 über Gemeinsame Tabellenausdrücke in Datenbanken, die sie unterstützen
  2. Verschachtelte Menge (a.k.a Modifizierte Preorder Tree Traversal)
    • Spalten: Links, Rechts
    • Billige Abstammung, Nachkommen
    • Sehr teuer O(n/2) verschiebt, fügt ein und löscht aufgrund der flüchtigen Codierung
  3. Bridge-Tabelle (a.k.a. Closure Table / w löst aus)
    • Verwendet separate Join-Tabelle mit: Vorfahre, Nachfahre, Tiefe (optional)
    • Billige Abstammung und Nachkommen
    • Schreibt Kosten O(log n) (Größe des Teilbaums) zum Einfügen, Aktualisieren, Löschen
    • Normalisierte Codierung: Gut für RDBMS-Statistiken und Abfrageplaner in Joins
    • Erfordert mehrere Zeilen pro Knoten
  4. Abstammungsspalte (a.k.a. Materialisierter PfadPfad-Enumeration
    • Spalte: Abstammung (z. B. / Eltern / Kind / Enkel / etc ...)
    • Günstige Nachkommen über Präfixabfrage (z.B. LEFT(lineage, #) = '/enumerated/path')
    • Schreibt Kosten O(log n) (Größe des Teilbaums) zum Einfügen, Aktualisieren, Löschen
    • Nicht-relational: stützt sich auf den Array-Datentyp oder das serialisierte String-Format
  5. Verschachtelte Intervalle
    • Wie verschachtelte Menge, aber mit Real / Float / Dezimal, so dass die Codierung nicht flüchtig ist (kostengünstig move / insert / delete)
    • Hat echte / float / Dezimaldarstellung / Genauigkeitsprobleme
    • Matrixcodierungsvariante fügt die Vorfahrenkodierung (materialisierter Pfad) für "frei" hinzu, jedoch mit zusätzlicher Trickhaftigkeit der linearen Algebra.
  6. Flacher Tisch
    • Eine modifizierte Adjazenzliste, die jedem Datensatz eine Spalte "Level und Rang" (z. B. Reihenfolge) hinzufügt.
    • Günstig zu iterieren / paginieren
    • Teure Umzug und Löschen
    • Gute Verwendung: Threaded Diskussion - Foren / Blog-Kommentare
  7. Mehrere Abstammungsspalten
    • Spalten: eine für jede Abstammungsstufe, bezieht sich auf alle Eltern bis zur Wurzel, Ebenen unterhalb der Stufe der Gegenstände werden auf NULL gesetzt
    • Günstige Vorfahren, Nachkommen, Ebene
    • Billig einfügen, löschen, bewegen der Blätter
    • Teuer einfügen, löschen, verschieben der internen Knoten
    • Hard Limit, wie tief die Hierarchie sein kann

Datenbankspezifische Hinweise

MySQL

Orakel

PostgreSQL

SQL Server


1061
2017-10-29 00:34


Ursprung


Antworten:


Meine Lieblingsantwort ist wie der erste Satz in diesem Thread vorgeschlagen. Verwenden Sie eine Adjazenzliste, um die Hierarchie zu verwalten, und verwenden Sie geschachtelte Sets zum Abfragen der Hierarchie.

Bisher bestand das Problem darin, dass die Coversion-Methode von einer Adjacacy-List zu Nested-Sets furchtbar langsam war, da die meisten Leute die extreme RBAR-Methode, die als "Push-Stack" bekannt ist, verwenden und als viel zu teuer angesehen wurde das Nirvana der Einfachheit der Wartung durch die Adjazenzliste und die beeindruckende Leistung von Nested Sets zu erreichen. Infolgedessen müssen die meisten Leute sich mit dem einen oder dem anderen zufrieden geben, besonders wenn es mehr als, sagen wir, 100000 Knoten oder so gibt. Die Verwendung der Push-Stack-Methode kann einen ganzen Tag in Anspruch nehmen, um die Konvertierung durchzuführen, die MLM-Benutzer als eine kleine Million-Knoten-Hierarchie betrachten würden.

Ich dachte, ich würde Celko ein wenig Konkurrenz machen, indem ich eine Methode entwarf, um eine Adjazenzliste in verschachtelte Mengen mit Geschwindigkeiten umzuwandeln, die einfach unmöglich erscheinen. Hier ist die Leistung der Push-Stack-Methode auf meinem i5 Laptop.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Und hier ist die Dauer für die neue Methode (mit der Push-Stack-Methode in Klammern).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Ja das ist richtig. 1 Million Knoten wurden in weniger als einer Minute und 100.000 Knoten in weniger als 4 Sekunden konvertiert.

Sie können über die neue Methode lesen und eine Kopie des Codes unter der folgenden URL abrufen. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Ich entwickelte auch eine "voraggregierte" Hierarchie mit ähnlichen Methoden. MLM'ers und Leute, die Stücklisten erstellen, werden besonders an diesem Artikel interessiert sein. http://www.sqlservercentral.com/articles/T-SQL/94570/

Wenn du vorbeischaust, um einen der beiden Artikel anzuschauen, springe einfach in den "Join the discussion" -Link und lass mich wissen, was du denkst.


30



Dies ist eine sehr unvollständige Antwort auf Ihre Frage, aber ich hoffe immer noch nützlich.

Microsoft SQL Server 2008 implementiert zwei Funktionen, die für die Verwaltung hierarchischer Daten äußerst nützlich sind:

  • das HierarchieId Datentyp.
  • allgemeine Tabellenausdrücke, die mit Stichwort.

Schau es dir an "Modellieren Sie Ihre Datenhierarchien mit SQL Server 2008" von Kent Tegels auf MSDN für Starts. Siehe auch meine eigene Frage: Rekursive Abfrage der gleichen Tabelle in SQL Server 2008


21



Dieser Entwurf wurde noch nicht erwähnt:

Mehrere Abstammungsspalten

Obwohl es Einschränkungen gibt, wenn Sie sie ertragen können, ist es sehr einfach und sehr effizient. Eigenschaften:

  • Spalten: eine für jede Abstammungsstufe, bezieht sich auf alle Eltern bis zur Wurzel, Ebenen unterhalb der Ebene der aktuellen Gegenstände sind auf NULL gesetzt
  • Beschränken Sie, wie tief die Hierarchie sein kann
  • Günstige Vorfahren, Nachkommen, Ebene
  • Billig einfügen, löschen, bewegen der Blätter
  • Teuer einfügen, löschen, verschieben der internen Knoten

Hier folgt ein Beispiel - taxonomischer Baum der Vögel, also ist die Hierarchie Klasse / Ordnung / Familie / Gattung / Art - Art ist die unterste Ebene, 1 Reihe = 1 Taxon (was den Arten im Falle der Blattknoten entspricht):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

und das Beispiel der Daten:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Das ist großartig, weil Sie auf diese Weise alle erforderlichen Operationen auf sehr einfache Weise ausführen können, solange die internen Kategorien ihre Ebene in der Struktur nicht ändern.


20



Adjazenzmodell + geschachtelte Mengenmodell

Ich ging dafür, weil ich neue Elemente leicht in den Baum einfügen konnte (Sie brauchen nur die ID eines Zweigs, um ein neues Element einzufügen) und es auch ziemlich schnell abzufragen.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • Jedes Mal, wenn Sie alle Kinder eines Elternteils benötigen, fragen Sie einfach nach parent Säule.
  • Wenn Sie alle Nachkommen eines Elternteils benötigen, fragen Sie nach Artikeln, deren lft zwischen lft und rgt von Eltern.
  • Wenn Sie alle Eltern eines beliebigen Knotens bis zum Stamm des Baums benötigen, fragen Sie nach Elementen mit lft niedriger als die des Knotens lft und rgt größer als die des Knotens rgt und sortiere das durch parent.

Ich musste den Zugriff auf den Baum beschleunigen und den Baum schneller durchsuchen als Inserts, deshalb habe ich das gewählt

Das einzige Problem ist, das zu beheben left und right Spalten beim Einfügen neuer Elemente. Nun, ich habe eine gespeicherte Prozedur dafür erstellt und sie jedes Mal aufgerufen, wenn ich ein neues Element eingefügt habe, was in meinem Fall selten war, aber es ist wirklich schnell. Ich habe die Idee aus dem Buch von Joe Celko, und die gespeicherte Prozedur und wie ich darauf gekommen bin, wird hier in DBA SE erklärt https://dba.stackexchange.com/q/89051/41481


13



Wenn Ihre Datenbank Arrays unterstützt, können Sie auch eine Herkunftsspalte oder einen materialisierten Pfad als Array mit übergeordneten IDs implementieren.

Speziell mit Postgres können Sie dann die Mengenoperatoren verwenden, um die Hierarchie abzufragen und eine ausgezeichnete Leistung mit GIN-Indizes zu erzielen. Dies macht das Auffinden von Eltern, Kindern und der Tiefe in einer einzigen Abfrage ziemlich trivial. Updates sind auch ziemlich überschaubar.

Ich habe eine vollständige Beschreibung der Verwendung Arrays für materialisierte Pfade wenn du neugierig bist.


10



Dies ist wirklich eine quadratische Pflock, Rundloch Frage.

Wenn relationale Datenbanken und SQL der einzige Hammer sind, den Sie verwenden möchten oder wollen, dann sind die bisher geposteten Antworten angemessen. Warum nicht ein Werkzeug verwenden, das für die Verarbeitung hierarchischer Daten entwickelt wurde? Grafikdatenbank sind ideal für komplexe hierarchische Daten.

Die Ineffizienzen des relationalen Modells zusammen mit den Komplexitäten einer beliebigen Code / Abfrage-Lösung, um ein Graph / hierarchisches Modell auf ein relationales Modell abzubilden, sind den Aufwand im Vergleich zu der Leichtigkeit, mit der eine Graphdatenbanklösung das gleiche Problem lösen kann, einfach nicht wert.

Betrachten Sie eine Stückliste als eine allgemeine hierarchische Datenstruktur.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Kürzester Pfad zwischen zwei Unterbaugruppen: Einfacher Graph-Traversal-Algorithmus. Akzeptable Pfade können basierend auf Kriterien qualifiziert werden.

Ähnlichkeit: Was ist der Grad der Ähnlichkeit zwischen zwei Baugruppen? Führen Sie eine Traversierung auf beiden Teilbäumen durch, um die Kreuzung und Vereinigung der beiden Teilbäume zu berechnen. Der Prozentsatz ähnlich ist der Schnittpunkt geteilt durch die Union.

Transitive SchließungGehen Sie den Unterbaum und summieren Sie das interessierende Feld, z. "Wie viel Aluminium ist in einer Unterbaugruppe?"

Ja, Sie können das Problem mit SQL und einer relationalen Datenbank lösen. Es gibt jedoch viel bessere Ansätze, wenn Sie bereit sind, das richtige Werkzeug für den Job zu verwenden.


7



Ich verwende PostgreSQL mit Verschlusstabellen für meine Hierarchien. Ich habe eine universelle gespeicherte Prozedur für die gesamte Datenbank:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Dann erstelle ich für jede Tabelle, in der ich eine Hierarchie habe, einen Trigger

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Zum Füllen einer Verschlusstabelle aus einer vorhandenen Hierarchie verwende ich diese gespeicherte Prozedur:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Closure-Tabellen sind mit 3 Spalten definiert - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Es ist möglich (und ich rate sogar), Datensätze mit demselben Wert für ANCESTOR und DESCENDANT zu speichern und einen Wert von 0 für DEPTH. Dies vereinfacht die Abfragen zum Abrufen der Hierarchie. Und sie sind wirklich sehr einfach:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

4