Ich untersuche die Idee, ein DBMS rein funktional zu schreiben. Die traditionelle Datenstruktur für die Indizierung ist B-Tree. Ich möchte eine rein funktionale Entsprechung von B-Tree kennen, die optimiert werden könnte, um den Festplattenzugriff zu minimieren. Vielen Dank.
14
Antworten:
Ich weiß mehr über rein funktionale Datenstrukturen als über externe Speicherdatenstrukturen, aber ich werde es versuchen.
Ein B-Baum kann durch Pfadkopieren rein funktional geschrieben werden. Der Pfad ist kurz ( ), aber das Kopieren jedes Blocks erfordert O ( B ) -Schreibvorgänge in O ( 1 ) -Blöcken.O ( logBn ) O ( B ) O ( 1 )
Wenn Sie bereit sind , die Struktur nur voll hartnäckig sein zu lassen, anstatt rein funktional, ich glaube , Sie die Anzahl der Schreibvorgänge in einem Knoten Kopie reduzieren abgeschrieben erwartet, wobei w die Wortbreite ist, mit der vollständig persistente Arrays in "Konsequent persistente Versuche für eine effiziente Versionskontrolle"O ( lgw ) w
Vielleicht möchten Sie sich diese Präsentation über RethinkDB ansehen , die aufgrund der Schreibkosten in SSDs rein funktionale Datenstrukturen verwendet.
quelle
Wenn Sie an einer rein funktionalen Datenbank interessiert sind, sollten Sie sich wahrscheinlich die Doktorarbeit von Phil Trinder ansehen, die sich mit diesem Thema befasste . Er hat ein Kapitel über die Verwendung von B-Bäumen.
quelle