IPC 2012 Spring

Nested Sets – Hierarchische Strukturen und Bäume in MySQL

MySQL von Jan

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.

Post to Twitter Beitrag twittern

Schlagwörter: , , , , , ,

65 Kommentare bisher »

  1. PHP Performance » Hierarchische Strukturen und Bäume in MySQL (Rekursion) sagt

    am 17. April 2007 @ 13:31

    [...] langsam. Wenn Sie schon etwas fortgeschrittener im Umgang mit SQL sind, empfehle ich deshalb das Nested Sets-Modell, das wesentlich besser skaliert. db mysql performance rekursion schleife Kommentar schreiben | [...]

  2. Artemis sagt

    am 17. Mai 2007 @ 16:18

    Ich hatte mich vorher schon einmal mit Nested Sets befasst, das ganze aber nicht wirklich verstanden. Dieser Artikel, und vor allem das Bild vom Anfang, haben mir das ganze aber klar gemacht.

    Danke dafür,
    Artemis

  3. "Sie sind hier" - Realisieren - XHTMLforum sagt

    am 30. Mai 2007 @ 11:20

    [...] die Struktur vernünftig in der Datenbank zu realisieren: Nested Sets – Hierarchische Strukturen und Bäume in MySQL » Beitrag » PHP Performance __________________ Applikations-Programmierung: BlitzMax, BlitzPlus, C# Webentwicklung: PHP, [...]

  4. Nested Sets - oder wie man Baumstrukturen effizient in Datenbanken hält » Von juniperus » Beitrag » GUXX sagt

    am 30. Mai 2007 @ 22:24

    [...] in SQL Bibliothek für Nested Sets Sehr Umfangreicher Artikel zu Nested Sets (englisch) Umfangreicher Artikel zu "Nested Sets" [...]

  5. Scar sagt

    am 17. Juli 2007 @ 17:47

    ich bastel grad an einem kleinen cms Projekt zum Spaß (und lernen) rum und wollte eigentlich im Netz rausfinden wie man ordentliche Bäume via Rekursion baut (hab eszwar hinbekommen, wollte aber mal schaun, was ich verbessern kann – ich hasse Rekursion), da bin ich hier rauf gestoßen. Tolles Konzept und tolle Erklärung von dir, danke. Werd ich in jedem Fall verwenden.

    Mfg

  6. Suche einen bestimmten Artikel zu SQL - XHTMLforum sagt

    am 26. August 2007 @ 11:20

    [...] Sets – Wikipedia Nested Sets – Hierarchische Strukturen und Bäume in MySQL » Beitrag » PHP Performance Nested Sets &ndash; Verschachtelte Bäume mit MySQL – Arne Klempert __________________ [...]

  7. michael sagt

    am 11. September 2007 @ 20:53

    Hat jemand ein funktionierendes SQL-Script wie ich Äste verschieben kann ???

  8. ex sagt

    am 13. September 2007 @ 23:26

    Hi,

    wirklich sehr toll erklärt! Hatte die Tage aus Langeweile mal an sowas gedacht. Hab erst PEAR Tree ausprobiert, das funktioniert aber anscheinend mit der neusten Version von MDB2 nicht mehr. Dann hab ich die DB_NestedSet Klasse ausprobiert und die ging auch nicht (wurde auch schon sehr lange nicht mehr aktualisert).

    Auf meiner Suche bin ich dann auf diesen Artikel (und das sehr interessante Blog) gestoßen. Hab das Alles in eine NestedSet geschrieben. Funktioniert wirklich toll und wenn man alles Schritt für Schritt durchgeht und das mit den Balken etwas nachskizziert auch ganz verständlich! Super Konzept und Tutorial!

  9. ex sagt

    am 13. September 2007 @ 23:26

    Ich meinte natürlich ich hab ne eigene NestedSet Klasse dafür gemacht. ;)

  10. Samas sagt

    am 1. Oktober 2007 @ 17:24

    Sehr schöne Erklärung, aber ich fürchte da hat sich ein kleiner Fehler eingeschlichen bei dem finallen Update vor dem Einfügen eines neuen Knotens. Wird nämlich der neue Knoten in die dritte Ebene eingefügt, müssen alle Knoten 'über' diesem neuen Knoten an der rechten Grenze erhöht werden. Das zweite Update

    UPDATE kategorien SET rgt=rgt+2 WHERE rgt = $RGT;

    muß also auf

    UPDATE kategorien SET rgt=rgt+2 WHERE $RGT between lft and rgt;

    geändert werden.

    Schönen Gruß

    Samas

  11. Woody sagt

    am 5. November 2007 @ 16:55

    Die oben angegebene SQL-Query zum Erzeugen der Tabelle kategorien ist falsch, hier die berichtigte Version:

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

  12. admin sagt

    am 5. November 2007 @ 17:17

    Hmm, was genau ist anders? Ich kann keinen Unterschied erkennen.

  13. Leif sagt

    am 6. November 2007 @ 09:31

    Letztes Komma wurde entfernt.

  14. admin sagt

    am 6. November 2007 @ 10:18

    Habs im Beitrag angepasst. Danke.

  15. Alex sagt

    am 29. November 2007 @ 16:58

    Hi. Super Beitrag!

    Ich habe ebenfalls versucht mit Rekursion dieses Problem zu lösen, allerdings nach längeren Überlegungen die Idee verworfen, da inperfomant. Nun bin ich auf den Begriff "Nested Sets" gestossen und kann mich deinem letzten Satz "…dass selbst langjährige Datenbank-Administratoren von diesem Modell nichts wussten und ganz erstaunt waren" nur zustimmen.

    An dieser Stelle habe ich noch eine Frage: ist es denn möglich die Ausgabe nach Namen zu sortieren? Also den Baum. Denn die Sortierung wird benötigt um den Baum "richtig" darstellen zu können. Aber eine Sortierung nach Namen wäre nicht verkehrt.

    Für einen Vorschlag / Idee wäre ich Dankbar.

  16. admin sagt

    am 29. November 2007 @ 17:18

    Auf SucheBiete.com nutze ich Nested Sets inkl alphabetischer Sortierung. Der Trick dabei ist, dass man schon bei der Generierung der lft- und rgt-Werte nach dem Alphabet sortiert, sodass beim späteren Selektieren mit dem "ORDER BY lft" keine Probleme entstehen.

  17. Alex sagt

    am 29. November 2007 @ 17:55

    Diesen Gedanken habe ich auch kurz gehabt. Allerdings wird es schwirig bei dynamischer Sortierung. Denn ich versuche einen Verzeichnis samt Dateien abzubilden. Und möchte dem Benutzer es ermöglichen Aufsteigend/Absteigend bzw. ggf. nach der Dateigröße sortieren zu lassen. Oder wenn zuviele Einträge sind, es irgendwie durch Blättern und "anzeigen pro Seite" darstellen.

    Mir ist ausserdem folgendes aufgefallen und zwar bei der Performancesteigerung. Da steht: (da lft immer größer als rgt ist). Ist das auch so gemeint, oder ein kleiner Dreher?
    Und was noch wichtiger ist: da ist ein Fehler drin (meiner Meinung nach):
    1. UPDATE kategorien SET rgt=rgt+2, lft=lft+2 WHERE lft > $RGT;
    2. UPDATE kategorien SET rgt=rgt+2 WHERE rgt = $RGT;

    Mit dem ersten Statement verschiebst du alle "Mengen" nach rechts, die komplett (also beiden Grenzen) weiter rechts liegen als $RGT. Mit dem zweiten Statement versuchst du nun die rechte Grenze der Menge um 2 zu verschieben, in die du eine neue Menge einfügen möchtest. Schau dir nun zum Veranschaulichen das bild mit Säugetieren (oben) an. Stell nun mal vor, da ist noch eine Übermenge, die von 1.5 bis 7.5 verläuft. Also die Primaten umfasst (ja, keine Kommazahlen, aber nur zum Verstehen, wo die Grenzen liegen sollen). Die Rechte Grenze dieser Menge wird in diesem Fall nicht angefasst und die Zuordnung gerät durcheinander.

    Gruss,
    Alex

  18. admin sagt

    am 29. November 2007 @ 18:06

    Wie gesagt: Für sich häufig ändernde Abfragen bzw Sortierungen sind Nested Sets eher nicht gedacht.

    Und das andere war ein Dreher, hab ich korrigiert. Danke.

  19. Alex sagt

    am 29. November 2007 @ 18:11

    Sorry nochmal für diesen Hinweis/Anmerkung (kannst ggf, diese auch Löschen, da nur an dich gerichtet), aber der Vorschlag zur Optimierung ist falsch!
    1. UPDATE kategorien SET rgt=rgt+2, lft=lft+2 WHERE lft > $RGT;
    1. UPDATE kategorien SET rgt=rgt+2 WHERE rgt = $RGT;

    Denn dadurch gehen die Mengen kapput!

  20. andi’s developer blog » Blog Archive » Hierarchische Strukturen in MySQL sagt

    am 9. Januar 2008 @ 22:27

    [...] dritte Modell, "Nested Sets" (gut erklärt auch im PHP Performance-Blog), ist wohl am kompliziertesten und schnellsten. Da dieses Modell jedoch eher geeignet ist für [...]

  21. LioGetz sagt

    am 19. Januar 2008 @ 23:55

    Sorry, ich komme mir ja schon fast "zu dumm" vor, aber bin ich der einzige der Probleme damit hat die Daten als "eingerückte Liste (Hauptpunkte – Unterpunkte – Unterunterpunkte)" in HTML darzustellen?

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

    Aber was mache ich dann mit der Abfrage? Es hilft mir nicht weiter wenn ich die Ausgabe dann nach Ebenen sortiert habe…Wie sieht die dazugehörige PHP-Schleife dazu aus…

    Danke im voraus
    CU
    Lio :D

  22. admin sagt

    am 26. Januar 2008 @ 09:57

    Hallo Lio,

    ich setze diese Art der Struktur ja auch ein. Wenn man das ResultSet einmal hat, dann geht das Auslesen über Rekursion. Du nimmst das erste Element und durchläufst das erste Kind von dem, guckst dann wieder ob dieses Element Kinder hat usw.
    Da Verarbeiten ist deshalb dann wieder etwas aufwändiger als ein klassisches parentOf-Modell, allerdings trotzdem performanter, da die Daten nur von PHP intern rumgeschaufelt werden und nicht ständig MySQL belästigt wird.

  23. JoJo sagt

    am 31. März 2008 @ 10:57

    Wie verschiebe ich einen Eintrag ?
    Und wie verschiebe ich einen Knoten mit allen Untereinträgen ?

    Hat jemand einen gültigen funktionierenden SQl Code ?

    Vielen Dank für Eure Hilfe

  24. Jan sagt

    am 31. März 2008 @ 11:06

    Ein Verschieben ist nicht möglich. Dazu musst Du den gesamten Baum neu erzeugen. Deshalb ist dieses System auch nur für Anwendungen geeignet, deren Datenbank nur selten geändert wird.

  25. Breadcrumb - Seite 2 - XHTMLforum sagt

    am 4. April 2008 @ 08:35

    [...] bauen sehr oft auf dem Nested Sets Modell auf. Hier mal zwei Links, die das Modell erklären: Nested Sets – Hierarchische Strukturen und Bume in MySQL Beitrag PHP Performance Nested Sets – oder wie man Baumstrukturen effizient in Datenbanken hlt / GUXX Entwicklerblog [...]

  26. Happy Birthday PHP Performance » Beitrag » PHP Performance sagt

    am 14. April 2008 @ 09:29

    [...] geplante Portal reingepumpt. Darunter auch der mittlerweile recht gut verlinkte Beitrag über Nested Sets – ein völlig untypischer Blogbeitrag, vor allem aufgrund seiner [...]

  27. Lisa sagt

    am 27. April 2008 @ 22:42

    Irgendwie hänge ich auch an dem Problem aus dem Resultset in HTML eine Ul-LI-Liste zu generieren. Ich komme einfach absolut nicht weiter. Könntest du das vielleicht mal posten wie du das machst? Vielleicht auch gerne in einem extra Blogbeitrag. Die Frage kommt sicherlich öfters vor.

    Finde das wirklich schwierig. :(

  28. GhostGambler sagt

    am 28. April 2008 @ 12:27

    http://www.google.com/search?hl=de&client=safari&rls=de-de&q=nested+set+ul&btnG=Suche&lr=

  29. Lisa sagt

    am 28. April 2008 @ 23:23

    Sorry GhostGambler, aber diese Verweise auf Google helfen mir herzlich wenig. Dort gibts 1000 Beiträge mit derselben Frage aber nie Antworten und Lösungen.

  30. GhostGambler sagt

    am 29. April 2008 @ 08:35

    Erster Treffer, vierter Post.

  31. Oliver sagt

    am 8. Mai 2008 @ 16:22

    Wie kann man die Nested Sets in der einzelnen Ebene alphabetisch speichern?

  32. Jan sagt

    am 8. Mai 2008 @ 16:27

    Ganz einfach, indem Du beim Ermitteln der lft- und rgt-Werte deine Kategorien (oder was auch immer) nach Namen sortierst. Ich empfehle ja eine zusätzliche Spalte parentID, damit ist das sehr viel einfacher – und man kann die lft- und rgt-Werte immer wieder herstellen.

  33. Oliver sagt

    am 8. Mai 2008 @ 19:31

    Kannst du das erklären? Nur die einfache Abfrage posten oder so?

  34. Jan sagt

    am 8. Mai 2008 @ 20:24

    Nunja, das ganze geht dann wie früher eben rekursiv für das Erstellen des Nes Sets.

    function funktion($curID) {
    SELECT ID FROM kategorien WHERE parent='".$curID."' ORDER BY name

    while(…) {
    UPDATE kategorien SET lft=…,rgt=… WHERE ID='".$rs['ID']."'";
    if(hasChildren() funktion($rs['ID']);
    }
    }

    Hier kann ma nruhig das rekursive anwenden, denn dieses erstellen macht man ja wirklich nur, wenn eine neue Kategorie dazukommt (sollte selten sein, damit sich das lohnt, denn der Neuaufbau wie oben beschrieben, ist natürlich recht aufwändig.

  35. Tobias sagt

    am 4. Juni 2008 @ 01:29

    > GhostGambler sagt
    > am 29. April 2008 @ 08:35
    > Erster Treffer, vierter Post.

    Leider stimmen die Koordinaten nicht mehr – bitte neu angeben oder direkt den Link posten. Danke

  36. GhostGambler sagt

    am 4. Juni 2008 @ 15:29

    Zweiter Treffer vierter Post.

  37. Tobias sagt

    am 5. Juni 2008 @ 06:30

    GhostGambler vielen Dank für diese Referenz, die wird sich bestimmt in den nächsten Tagen / Wochen nicht ändern und jeder wird sofort genau das finden was er sucht.

    Nebenbei bemerkt ist diese Lösung nicht praktikabel, da man halt nur eine einfache Unordered List bekommt, die nur eine Unterebene hat. In einem Nested Set sind allerding Unter(Unter…) Ebenen möglich.

    Anders gesagt – das Code Beispiel gibt folgendes aus:
    * Säugetier
    * Primaten
    * Affen
    * Halbaffen
    * Nagetiere

    Und gefragt ist folgende Struktur:
    * Säugetier
    * Primaten
    * Affen
    * Halbaffen
    * Nagetiere

  38. Tobias sagt

    am 5. Juni 2008 @ 06:31

    Okay, das klappt heir nicht – nochmal die Visualisierung:

    Anders gesagt – das Code Beispiel gibt folgendes aus:
    > Säugetier
    > Primaten
    > Affen
    > Halbaffen
    > Nagetiere

    Und gefragt ist folgende Struktur:
    > Säugetier
    >> Primaten
    >>> Affen
    >>> Halbaffen
    >> Nagetiere

  39. Jan sagt

    am 5. Juni 2008 @ 09:14

    Wie gesagt müsst ihr das Auswerten rekursiv machen. Leider habe ich den Code nicht mehr da, da ich es mittlerweile über AJAX löse und nicht mehr das gesamte Menü auf Anhieb lade.

    Aber ich werds mal in nem Beitrag schreiben, wei ich es damals ungefäöhr gemacht habe, da ja anscheinend jede Menge Nachfrage danach besteht.

  40. GhostGambler sagt

    am 5. Juni 2008 @ 09:48

    "im grunde brauchst du in deinem beispiel doch "nur" jeweils das level vom aktuellen eintrag mit dem vom nächten eintrag vergleichen. in php sind da next() und current() – (arrayfunktionen) deine freunde.

    wenn next dann größer current is, geht n ul auf. wenns kleiner is, ein ul zu. wenns gleich is passiert nüschts…"

    Für mich ist das die Lösung. Kann natürlich sein, dass da jemand anderer Ansicht ist…

  41. Jan sagt

    am 5. Juni 2008 @ 09:51

    Meine Lösung ist ohne next() und current(), ich stell Sie euch bald mal vor. Der Beitrag ist geschrieben, muss aber noch überarbeitet werden.

  42. Lunatic sagt

    am 8. Juni 2008 @ 13:29

    Das Problem mit dem verschieben von ganzen Knoten hatte ich auch und habe gerade diese gute Anleitung zu dem Thema gefunden. Bei mir klappt es damit problemlos, auch wenn ich momentan noch nicht alle Vorgänge nachvollziehen kann. :)

  43. Wie erstelle ich eine HTML-Liste aus einem Nested-Set? » Beitrag » PHP Performance sagt

    am 30. Juli 2008 @ 21:05

    [...] der meistgelesenen Beiträge in diesem Blog ist der über Nested Sets. Es bringt natürlich nichts, wenn man damit performante Abfragen realisieren kann aber [...]

  44. Jingles sagt

    am 5. August 2008 @ 14:19

    Die erste Query im letzten Listing ist falsch.

    Sie müsste wie bei Arne Klempert zu sehen so lauten:

    DELETE FROM kategorien WHERE lft = $LFT;

  45. Lennart Sauter’s Blog » Post Topic » CMS - jetzt auf einer höheren Stufe sagt

    am 8. Mai 2009 @ 18:44

    [...] Diese zwei Seiten sind sicherlich interessant wenn man sich mit dem Thema näher beschäftigen möchte: Traum-Projekt.com sowie Php Performance.de [...]

  46. hups sagt

    am 12. Mai 2009 @ 18:42

    hallo,

    mal eine frage würdest du mir bei meinen projekt helfen hab da probleme mit den abruf von Kathegorien

    details Hier:

    http://www.hupsis-e107.de/theme/e107_plugins/forum/forum_viewtopic.php?4551.last

    würde mich über deine hilfe sehr freuen .

  47. Markus sagt

    am 5. Juni 2009 @ 15:21

    Hallo,
    Danke für diese ausführliche Erklärung von Nested Sets, jedoch wollte ich Dich Benachrichtigen, dass deine Annahme, dass es aus Performancegründen sinnvoller wäre den UPDATE query:
    [quote]UPDATE kategorien SET rgt=rgt+2, lft=lft+2 WHERE lft > $RGT;
    UPDATE kategorien SET rgt=rgt+2 WHERE rgt = $RGT;[/quote] so zusammenzufassen aus meiner Sicht auch sinnvoller ist, jedoch nur, wenn der Baum nur 2 Ebenen hat und wenn man mehr Ebenen benötigt, sollte man den query nutzen, den A. Klempert nutzt, da dann das rgt von allen elternelementen (dert ist ) erhöht wird und nicht nur der rgt-wert des direkt darüberliegenden Elternelements.

    Mit freundlichen Grüssen
    Markus

  48. vater sagt

    am 22. September 2009 @ 16:46

    BOAH DU HURENSOHN bei mir ist nun die ganze tabelle im arsch wegen:

    db::db_query("DELETE FROM mainproject.board_category WHERE lft BETWEEN ".$LFT." AND ".$RGT);
    db::db_query("UPDATE mainproject.board_categoryn SET lft=lft-".$RGT."-".$LFT."+1 WHERE lft>".$RGT);
    db::db_query("UPDATE mainproject.board_category SET rgt=rgt-".$RGT."-".$LFT."+1 WHERE rgt>".$RGT);

  49. Jan sagt

    am 22. September 2009 @ 18:28

    Was heiß "im Arsch"? Dort steht ja, dass diese Befehle zum Löschen einer Kategorie sind. Vermutlich wurde genau das getan, oder?

    Übrigens sollte man nicht gleich jedes Snippet auf seine Produktivumgebung ansetzen.

  50. worxhard sagt

    am 5. Oktober 2009 @ 16:32

    @vater
    …na , dann nimmst du dein vorher erstelltes BackUp ..und alles ist gut ;-) )

  51. albertus sagt

    am 1. Januar 2010 @ 22:06

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

  52. alsahmut sagt

    am 10. Februar 2010 @ 15:05

    Ist es irgendwie möglich einem Kind 2 Kategorien auf einer Ebene zuzuweisen?

  53. Jan sagt

    am 10. Februar 2010 @ 15:52

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

  54. alsahmut sagt

    am 10. Februar 2010 @ 16:25

    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?

  55. Jan sagt

    am 10. Februar 2010 @ 16:51

    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.

  56. alsahmut sagt

    am 10. Februar 2010 @ 19:06

    Gibt es irgend eine Alternative um eine Art Netzplan für eine MySQL-Tabele zu erzeugen? So inder Art wie:

    http://www.industrieschule.de/page/05_IT-Bereich/Projekte/itf022/wlan/bilder/netzplan.gif

  57. Jan sagt

    am 10. Februar 2010 @ 19:37

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

  58. alsahmut sagt

    am 10. Februar 2010 @ 19:45

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

  59. Serkan sagt

    am 24. Mai 2010 @ 13:38

    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

  60. Simon sagt

    am 29. Mai 2010 @ 14:14

    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!

  61. Rene Pardon sagt

    am 16. Juni 2010 @ 12:29

    Wie der Original so ist auch dieser gut und ausführlich beschrieben – auch wenn es noch viel mehr und komplexere Möglichkeiten gibt.

    Danke!

  62. Kurt H. sagt

    am 27. Juni 2010 @ 08:41

    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.

  63. Moritz M. sagt

    am 26. Dezember 2010 @ 19:07

    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.

  64. GhostGambler sagt

    am 1. Januar 2011 @ 20:32

    Das sind die Tabellen Präfixe, siehe z.B. „kategorien AS p“.

  65. René Pardon sagt

    am 1. Januar 2011 @ 21:00

    Hallöchen nochmal und ein frohes neues Jahr!!

    Ich habe vor geraumer Zeit eine Implementierung für das Zend Framework geschrieben. Falls es jemanden interessiert: http://www.renepardon.de/2010/10/18/zend-framework-nestedsets-implementierung-fur-zend_db_table-teil-1/

Komentar RSS · TrackBack URI

Hinterlasse einen Kommentar

Name: (erforderlich)

eMail: (erforderlich)

Website:

Kommentar: