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?

[Patito]

Als Datensuruktur wäre statt AVL-Tree sicher auch ein RedBlack-Tree oder ein B-Tree passend.
B-Trees scheinen ja für File-orientierte Angelegenheiten recht gut zu sein. Persönlich verwende ich zur Zeit immer RedBlack-Trees.
Ein AVL-Tree ist aber sicher auch eine gute Wahl.

[BUG]

Zitat von Laser:

Nachteile:

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

1. Denke ich nicht. Da alles sortiert ist (Minimum findet man im AVL-Baum ja auch schnell), kannst du immer durch das Mergen einen Puffer füllen, den du dann auf die Platte schreibst und wiederverwendest.
2. Du könntest neu in den Index eingefügte Datensätze ungeordnet auf die Platte schreiben, dann musst du nicht denn ganzen Index neu erstellen, sondern kannst den AVL-Baum neu aufbauen. Da müsste man sich noch sicherstellen, dass ein Datensatz erst dann als "sicher" eingefügt gilt (und so an den Clienten gemeldet wird), wenn er auch im Index ist (zumindest in der Sicherungsdatei, flushen nicht vergessen). Das wäre der Aufwand, den dir eine Datenbank abnehmen würde

[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.

[himitsu]

'ne eigene Cache braucht man nicht unbedingt zu implementieren, wenn man nicht das Cachingmuster (was wann wie geladen und freigegeben wird) selbst implementieren will, sondern einem 'nen einfaches Verhalten ausreicht

Zugriffe über TStream oder über eine MMF werden eh über die Windows File Cache umgeleitet.


Wenn man es schaft den Speicher des BTree (oder sonstewas) als einen zusammenhängenden Speicherblock (oder als ein paar Blöcke) im RAM abzubilden (z.B. die einzelnen Einträge nicht über New, sondern in einem statischen Array), dann könnte man diesen auch in eine MMF legen.
Dann könnte das Programm abstürzen, aber die Daten blieben erhalten.