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

[Iwo Asnet]

Ich würde auch einen BTree + Cache nehmen. Es existieren diverse Delphi-Implementierungen im Netz.
Der große Vorteil wäre der, das das Ding komplett skalierbar ist und auch bei 200 PetaByte noch schnell genug ist.

Richtig fix wird es durch die Verwendung eines MRU-Caches, bei dem die letzten N benötigten Seiten im Speicher gehalten werden.

Eine 'Seite' entspricht einem Blatt/Knoten des BTree-Baumes und ist i.A. 8k groß (weil das die Systempage-Größe von Windows ist).

Wenn Du das Teil fertig hast, könnte man sich überlegen, ob eine Indexierung per Hashmap oben drauf nicht noch besser wäre.

Riesenvorteil: Der Btree erzeugt gleichzeitig die Datei mit den Daten. Wenn deine Anwendung selten gestartet wird, dann kannst Du die DB am Anfang komplett einlesen (also die Schlüssel) und die Recordnummern / Position der Daten in der Datei in der Hashmap ablegen.

Dann suchst Du über die Hashmap in optimal kurzer Zeit und bist auch beim Einfügen noch schnell. Leider ist ein Btree beim Einfügen nicht wirklich sauschnell. Abhilfe schafft hier eine art Transaktionskontrolle: Beim Einfügen mehrerer Datensätze werden einzelne Seiten verändert. Um das redundante mehrfach hintereinander stattfindende Schreiben einer Seite zu optimieren, könntest Du die zu schreibenden Seiten vormerken und erst beim 'Commit' (oder einem 'Flush'-Befehl) einmalig speichern.

Überlege dir noch, ob nicht eine einfache simple DB ausreicht, denn eigentlich programmierst du mit dem o.g. Verfahren eine generische DB.