Effiziente persistente Datenstrukturen für die relationale Datenbank

Question

Ich suche nach Material über persistenten Datenstrukturen, die verwendet werden können, ein relationales Modell zu implementieren.

Persistenz im Sinne der unveränderlichen Datenstrukturen.

Wer weiß, einige gute Ressourcen, Bücher, Papiere und so?

(Ich habe das Buch schon rein funktionale Datenstrukturen das ist ein gutes Beispiel dafür, was ich suche.)

Answer 1

Es ist einfach, den allgegenwärtigen B-Baum als persistent zu ändern. Einfach immer einen neuen Knoten alloctate wenn ein Knoten geändert wird, und den neuen Knoten zu dem rekursiven Anrufer zurückzukehren, der es auf dieser Ebene einfügen wird durch einen neuen Knoten Zuweisung usw. Ultimative der neue Wurzelknoten zurückgeführt wird. Nicht mehr als O (log N) Knoten pro Betrieb zugeordnet sind.

Dies ist die Technik, die in funktionalen Sprachen verwendet zu implementieren, z, 2-3 Bäume.

Answer 2

Ich habe eine solche Datenstruktur für BergDB implementiert ( http://bergdb.com/ ) - eine Datenbank mit ein Datenmodell, das eine persistente Datenstruktur ist.

Ich würde vorschlagen, das Lesen

http://www.cs.cmu.edu/~sleator/ Papiere / Persistence.htm

Es ist die ursprüngliche Arbeit, wie eine persistente Datenstruktur zu schaffen, basierend auf einem gewöhnlichen (kurzlebig) ein.

Answer 3

SQLite hat eine b-Baum-Datenstruktur Implementierung können Sie einen Blick auf nehmen;