In dieser kurzen Serie von Artikeln soll es um eine Einführung in Nested Sets gehen und deren Abbildung in einer relationalen Datenbank. In diesem ersten Teil soll erläutert werden, worum es sich bei Nested Sets handelt. Die verschiedene Operationen auf Nested Sets werden in den folgenden Artikeln behandelt werden.
Nested Sets stellen ein Modell dar, um Bäume mit Hilfe von (Teil-) Mengen abzubilden. Das Modell der Nested Sets wird meist in Datenbankanwendungen eingesetzt. Am einfachsten wird das Modell mit Hilfe eines Beispiels verständlich.
In der oben liegenden Zeichnung ist ein einfacher Baum dargestellt. Wie sieht dieser Baum jetzt als Nested Set aus?
Es gibt für jeden Knoten zwei Informationen, die linke und die rechte Grenze der Teilmenge. Folgend ein paar (redundante) Informationen/Regeln zu den Grenzen:
- Die linke Grenze ist immer kleiner als die rechte Grenze (im folgenden wird oft nur noch von links und rechts gesprochen).
- Die beiden Grenzen umfassen alle ihre Kindelemente.
- Für Blätter gilt links plus eins ergibt rechts.
- Beide Grenzen sind größer als die linke Grenze des Elternelements und kleiner als die rechte Grenze des Elternelements.
Die nächste Darstellung des Baums enthält jetzt zusätzlich die Nested Set Informationen (linke und rechte Grenze).
Im kommenden Teil II werden dann, wie oben schon angekündigt, verschiedene Operationen erläutert werden. Motiviert wurde dieser Artikel durch die Verwendung von Nested Sets, zur Abbildung von Verzeichnis/Ordner Strukturen in einer Webanwendung.
Also bis demnächst..
Sven Seiller
