Suche Datenstruktur für Index in Datei und RAM - Kombination Array+indexed AVL-Baum?

[Laser]

Hallo,

ich bin dabei, eine Datenstruktur für einen Index auszuwählen. Eine Datenbank soll nicht verwendet werden. Zu Lasten der RAM-Verwendung soll eine extreme Beschleunigung erreicht werden. Könnt Ihr meine bisherigen Überlegungen bitte kommentieren, was man vielleicht anders oder besser machen könnte. Vielen Dank.

Der Index besteht aus Int64 auf der Festplatte und ist aufsteigend sortiert.

furtbichler hat hier schon einmal ein paar Kriterien für die Entscheidung benannt.
Auf den Index wird sehr häufig zugegriffen.
90% Lesen, Zugriff auf neu eingefügte Datensätze ist wahrscheinlicher als auf alte Datensätze
10% Einfügen, hinten anhängen ist unwahrscheinlich (ohne die Sortierung zu verlieren)
0% Löschen, kommt nicht vor

Die Datei wird komplett in ein Array eingelesen (blockread). Die Datei wird in der Regel < 1 GiB groß sein.
Neue Datensätze werden in einen indexierten AVL-Baum (TIndexedAVLTree) eingefügt.
Beim Lesezugriff wird im Array und im AVL-Baum gesucht.
Beim Schließen der Indexdatei werden Array und Baum gemergt und sortiert auf die Platte geschrieben.

Vorteile:
Hohe Lesegeschwindigkeit durch kompletten Index im RAM.
Schnelles Einfügen neuer Datensätze in den Baum.

Nachteile:
Zusätzlicher Speicherbedarf für out-of-place natural merge sort.
Index muss bei ungeplantem Programmabbruch neu aufgebaut werden.


Was meint Ihr?