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.

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 »