Was sind Modelle zur Speicherung von Baumstrukturen und was sind ihre Eigenschaften?

Question

Bisher habe ich Adjazenzlisten, verschachtelte Mengen und verschachtelte Intervalle als Modelle für die Speicherung von Baumstrukturen in einer Datenbank kennengelernt.Ich kenne diese gut genug und habe Bäume von einem zum anderen gewandert.

Welche anderen beliebten Modelle gibt es?Was sind ihre Eigenschaften?Was sind gute Ressourcen (Bücher, Internet usw.) zu diesem Thema?

Ich suche nicht nur nach Datenbankspeicher, sondern möchte mein Wissen über Bäume im Allgemeinen erweitern.Ich verstehe zum Beispiel, dass verschachtelte Mengen/Intervalle besonders günstig für die relationale Datenbankspeicherung sind, und habe mich gefragt, ob das tatsächlich so ist schlecht Wahl in anderen Kontexten?

Answer 1

Die wichtigste Quelle hierfür sind die Kapitel 28–30 von SQL für Smarties.

(Ich habe dieses Buch so sehr empfohlen, dass ich denke, Celko schuldet mir inzwischen Tantiemen!)

Answer 2

Eine Variante besteht darin, dass Sie eine direkte hierarchische Darstellung verwenden (d. h.übergeordneter Link im Knoten), sondern speichert auch einen Pfadwert.

dh.für einen Verzeichnisbaum bestehend aus Folgendem:

C:\
   Temp
   Windows
       System32

Sie hätten die folgenden Knoten

Key     Name     Parent     Path
1       C:                  *1*
2       Temp       1        *1*2*
3       Windows    1        *1*3*
4       System32   3        *1*3*4*

Der Pfad ist indiziert und ermöglicht Ihnen die schnelle Durchführung einer Abfrage, die einen Knoten und alle seine untergeordneten Knoten aufnimmt, ohne Bereiche bearbeiten zu müssen.

dh.um C: emp und alle seine untergeordneten Elemente zu finden:

WHERE Path LIKE '*1*2*%'

Diese Darstellung ist der einzige Speicherort, der mir einfällt Ausweise in einer Zeichenfolge wie dieser ist in Ordnung.

Answer 3

@lassevk: Dieser Artikel geht ausführlicher auf Ihren Ansatz ein und stellt Codeausschnitte bereit.

Hoffe das hilft.