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.

Weiter geht's unter http://www.develnet.org/36.html