Was sind Modelle zum Speichern von Baumstrukturen und was sind ihre Eigenschaften?

Question

Bis jetzt habe ich Adjazenzliste, verschachtelte Mengen und verschachtelte Intervalle als Modelle zum Speichern von Baumstrukturen in einer Datenbank gefunden. Ich kenne diese gut genug und bin von einem Baum zum anderen gewandert.

Was sind andere beliebte Modelle? Was sind ihre Eigenschaften? Was sind gute Ressourcen (Bücher, Web, etc.) zu diesem Thema?

Ich bin nicht nur auf der Suche nach db-Speicher, sondern möchte mein Wissen über Bäume im Allgemeinen erweitern. Zum Beispiel verstehe ich, dass verschachtelte Sätze/Intervalle besonders günstig für relationale Datenbankspeicher sind und haben mich gefragt, ob sie tatsächlich eine Alternative in anderen Kontexten sind?

Answer 1

Die grundlegende Ressource dafür sind die Kapitel 28-30 von SQL for Smarties.

(ich dieses Buch habe so viel empfohlen Tantiemen ich heraus Celko schuldet mir jetzt!)

Answer 2

Eine Variante ist, wo Sie eine direkte hierarchische Darstellung (dh. Eltern Link im Knoten) verwenden, sondern auch einen Pfadwert speichern.

dh. für einen Verzeichnisbaum der folgenden besteht:

C:\ 
    Temp 
    Windows 
     System32 

würden Sie haben folgende Knoten

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

Pfad indiziert ist, und ermöglicht es Ihnen, schnell eine Abfrage zu tun, die einen Knoten aufnimmt und alle seine Kinder, ohne Bereiche manipulieren zu müssen.

dh. \ Temp und alle seine Kinder: C finden

WHERE Path LIKE '*1*2*%' 

Diese Darstellung ist der einzige Ort, den ich mir vorstellen kann, wo die Speicherung ids in einem String wie dies in Ordnung ist.

Answer 3

@lassevk: This article spricht über Ihren Ansatz näher und Code-Schnipsel zur Verfügung stellt.

Hoffe, das hilft.