Sie sind hier : sebastian1012.bplaced.net/ homepage-neu / kreuz-und-quer / tutorials-info-neuigkeiten-datenbank / nested-sets-hierarchische-strukturen-und-baeume-in-mysql.php

Nested Sets – Hierarchische Strukturen und Bäume in MySQL

Wir haben bereits gesehen, dass das rekursive Abfragen eines Baumes, der über Parent-IDs verwirklicht wurde, sehr langsam ist. Dieses Problem soll nun umgangen werden, damit wir mit nur einer SELECT-Abfrage und ohne jegliche Rekursion (auch kein connect by prior, wie es in Oracle möglich ist) alle Datensätze und die dazugehörigen Ebenen erhalten.

Das Modell der Nested Sets stammt von Joe Celko. Mittlerweile sind zum ursprünglichen Verfahren noch ein paar Kniffe hinzugekommen, die Grundidee aber ist gleich geblieben – und aus Performance-Sicht ein wahrer Segen.

Das Konzept
Arne Klempert beschreibt das Verfahren meiner Meinung nach am verständlichsten, deshalb möchte ich dieses Beitrag auf seine Ausführungen stützen.
Das Konzept von Nested Sets basiert auf Mengen. Wir stellen uns allerdings weniger das Mengenmodell vor sondern vielmehr einen Zahlenstrahl (zum besseren Nachvollziehen genügt auch ein Lineal). Zahlenstrahl-Modell der Nested SetsDen Kategorien wurde ein bestimmter Bereich auf diesem Zahlenstrahl zugewiesen. Im Bild ist die Beziehung von Säugetierklasen dargestellt. Die oberste Kategorie Säugetiere hat einen Bereich von 1 bis 10. Innerhalb dieses Bereichs sind alle Kind-Kategorien von Säugetiere – so z.B. Primaten (Bereich 2 bis 7). Und Unterkategorien der Primaten sind wiederum im Bereich zwischen 2 und 7, z.B. Halbaffen (3 – 4) und Affen (5 – 6).
Hieran wird das Konzept deutlich: Alle Kategorien, die unter einer übergeordneten Kategorie H liegen, haben einen Zahlenbereich innerhalb des zu H zugewiesenen Bereiches.

In der Datenbank wird das über 2 zusätzliche Spalten umgesetzt, die wir der Kategorie-Tabelle hinzufügen: lft (die linke Grenze des Bereiches einer Kategorie) und rgt (die rechte Grenze).
Wie baut man das ganze nun auf?

Der Aufbau
Als Beispiel wollen wir wieder die Online-Shop-Kategorien wählen. Hier nochmal die Struktur:

Unsere Kategorien-Tabelle sieht so aus:

CREATE TABLE kategorien (     ID    INT(12)      UNSIGNED NOT NULL AUTO_INCREMENT,     name  VARCHAR(50)  NOT NULL,     lft   INT(12)      UNSIGNED NOT NULL,     rgt   INT(12)      UNSIGNED NOT NULL,     PRIMARY KEY (id),     KEY lft (lft),     KEY rgt (rgt) );

Wenn wir die erste Kategorie hinzufügen wollen, tun wir dies mittels

INSERT INTO kategorien (name,lft,rgt) VALUES  ('Lebensmittel',1,2);

Wieso lft=1 und rgt=2? Wenn die erste Kategorie eingefügt wird, bekommt diese Kategorie einfach den Bereich 1 und 2 – ohne Begründung 🙂
Nun wollen wir Gemüse unter die Lebensmittel hängen. Dazu muss natürlich der Bereich der Lebensmittel erweitern werden, damit der Grundsatz wieder passt, dass alle Unterkategorien innerhalb des Bereiches der Oberkategorie liegen.

UPDATE kategorien SET rgt=rgt+2 WHERE rgt >= 2; INSERT INTO kategorien (name,lft,rgt) VALUES ('Gemüse',2,3);

Das Update schafft den nötigen Platz (neuer Bereich von Lebensmittel ist 1-4). Das Insert hat als lft-Wert den alten rgt-Wert der übergeordneten Kategorie (nämlich 2) und als rgt-Wert bekommt die neue Kategorie den alten rgt-Wert der übergeordneten Kategorie + 1.
Wenn wir nun den Bruder Obst einfügen, führen wir die gleiche Query wie oben wieder aus, wobei der alte rgt-Wert der übergeordneten Kategorie (Lebensmittel) als Variable $RGT (in diesem Beispiel 4) angenommen wird (wenn nicht bekannt, einfach per SELECT-Statement vorher abfragen und speichern).

UPDATE kategorien SET rgt=rgt+2 WHERE rgt >= $RGT; INSERT INTO kategorien (name,lft,rgt) VALUES ('Obst',$RGT,$RGT+1);

Wir haben nun also folgende Tabelle:

ID name lft rgt
1 Lebensmittel 1 6
2 Gemüse 2 3
3 Obst 4 5

Wenn wir nun aber nicht immer sofort alle Kind-Kategorien hinzufügen, sondern merken, dass wir zwischendurch eine vergessen haben, müssen auch die lft-Werte upgedatet werden. Beispielsweise wollen wir nun Broccoli hinzufügen. $RGT ist also 3, da die übergeordnete Kategorie Gemüse zu diesem Zeitpunkt diesen rgt-Wert hat.

UPDATE kategorien SET rgt=rgt+2 WHERE rgt >= $RGT; UPDATE kategorien SET lft=lft+2 WHERE lft > $RGT; INSERT INTO kategorien (name,lft,rgt) VALUES ('Broccoli',$RGT,$RGT+1);

Dieses Statement ist dann auch das entscheidende beim Eintragen. Die vorhergehenden sollten nur mit geringerer Komplexität das Konzept verdeutlichen. Die gleichen Ergebnisse wären aber entstanden, wenn wir diese 3 Queries angewendet hätten.

Um etwas Performance noch herauszuholen, könnte man die beiden Updates noch etwas entschärfen, da bei den Datensätzen, wo der lft-Wert > $RGT gilt, dass auch der rgt-Wert &gt $RGT (da rgt immer größer als lft ist):

UPDATE kategorien SET rgt=rgt+2, lft=lft+2 WHERE lft > $RGT; UPDATE kategorien SET rgt=rgt+2 WHERE rgt = $RGT;

Dadurch haben wir immernoch 2 Updates, aber es müssen weniger Einzel-Updates durchgeführt werden. Bei der oben genannten Variante sind es fürs erste Update N – $RGT +1 Datensätze und fürs zweite N – $RGT = (N-$RGT+1) + (N – $RGT) = 2*N – 2*$RGT +1.
Die schnellere Variante braucht nur N – $RGT Datensätze fürs erste Update und 1 fürs 2. Update aktualisieren. Das sind N – $RGT + 1. Und es gilt N – $RGT + 1 < 2*N - 2*$RGT + 1. Man braucht also N - $RGT Einzelupdates weniger. Wenn wir eine neue Hauptkategorie hinzufügen möchten, müssen wir den aktuell größten rgt-Wert der Tabelle ermitteln und diesen um 1 erhöhen, um den lft-Wert bzw. um 2 erhöhen um den rgt-Wert der neuen Hauptkategorie (keine übergeordnete Kategorie) zu ermitteln.

ID name lft rgt
1 Lebensmittel 1 16
2 Gemüse 2 7
3 Obst 8 13
4 Broccoli 3 4
5 Kleidung 17 22
6 Kohlrabi 5 6
7 Pfirsich 9 10
8 Herrenkleidung 18 19
9 Damenbekleidung 20 21
10 Orange 11 12
11 Getränke 14 15

Was ist nun gewonnen?
Es ist recht aufwändig die Nested-Set-Struktur zu erstellen, aber sie ist unschlagbar beim Auslesen. Deshalb wird dieses Modell auch eher für Anwendungen empfohlen, die recht selten geändert werden aber umso öfter gelesen werden. Was „recht selten“ bedeutet, muss jeder selbst entscheiden, denn es ist ein Unterschied, ob die Kategorien einmal im Monat verändert werden oder ob stündlich eine Veränderung in der Struktur geschieht. Im Grunde ist sie aber für fast alle Anwendungsgebiete im Web, die eine Hierarchie in einer Datenbank ablegen geeignet.

Für das Auslesen des kompletten Baums inklusive der Ebenen ist nur noch eine Abfrage nötig:

SELECT n.name, COUNT(*)-1 AS ebene FROM kategorien AS n,kategorien AS p WHERE n.lft BETWEEN p.lft AND p.rgt GROUP BY n.lft ORDER BY n.lft;

Dadurch erhält man das gewünschte Ergebnis, dass zwischen 2 Kategorien der gleichen Ebene ersmtal alle Kind-Kategorien kommen. Somit kann man das Ergebnis wunderbar zu der visualisierten Baumstruktur verwenden.

Zusätzlich lassen sich aus dem Baum noch mehr Informationen ermitteln:

SELECT n.*, round((n.rgt-n.lft-1)/2,0) AS countUntergeordnete, COUNT(*)-1+(n.lft>1) AS ebene, ((MIN(p.rgt)-n.rgt-(n.lft>1))/2) > 0 AS countVorgaengerGleicheEbene, (((n.lft-MAX(p.lft)>1))) AS countNachfolgerGleicheEbene FROM kategorien n, kategorien p WHERE n.lft BETWEEN p.lft AND p.rgt AND (p.id != n.id OR n.lft = 1) GROUP BY n.id ORDER BY n.lft;

Solch komplexe Abfragen sind allerdings eher selten nötig, aber möglich.

Wir wollen uns lieber mit für die Praxis wichtigeren Abfragen beschäftigen:
Zum Beispiel für Breadcrumbs ist es noch wichtig alle übergeordneten Kategorien zu ermitteln von einer Unterkategorie ausgehend. Wir möchten beispielsweise den kompletten Baum über der Kategorie Pfirsich (ID: 7) ermitteln.

SELECT p.* FROM kategorien n, kategorien p WHERE n.lft BETWEEN p.lft AND p.rgt AND n.id = 7 ORDER BY n.lft;

Als Ergebnis erhält man Lebensmittel > Obst > Pfirsich (als 3 Datensätze) in der gewünschten Reihenfolge von der Wurzel bis zur Kategorie Pfirsich.

Entfernen von Kategorien
Wichtig ist in der Praxis noch, wie man Kategorien wieder entfernen kann.
Sollen alle Kategorien unter einer bestimmten (bzw. nur diese eine, wenn sie keine Kinder hat) gelöscht werden, sind diese Befehle nützlich ($LFT und $RGT sind die lft- und rgt-Werte der zu löschenden Kategorie):

DELETE FROM kategorien WHERE lft BETWEEN $LFT AND $RGT; UPDATE kategorien SET lft=lft-$RGT-$LFT+1 WHERE lft>$RGT; UPDATE kategorien SET rgt=rgt-$RGT-$LFT+1 WHERE rgt>$RGT;

Arne Klempert beschreibt es zwar mit einer zusätzlichen ROUND-Funktion, allerdings ist mir nicht klar weshalb, denn bei Addition und Subtraktion mit natürlichen Zahlen kommt stets eine natürliche Zahl heraus.
Wenn darunterliegende Kategorien nicht mit gelöscht werden sollen, sondern eine Ebene nach oben geschoben, ist folgende Query die richtige:

DELETE FROM kategorien WHERE lft BETWEEN $LFT AND $RGT; UPDATE kategorien SET lft=lft-1, rgt=rgt-1 WHERE lft BETWEEN $LFT AND $RGT; UPDATE kategorien SET lft=lft-2 WHERE lft>$RGT; UPDATE kategorien SET rgt=rgt-2 WHERE rgt>$RGT;

Ich hoffe ich konnte das Konzept von Nested Sets etwas näherbringen, denn ich habe die Erfahrung gemacht, dass selbst langjährige Datenbank-Administratoren von diesem Modell nichts wussten und ganz erstaunt waren. Ich empfehle auf jeden Fall die Lektüre Nested Sets – Verschachtelte Bäume mit MySQL.