Speicherung von Baumstrukturen in einer relationalen Datenbank

Baumstrukturen in Datenbanken. Das Leid von Eltern, Kindern, Geschwister, …

Das Speichern von Baumstrukturen in einer relationalen Datenbank kann man mit verschiedenen Methoden bewerkstelligen. Einige davon sind sehr einfach, aber bei großen Datenmengen nicht sehr effizient und für einige Arten von Bäumen nicht einmal geeignet. Einige Methoden sind hingegen sehr effizient, es gestaltet sich aber etwas komplizierter, wenn man den Baum dann manipulieren will. Dafür muss man in den meisten Fällen den kompletten Baum in der Datenbank neu organisieren.

Folgende Methoden kann man verwenden:

1. Adjacency List Model - Jeder Knoten speichert die ID seines Elternknotens (Parent-ID
2. Nested Sets - Verschachtelte Mengen

Parent ID Tree / Adjacency List Model

Das Adjacency List Model ist eine einfache Methode, hierarchische Daten (z. B. Kategorien, Menüs, Ordnerstrukturen) in einer relationalen Datenbank zu speichern. Die Grundidee ist, dass jeder Eintrag seinen direkten übergeordneten Knoten kennt (Parent).

Weblinks:

• Managing Hierarchical Data in MySQL
• mysqlbook adjacency_list_model

Nested Sets

Die Speicherung und Organisation eines Nested Sets Baum sowie die Darstellung kann sich als sehr kompliziert herausstellen.  Besonders bei der Ausgabe von geschachtelten Strukturen wie z.B. UL/LI-Listen.

Weblinks:

• Nested Sets - Artikel von Arne Klempert in deutsch
• Artikel zum Thema Nested Sets
• Artikel zum Thema auf traum-projekt.de
• Workshop NestedSets

Begriffsklärung

• Root - Wurzel
• Leaf - Blatt
• Branch - Zweig
• Node - Knoten
• Ancestry - Vorfahre
• Descendant - Nachfahre
• Parent - Eltern
• Child - Kind
• Siblings - Geschwister
• Path - Pfad über die Knoten

Weblinks Allgemein

• Multiple trees in one table
• Etwas zur Performance bei Parent ID Trees [pdf]
• Trees and Other Hierarchies in MySQL
• Wikipedia: Baum (Graphentheorie)
• Wikipedia: Balancierter Baum
• Wikipedia: Nested Sets
• Wikipedia: Kategorie: Datenstrukturen