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:

  • Lebensmittel
    • Getränke
    • Gemüse
      • Broccoli
      • Kohlrabi
    • Obst
      • Pfirsich
      • Orange
  • Kleidung
    • Herrenkleidung
    • Damenkleidung

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.

Jan hat 152 Beiträge geschrieben

66 Kommentare zu “Nested Sets – Hierarchische Strukturen und Bäume in MySQL

  1. albertus sagt:

    Das Löschen einer Kategorie inklusive Unterkategorien ist auf einen ersten fixen Blick meinerseits vermutlich falsch: Es wird irgendwie $RGT und $LFT von allen “rechts” stehenden Kategorien abgezogen, anstatt nur die Breite der gelöschten Kategorie ($RGT-$LFT), in Klammern(!), abzuziehen. In der Tat aber eine schöne Erklärung. Wer den falschen Code übernimmt, demonstriert damit, dass er selber das Prinzip nicht ganz verstanden hat 😉

  2. Jan sagt:

    @alsahmut: Ich verstehe Dich leider nicht ganz. Meinst Du 2 Eltern-Kategorien?
    Oder erkläre Deine Frage einfach mal an einem Beispiel.

  3. alsahmut sagt:

    Naja eine Baumstruktur verzweigt sich immer weiter, ich will abwer das sie an manchen Stellen auch wieder zusammenwächst.
    Ein Kohlrabi ist der Kategorie Gemüse zugeordnet, was wenn ich aber Kohlrabi der Kategorie Gemüse und Kategorie Obst zuordnen will?

  4. Jan sagt:

    Nun, das macht ein Baum nunmal nicht. Das ist das gleiche wie 2 Elternkategorien. Sowas gibt es in einem Baum nicht – und ein Kohlrabi ist eben auch nur Gemüse, kein Obst.
    Geht also innerhalb eines Nested Sets nicht.

  5. Jan sagt:

    Speichere die Parents doch einfach in einer Extra-Tabelle. Dann kann jeder Knoten mehrere Elternknoten haben – eine 1:n-Beziehung also.

  6. alsahmut sagt:

    Die Knoten sind dann aber selber wieder Elternknoten.. Ich schau mal ob es passende rekursive Abfragen für MySQL gibt.

  7. Serkan sagt:

    Hallo,

    ein sehr guter Ansatz um eine Baumstruktur darzustellen. Wichtig meiner Meinung nach, das Performante auslesen von Daten!

    Für die Nörgler unter uns: Ihr solltet nicht alle so nörgeln! Mal lieber hinsetzen und bissel Coden und eure fine tuning Wünsche einfach umsetzen!

    Wie schon einstein sagte, Phantasie ist wichtiger als Wissen, denn Wissen ist begrenzt.

    Ich muss zugeben, das ich nicht soviel allgemeinwissen habe aber dafür eine sehr größe Vorstellungskraft und das hilft mir ungemein beim Programmieren!

    Gruß

    Serkan

  8. Simon sagt:

    Hallo!

    Ich bin mir nicht ganz sicher, aber das Entfernen von Kategorien scheint so nicht zu funktionieren wie angegeben:

    UPDATE kategorien SET lft=lft-$RGT-$LFT+1 WHERE lft>$RGT;
    UPDATE kategorien SET rgt=rgt-$RGT-$LFT+1 WHERE rgt>$RGT;

    Weil du die Round() Funktion entfernt hast, fehlen nun auch die Klammern. Richtig wäre meiner Meinung nach:

    UPDATE kategorien SET lft=lft-($RGT-$LFT+1) WHERE lft>$RGT;
    UPDATE kategorien SET rgt=rgt-($RGT-$LFT+1) WHERE rgt>$RGT;

    Ansonsten kann ich mich nur anschließen, das ist ein super Artikel!

  9. Kurt H. sagt:

    Danke für die ausführliche Erklärung! Mit dem Bild mit den verschachtelten Balken kann man sich meiner Meinung nach sehr gut vorstellen, was wann wie verschoben werden muss.

  10. Moritz M. sagt:

    Moin,
    zunächst einmal danke für dieses schöne Tutorial. Ich habe das Grund Prinzip der Nested Sets nun denke ich sehr gut verstanden.
    Allerdings habe ich noch ein zwei Fragen zu der MYSQL Syntax. Ich muss dazu sagen, dass ich noch nicht allzu lange mit MYSQL arbeite und mich von daher noch nicht allzu gut damit auskenne. Mir ist noch nicht ganz klar was “n.name” oder auch “p.lft” etc. beduetet. Die Tabelle hat ja nur die Spalten “name” und “lft” was also bedeuten “n.” und “p.”?
    Vielen Dank schon einmal und noch einen schönen Rest Weihnachtsabend.

  11. HI,

    (ich glaub) du hast einen schwerwiegenden Fehler beim Löschen eines Knotens, wobei die Kinder nachrutschen…

    mit dem Statement:
    DELETE FROM kategorien WHERE lft BETWEEN $LFT AND $RGT;
    löscht du den ganzen Unterbaum und versuchst anschließend die Knoten des Unterbaums zu “verschieben”

    Viele Grüße

Eine Antwort schreiben

Ihre E-Mail-Adresse wird nicht veröffentlicht. Benötigte Felder sind markiert mit *

You may use these HTML tags and attributes: <a href=""> <blockquote cite=""> <pre lang=""> <b> <strong> <i> <em>