Optimierung von mmap auf sehr große Datei

Question

Ich habe eine sehr große Datei 150 GB. Ich benutze schreibgeschützt mmap und ich führe binäre Suche in die Datei.

Derzeit binäre Suche ziemlich langsam.

Allerdings denke ich über folgende Optimierung nach - wenn ich (Disk-Suche) einen Wert überprüft, sind alle Werte "um" diesen Wert bereits in den Speicher, weil sie zum gleichen Festplattenblock gehören. Anstatt irgendwo anders in der Datei zu springen, kann ich "nahe" Werte überprüfen und danach springen.

Lohnt sich diese Optimierung?

Auch wie kann ich abschätzen, wo Plattenblock "endet".

Answer 1

Sie sind auf die Argumentationskette gestoßen, die zur B-tree Datenstruktur führt. Die Optimierung, die Sie sich vorstellen ist lohnt sich, aber um so viel wie möglich zu bekommen, müssen Sie die Daten auf der Festplatte wesentlich reorganisieren und verwenden kompliziertere Algorithmen als die binäre Suche. Sie sollten wahrscheinlich in vorhandene Open-Source-B-Tree-Bibliotheken schauen, anstatt von Grund auf neu zu implementieren.

Da Sie mmap verwenden, ist die minimale Granularität des Zugriffs nicht die Festplattenblockgröße, sondern die Größe der Speicherseite, die mit sysconf(_SC_PAGESIZE) abgefragt werden kann. Einige Betriebssysteme lesen und bevölkern einen größeren Teil des Speichers bei wahlfreiem Zugriff auf eine dateiunterstützte Region, aber ich kenne keine tragbare Methode, um herauszufinden, wie viel. Sie können auch einen Vorteil von madvise(MADV_RANDOM) erhalten.