php-resource.de

MySQL Tutorial: Das 'Nested Sets' Modell - Bäume mit SQL

Dieses Tutorial beschreibt die 'Nested Sets'-Technik, mit der man solche Bäume mit SQL performant konstruieren kann.

|23.02.2011 | gorski@ | 47046 | KAT : MySQL | | Kommentare 2


3

4

Der Aufbau eines Nested Sets-Baumes

Als Implementation der Nested Sets mit SQL realisieren wir im Folgenden die Grundstruktur eines "Threaded Forum" also eines Forums in dem Antworten auf ein Posting baumartig dargestellt werden können.

Als Datenquelle für unsere Implementation eignet sich eine beliebige SQL-Datenbank - bei der Überprüfung der Beispiele wurde die schnelle und kostenlose MySQL-Datenbank verwendet. Bei anderen Datenbanken sind die SQL-Statements bzw. -Funktionen (z.B. LAST_INSERT_ID(), ggf. das Locking oder Sequenzen und Trigger anstatt AUTO_INCREMENT) auf die Gegebenheiten der jeweiligen Datenbank anzupassen. Wenn das RDBMS Transaktionen beherrscht (COMMIT, ROLLBACK) sollte man selbstverständlich nicht vergessen diese ergänzend zu den Beispielen zu implementieren.

Unsere simple Thread-Tabelle:

CREATE TABLE node (
    node_id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
    root_id INT(10) UNSIGNED NOT NULL,
    payload VARCHAR(64)      NULL,
    lft     INT(10) UNSIGNED NOT NULL,
    rgt     INT(10) UNSIGNED NOT NULL,

    PRIMARY KEY (node_id),
    KEY root_id (root_id)
);

Um verschiedene Threads (Bäume) voneinander unterscheiden zu können, führen wir in jedem Datensatz die root_id mit. Die root_id ist bei jedem Datensatz, der zu einem Thread gehört, gleich und mit der node_id (dem Primärschlüssel) des allerersten Postings eines Threads identisch.


Die Baumwurzel - das Rootposting:

Die einfachste Operation in unserem Baum ist das Einfügen eines Root- resp. Wurzelpostings. Diese setzt sich aus einem INSERT und einem UPDATE-Statement zusammen. Das UPDATE-Statement wird benötigt, um die bereits erwähnte root_id dem Wert der node_id anzupassen, da der Wert der node_id automatisch vergeben wird (AUTO_INCREMENT bei MySQL) und wir diesen vor der INSERT-Operation nicht kennen können:

LOCK TABLES node WRITE;

INSERT INTO node ( payload, lft, rgt )
          VALUES ( 'A - Das Wurzelposting', 1, 2 );

UPDATE node
   SET root_id = LAST_INSERT_ID()
 WHERE node_id = LAST_INSERT_ID();

UNLOCK TABLES;

Das wenig spektakuläre Ergebnis sieht zunächst folgendermaßen aus:

+---------+---------+-----------------------+-----+-----+
| node_id | root_id | payload               | lft | rgt |
+---------+---------+-----------------------+-----+-----+
|       1 |       1 | A - Das Wurzelposting |   1 |   2 |
+---------+---------+-----------------------+-----+-----+

Ein Wurzelposting ohne Kinder wird immer durch die Zahlen LFT = 1 und RGT = 2 repräsentiert.


Reply - der Baum wird erweitert:

Die Erweiterung des Baumes gestaltet sich ein wenig trickreicher, wenn auch nicht undurchschaubar, wenn man das visuelle Modell der Nested Sets verstanden hat.

Um die korrekte Erweiterung des Baumes zu gewährleisten, kommen ebenfalls mehrere SQL-Statements zum Einsatz. Zwei davon stellen die Integrität der LFT-RGT-Zahlenpaare sicher, das dritte speichert den neuen Datensatz (das Reply) in der Datenbanktabelle ab. Als Eingangsparameter benötigen wir die root_id (nicht die node_id!) - d.h. die Thread-Zugehörigkeit - und die LFT- und RGT-Zahlen des Datensatzes an den der neue Knoten "angehängt" werden soll. Im folgendem Beispiel sind es die Werte:

root_id = 1   (Variable: V_ROOT_ID)
    lft = 1   (Variable: V_LFT)
    rgt = 2   (Variable: V_RGT)

... also die Daten des Wurzelpostings A. Um den Bezug zum nächsten Beispiel herzustellen wurden diese Werte als imaginäre Variablen (V_ROOT_ID, V_LFT und V_RGT) benannt. Diese Daten müssen vor der Einfügeoperation (z.B. durch ein entsprechendes SELECT-Statement für den zuerweiternden Knoten) ermittelt werden. Da üblicherweise eine übergeordnete Programmiersprache die Steuerung der SQL-Statements übernimmt, dürfte das Beschaffen dieser Werte kein Problem darstellen.

Zusätzlich gewährleistet hier das Locking der Tabellen, dass es zu keiner Zeit zu Kollisionen mir einem anderen Prozeß kommt, der eine ähnliche Einfügeoperation beabsichtigt:

LOCK TABLES node WRITE;

UPDATE node
   SET lft      =  lft + 2
 WHERE root_id  =  V_ROOT_ID
   AND lft      >  V_RGT
   AND rgt      >= V_RGT;
   
UPDATE node
   SET rgt      =  rgt + 2
 WHERE root_id  =  V_ROOT_ID
   AND rgt      >= V_RGT;
   
INSERT INTO node ( root_id, payload, lft, rgt )
          VALUES ( V_ROOT_ID, 'B - Reply auf "A"', V_RGT, V_RGT + 1 );

UNLOCK TABLES;

Spätestens an dieser Stelle wird es deutlich warum sich Nested Sets im Allgemeinen nur für Strukturen eignen, auf die zum größten Teil lesend zugegriffen wird: Die Erweiterung der Baustruktur ist relativ "teuer" - sie kostet viel Zeit, da u.U. sehr viele Knoten eines Baumes verändert werden müssen. Wie teuer so eine Erweiterung des Baumes ist, hängt natürlich von der Komplexität der Struktur ab.

Leider muß in MySQL die komplette Tabelle temporär für den Schreibzugriff gesperrt werden, da uns im Normallfall hier keine Transaktionen zur Verfügung stehen.

Das Ergebnis in der Datenbank:

+---------+---------+-----------------------+-----+-----+
| node_id | root_id | payload               | lft | rgt |
+---------+---------+-----------------------+-----+-----+
|       1 |       1 | A - Das Wurzelposting |   1 |   4 |
|       2 |       1 | B - Reply auf "A"     |   2 |   3 |
+---------+---------+-----------------------+-----+-----+

Wiederholt man diese "Ergänzungs-Query" ein weiteres Mal mit den Werten LFT- und RGT-Werten des neuen Knotens (B)

root_id = 1   (Variable: V_ROOT_ID)
    lft = 2   (Variable: V_LFT)
    rgt = 3   (Variable: V_RGT)

mit der Absicht dem Knoten B seinerseits einen Kind-Knoten hinzuzufügen, so erhält man:

+---------+---------+-----------------------+-----+-----+
| node_id | root_id | payload               | lft | rgt |
+---------+---------+-----------------------+-----+-----+
|       1 |       1 | A - Das Wurzelposting |   1 |   6 |
|       2 |       1 | B - Reply auf "A"     |   2 |   5 |
|       3 |       1 | C - Reply auf "B"     |   3 |   4 |
+---------+---------+-----------------------+-----+-----+

Als letztes Beispiel fügen wir dem Knoten B noch ein zusätzliches "Reply" hinzu, und beobachten die Änderung in der Datenbank. Das LFT-RGT-Zahlenpaar für den Knoten B hat sich mittlerweile geändert, so dass unsere Ausgangswerte für die Einfügeoperation wie folgt aussehen:

root_id = 1   (Variable: V_ROOT_ID)
    lft = 2   (Variable: V_LFT)
    rgt = 5   (Variable: V_RGT)

Nachdem die Query ausgeführt wurde finden wir folgendes zufriedenstellendes Ergebnis vor:

+---------+---------+-----------------------+-----+-----+
| node_id | root_id | payload               | lft | rgt |
+---------+---------+-----------------------+-----+-----+
|       1 |       1 | A - Das Wurzelposting |   1 |   8 |
|       2 |       1 | B - Reply auf "A"     |   2 |   7 |
|       3 |       1 | C - Reply auf "B"     |   3 |   4 |
|       4 |       1 | D - 2. Reply auf "B"  |   5 |   6 |
+---------+---------+-----------------------+-----+-----+
Navigation -> Seitenanzahl : (4)

  «  1 2 3 4  » 
Kommentare zum Tutorial
Tutorial kommentieren
 
25.02.2010 14:59:07 Schöne SQL-Erweiterung http://www.php-resource.de/forum/blogs/amicanoctis/25-nested-set-move-s ...
25.05.2009 15:47:58 Das 'Nested Sets' Modell verwenden wir häufig in unseren Projekten. Dieses Tutorial war gerade ...

Alle Kommentare anzeigen ...
 
Über den Autor
gorski@

gorski@

Status
Premium Mitglied

Beruf
Unbekannt

Mitglied seit:
30.04.2009

letzte Aktivität
04.06.2009

 

Tutorial bewerten

Hat Ihnen dieses Tutorial gefallen? Dann bewerten Sie es jetzt! Fünf Sterne bedeutet "Sehr gut", ein Stern "Unzureichend".



 

aktuelle Artikel

Die RIGID-FLEX-Technologie

Die RIGID-FLEX-TechnologieDie sogenannte "Flexible Elektronik" , oftmals auch als "Flexible Schaltungen" bezeichnet, ist eine zeitgemäße Technologie zum Montieren von elektronischen Schaltungen.

06.12.2018 | Neu | Berni

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Neu | Berni