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.

Selektieren der Daten

"Wozu der ganze Streß eigentlich?" mag man sich fragen ... Nun, die Früchte unserer Arbeit können wir mit dem folgenden Query ernten:

  SELECT node1.payload,
         COUNT(*) AS level

    FROM node AS node1,
         node AS node2
 
   WHERE node1.root_id = 1
     AND node2.root_id = 1

     AND node1.lft BETWEEN node2.lft AND node2.rgt

GROUP BY node1.LFT;

Dieses Konstrukt gibt den kompletten Thread-Baum mit den Elementen aus, die zu root_id = 1 gehören. Zusätzlich enthalten ist der Grad (level) - so ist es ein Leichtes, korrekte Einrückungen der Threads darzustellen. Das Ergebnis:

+-----------------------+-------+
| payload               | level |
+-----------------------+-------+
| A - Das Wurzelposting |     1 |
| B - Reply auf "A"     |     2 |
| C - Reply auf "B"     |     3 |
| D - 2. Reply auf "B"  |     3 |
+-----------------------+-------+

Als Teil eines Threaded Forums könnte die Ausgabe so aussehen:

A - Das Wurzelposting
- B - Reply auf "A"
  - C - Reply auf "B"
  - D - 2. Reply auf "B"

Ähnlich wie beim Erweitern des Baumes benötigen wir für die Ausgabe keinen direkten "Anfangspunkt" (node_id) - es reicht die eindeutige Zuordung (root_id) eines Postings zum Thread, den Rest ergibt die Logik der Nested Sets-Zahlenpaare.

Im normalen Einsatz haben wir trotzdem einen Ausgangspunkt: Üblicherweise wird in einer Übersicht mehr als ein Thread dargestellt. Nach dem Beschaffen der Daten der Wurzelpostings (aller Posting in den root_id = node_id gilt) für eine Übersichtsdarstellung verfügen wir über die benötigten Parameter. Für jedes dieser Wurzelpostings muss zusätzlich die oben beschreibene Operation angewendet werden.

Merke:

Man könnte auf die Idee kommen, ein komplettes Forum in nur einem Baum mit einer "unsichtbaren" Wurzel zu realisieren, um dann das ganze Forum und dessen Teilbäume (Threads) mit einer einzigen Query herauszulesen. Der gesunde Menschenverstand sollte an dieser Stelle aktiviert werden: Je größer das Nested Set wird, umso teurer ist es neue Einträge einzufügen und umso länger wird das Herauszulesen mittels dem vorgestellten Join dauern.
Hier gilt es einen Kompromiss zwischen Bequemlichkeit und Geschwindigkeit zu finden, und das Forum in kleinere autarke Teilbäume zu unterteilen.

Mehr Informationen aus dem Baum:

Mit einer leicht veränderten Query können wir für jeden Eintrag die Anzahl der Kind-Knoten ermitteln, und somit bei der Ausgabe die Anzahl der Antworten auf ein Posting angeben:

  SELECT node1.payload,
         IF ( node1.node_id = node1.root_id,
              round( (node1.rgt - 2) / 2, 0),
              round( ( (node1.rgt - node1.lft - 1) / 2), 0)
            ) AS children,
         COUNT(*) AS level

    FROM node AS node1,
         node AS node2
 
   WHERE node1.root_id = 1
     AND node2.root_id = 1

     AND node1.lft BETWEEN node2.lft AND node2.rgt

GROUP BY node1.LFT;

Das Ergebnis:

+-----------------------+----------+-------+
| payload               | children | level |
+-----------------------+----------+-------+
| A - Das Wurzelposting |        3 |     1 |
| B - Reply auf "A"     |        2 |     2 |
| C - Reply auf "B"     |        0 |     3 |
| D - 2. Reply auf "B"  |        0 |     3 |
+-----------------------+----------+-------+

Selbstverständlich könnte man die LFT-RGT-Zahlenpaare auch direkt aus den Datenbankfeldern rausziehen und die kleine Berechungsoperation in einer übergeordneten Steuerungssprache durchführen.

Betrachten wir abschließend das Ergebnis der letzten Query auf einen größeren Baum mit dem Augenmerk auf die jeweilige Einrückungstiefe und die Anzahl der Kinder. Der Baum dürfte bereits aus dem visuellen Modell bekannt sein:

+---------+----------+-------+
| payload | children | level |
+---------+----------+-------+
| A       |       12 |     1 |
| B       |        3 |     2 |
| C       |        0 |     3 |
| D       |        1 |     3 |
| E       |        0 |     4 |
| F       |        7 |     2 |
| G       |        0 |     3 |
| H       |        5 |     3 |
| I       |        3 |     4 |
| J       |        1 |     5 |
| K       |        0 |     6 |
| L       |        0 |     5 |
| M       |        0 |     4 |
+---------+----------+-------+

Navigation -> Seitenanzahl : (4)

« 1 2 3 4