Was sind die Optionen für die Speicherung von hierarchischen Daten in einer relationalen Datenbank?

Meine Lieblings-Antwort ist als das, was der erste Satz in diesem thread vorgeschlagen. Verwenden Sie ein Angrenzens Liste, die Hierarchie zu halten und verwenden Sie Verschachtelte Sätze, zum Abfragen der Hierarchie.

Das problem war bis jetzt, dass die coversion-Methode von einem Adjacecy Liste zu Nested Sets wurde furchtbar langsam, weil die meisten Menschen nutzen die extreme RBAR Methode bekannt als "Push-Stapel", um die Konvertierung und wurde als viel zu teuer zu erreichen das Nirwana der Einfachheit der Wartung durch die Nähe Liste und die tolle Leistung von Nested Sets. Als Ergebnis, die meisten Menschen müssen, um sich für die eine oder die andere, besonders wenn es mehr als, sagen wir, eine lausige 100.000 Knoten oder so. Mit der push-stack Methode kann einen ganzen Tag, um die Konvertierung zu tun, was MLM ' ers würden erwägen, um eine kleine Millionen-Knoten-Hierarchie.

Ich dachte, ich würde geben Celko ein bisschen Wettbewerb durch kommen mit einer Methode zum konvertieren eines Angrenzens Liste zu Nested sets bei Geschwindigkeiten, die scheinen einfach unmöglich. Hier ist die Leistung des 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 Millionen Knoten umgewandelt in weniger als einer minute und 100.000 Knoten in unter 4 Sekunden.

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

Ich entwickelte auch eine "pre-aggregierten" Hierarchie mit ähnlichen Methoden. MLM ' ers und die Leute, die Stücklisten werden vor allem Interessierte in diesem Artikel.
http://www.sqlservercentral.com/articles/T-SQL/94570/

Wenn Sie von zu stoppen, um einen Blick auf entweder den Artikel, den Sprung in die "diskutieren" - link und lassen Sie mich wissen, was Sie denken.

InformationsquelleAutor

Dieser Entwurf wurde noch nicht erwähnt:

Mehrere herkunftsspalten

Obwohl es seine Grenzen hat, wenn Sie tragen können, Sie, es ist sehr einfach und sehr effizient. Features:

• Spalten: eine für jede Linie Ebene bezieht sich auf alle Eltern, die bis zu der Wurzel, werden die Ebenen unterhalb des aktuellen items' - Ebene auf NULL gesetzt
• Grenze, wie tief die Hierarchie
• Günstigen Vorfahren, Nachkommen, Ebene
• Günstigen einfügen, löschen, verschieben der Blätter
• Teuer, einfügen, löschen, verschieben von dem internen Knoten

Hier folgt ein Beispiel - taxonomischen Baum der Vögel sind, so dass die Hierarchie-Klasse/Ordnung/Familie/Gattung/Spezies - Spezies ist die niedrigste Ebene 1 row = 1 taxon (das entspricht Art in der Fall of the leaf nodes):

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 ''
);

am 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, denn auf diese Weise erreichen Sie alle notwendigen Operationen auf sehr einfache Weise, wie lange, wie die internen Kategorien ändern sich nicht Ihrer Ebene in der Struktur.

InformationsquelleAutor

Wenn Ihre Datenbank unterstützt arrays, Sie können auch implementieren Sie eine Linie Spalte oder materialisierte Pfad als array des parent-ids.

Speziell mit Postgres verwenden Sie dann die set-Operatoren zum Abfragen der Hierarchie, und erhalten Sie ausgezeichnete Leistung mit GIN-Indizes. Dies macht die Suche nach Eltern, Kinder und Tiefe ziemlich trivial in einer einzigen Abfrage. Updates sind ziemlich überschaubar als gut.

Habe ich eine volle schreiben, der mit arrays für die materialisierte Pfade wenn du neugierig bist.

InformationsquelleAutor

Ich bin mit PostgreSQL mit Verschluss-Tabellen für mein Hierarchien.
Ich habe eine universal-gespeicherte Prozedur, die 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 für jede Tabelle, wo ich eine Hierarchie, bei der ich einen trigger erstellen

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');

Für das Auffüllen einer Schließung Tabelle aus vorhandenen Hierarchie ich diese gespeicherte Prozedur verwenden:

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;
$$;

Schließung Tabellen definiert sind, mit 3 Spalten - ANCESTOR_ID, DESCENDANT_ID, TIEFE. Es ist möglich (und ich auch Beratung) zum speichern der Datensätze mit demselben Wert für VORFAHREN und NACHKOMMEN, und ein Wert von null in die TIEFE. Dies wird zu einer Vereinfachung der Abfragen für den Abruf der Hierarchie. Und Sie sind in der Tat 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;

InformationsquelleAutor