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

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.

|23.02.2011 | gorski@ | 46144 | KAT : MySQL | | Kommentare 2


1

4

Das 'Nested Sets' Modell
Bäume mit SQL

Status Quo

Ein häufige Programmieraufgabe ist es baumartige Strukturen abzubilden, also Strukturen in denen jeder Knoten einen Baumes beliebig viele Unterknoten besitzen kann, die jeweils wieder beliebig viele Unterknoten besitzen können etc.

Diese Strukturen kennt jeder, wenn er sich mal genauer Filesystem-Browser (z.B. den Windows-Explorer o.ä), strukturierte Webkataloge oder ähnliche Tools angeschaut hat: Verzeichnisse (Knoten) enthalten Dateien und Verzeichnisse, die ihrerseits wieder Dateien und Verzeichnisse enthalten. Diese Schachtelung erfolgt dabei beliebig tief.

Nun, in Filesystem-Browsern erfolgt die Darstellung rekursiv, da der ganze darzustellende Baum mittels Pointern im RAM offensichtlich schnell genug durchlaufen werden kann. Was ist aber, wenn man aus einer relationalen SQL-Datenbank Daten performant holen möchte, um diese als einen Baum mit z.B. HTML zu visualisieren?

Die mit Abstand schlechteste Idee ist es, verkettete Listen mit Rückwärts- bzw. Vorwärtsreferenzen in der Datenbank zu erzeugen und ebenfalls rekursiv für jeden Knoten eines vermeintlichen SQL-Baumes eine separate Query an die Datenbank abzusetzen.

Solange der darzustellende Baum klein bleibt, werden Performanceverluste nicht augenscheinlich und fallen nicht ins Gewicht, aber bei größerer Datenmengen wird die Datenbank bei diesem Verfahren zwangsläufig in die Knie gehen müssen, da hunderte von Queries den Server verstopfen können.


Merke:

  • Nie rekursive Queries an die Datenbank absetzen, wenn es sich vermeiden lässt.

Mit "Nested Sets" (verschachtelten Mengen), einfachen Kenntnissen der Relationalen Algebra und wenig SQL-Verständnis lassen sich binäre und allgemeine Bäume abbilden, ohne dass es im Datenbanklayer zu Rekursion kommen muss. Relationale Algebra ist auch das interne Arbeitsprinzip der meisten SQL-Datenbanken.

Dieses Tutorial beschreibt einen Ansatz für ein Threaded Forum mit Nested Sets in einer abstrakten Form. Den Anfang macht ein visuelles Modell.

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

Wissensbestand in Unternehmen

Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Neu | Berni

Computer oder Gehirn? Macht uns das Internet immer dümmer? 

Computer oder Gehirn? Macht uns das Internet immer dümmer? Die ständig zur Verfügung stehenden Informationen über das Internet haben den Vorteil, dass man sich im Vergleich zu früheren Jahren deutlich weniger merken muss.

18.01.2018 | Neu | PhilippEgger