Ich suche nach Materialien zu persistenten Datenstrukturen, die zur Implementierung eines relationalen Modells verwendet werden können.
Persistenz im Sinne von unveränderlichen Datenstrukturen.
Wer weiß von einigen guten Quellen, Büchern, Papieren und dergleichen?
(Ich habe bereits das Buch Rein funktionale Datenstrukturen , was ein gutes Beispiel ist von dem, was ich suche.)
Es ist einfach, den allgegenwärtigen B-Baum so zu ändern, dass er beständig ist. Weisen Sie immer einfach einen neuen Knoten zu, wenn ein Knoten geändert wird, und geben Sie den neuen Knoten an den rekursiven Aufrufer zurück, der ihn auf dieser Ebene einfügt, indem er einen neuen Knoten usw. zuweist. Ultimate Der neue Wurzelknoten wird zurückgegeben. Nicht mehr als O (log N) Knoten werden pro Operation zugewiesen.
Dies ist die Technik, die in funktionalen Sprachen verwendet wird, um z. B. 2-3 Bäume zu implementieren.
Ich habe eine solche Datenstruktur für BergDB implementiert ( Ссылка ) - eine Datenbank mit einem Datenmodell, das eine persistente Datenstruktur darstellt.
Ich würde vorschlagen,
zu lesenEs ist die ursprüngliche Arbeit, wie man eine persistente Datenstruktur basierend auf einer gewöhnlichen (ephemeren) Struktur erstellt.
SQLite hat eine Implementierung der B-Tree-Datenstruktur Sie können sich ansehen;
Tags und Links data-structures functional-programming immutability rdbms relational