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

[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