Warning: file_put_contents(/home/www/web1/html/php_dev/test.txt) [function.file-put-contents]: failed to open stream: Permission denied in /home/www/web1/html/php_dev/sys/lib.activity.php on line 58
Das 'Nested Sets' Modell - Bäume mit SQL PHP Tutorials nicht nur für Anfänger php-resource.de
php-resource.de

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@ | 43667 | KAT : MySQL | | Kommentare 2


4

4

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

Zeit ist Geld, PC einfach selbst reparieren!

Zeit ist Geld, PC einfach selbst reparieren!Wenn der PC nicht richtig läuft, wirft sie das in Ihrem Arbeitsalltag meist zurück. Dabei können Sie einige Probleme mit relativ wenig Aufwand und ohne intime Kenntnisse Ihres Rechners selbst lösene

18.04.2016 | Neu | Berni

Die wichtigsten Rahmenbedingungen für das Hosting

Die wichtigsten Rahmenbedingungen für das HostingGuter Webspace wird in der heutigen Zeit immer wichtiger. Die Scripte werden moderner und fordern höhere Leistung, der allgemeine Traffic im Internet nimmt zu.

17.08.2015 | Neu | Berni