Datenbank Struktur & Festplatte suchen Zeit Verwirrung

Question

könnte jemand mir helfen zu verstehen, wie Festplattensuche funktioniert.

Ich habe eine kleine binäre Datenbank-Datei, die Leistung lesen unbedingt erforderlich ist. Wenn ich ein paar Bytes in der Datei überspringen muss, ist es schneller, seek() zu verwenden oder() zu lesen und dann die unerwünschten Daten zu verwerfen.

Wenn die durchschnittliche Suchzeit einer Festplatte 10ms beträgt und die Lesegeschwindigkeit 300MB/s beträgt, berechnet ich, dass es schneller zu lesen ist() als seek() mit einem Wert kleiner als 3MB. Ist wahr? Gibt es einen Overhead beim Ausführen eines neuen Suchvorgangs, den ein vorhandener Stream nicht lesen kann?

Welche sind Ihrer Meinung nach eine geeignetere Dateistruktur für einen Index?

Entry1:Value:PointerIntoToData 
Entry2:Value:PointerIntoToData 
Entry3:Value:PointerIntoToData 
Data, Data, Data 

Or 

Entry1:Value:Data 
Entry2:Value:Data 
Entry3:Value:Data 

Wenn ein Eintrag gelesen wird, wenn der Wert nicht korrekt ist, wird er ignoriert. Wenn Sie also die Datei streamen, ist es schneller: 1. Wenn ein Eintrag nicht benötigt wird, verwenden Sie seek(), um ihn zu überspringen. 2. Wenn ein Eintrag nicht benötigt wird, lesen Sie ihn und verwerfen Sie die Daten 3. oder verwenden Sie die erste Struktur , wenn ein Eintrag erforderlich ist, seek() in ein Daten-Repository am Ende.

Eintrag ist 4 Byte-Wert 8 Byte & Daten 12KB

Prost

Answer 1

Alle suchen Systemaufruf ändert eine Position in der Datei, wo der nächste gelesen wird. Es bewegt den Antriebskopf nicht. Laufwerksköpfe bewegen sich, wenn Daten gelesen oder geschrieben werden, und Sie haben keine direkte Kontrolle darüber, welches Betriebssystem als nächstes ausgeführt wird.

Das Lesen von vielen Daten, die Sie nicht benötigen, hat Auswirkungen, da alle gelesenen Daten Speicherplatz in Betriebssystempuffern benötigen und ältere Daten verworfen werden. Wenn Sie also über große Dateien suchen, wird der Dateisystem-Cache weniger durcheinander gebracht.

---

Alles, was ich unten schreibe, geht davon aus, dass Sie die ganze Datenbank nicht in den Speicher passen können. Wenn du kannst, mach das einfach. Lesen Sie alles und versuchen Sie, am Ende der Datei neue und geänderte Daten anzuhängen. Mach dir keine Sorgen über verschwendeten Raum, mach nur gelegentlich etwas Kompaktierung.

---

Wenn Ihre Datenbank zu groß ist:

Daten werden gelesen und in Blöcken zu physischen Laufwerk geschrieben (oder Seiten). In ähnlicher Weise ist die Basiseinheit der Datenträger-IO in Ihrem Betriebssystem die Seite. Wenn das Betriebssystem Daten von der Festplatte zwischenspeichert, sind es auch ganze Seiten. Es ist also wenig sinnvoll, zu überlegen, ob Sie mit Such- oder Lesevorgängen einige Bytes vorwärts bewegen müssen. Wenn Sie es schnell machen wollen, müssen Sie berücksichtigen, wie Festplatten-IO wirklich funktioniert.

Erstens, bereits von Nobugz, Ort der Referenz erwähnt. Wenn sich die Daten, die Sie in den einzelnen Vorgängen verwenden, in einer Datei befinden, muss Ihr Betriebssystem weniger Seiten lesen oder schreiben. Auf der anderen Seite, wenn Sie Ihre Daten verbreiten, müssen viele Seiten auf einmal gelesen oder geschrieben werden, was immer langsam ist.

Wie Datenstruktur für Index. In der Regel sind sie als B-trees organisiert. Es ist eine Datenstruktur, die speziell für die effektive Suche großer Mengen von Daten im Speicher mit seitenweisen Lese- und Schreibvorgängen erstellt wurde.

Und beide Strategien zum Organisieren von Daten werden in der Praxis verwendet. Zum Beispiel speichert MS SQL Server die Daten standardmäßig auf die erste Art und Weise: Daten werden separat gespeichert, und Indizes enthalten nur Daten aus indizierten Spalten und physikalischen Adressen von Datenzeilen in Dateien. Wenn Sie jedoch einen gruppierten Index definieren, werden alle Daten in diesem Index gespeichert. Alle anderen Indizes zeigen auf die Daten über einen Clustered-Index-Schlüssel anstelle der physischen Adresse. Der erste Weg ist einfacher, aber der andere kann viel effektiver sein, wenn Sie häufig Datenbereiche auf der Basis von Clustered-Scans scannen.

Answer 2

Wie "absolut notwendig" ist, den Zugang suchen? Haben Sie Ihre Anwendung bereits mit einer nicht optimalen Lösung getestet? Haben Sie bei diesem Test Benchmarks durchgeführt, um festzustellen, wo die echten Engpässe sind? Wenn nicht, werden Sie von den Ergebnissen überrascht sein.

Als nächstes versuchen Sie verschiedene Methoden und vergleichen Sie die Laufzeiten. Testen Sie unter verschiedenen Systemlasten (dh wenn das System außer für Ihre Anwendung im Leerlauf ist und wenn es beschäftigt ist).

Bedenken Sie, dass Ihre Optimierungen basierend auf Ihrer aktuellen Festplatte möglicherweise falsch werden, wenn eine neue, schnellere Festplatte verschiedene interne Optimierungen hat, die Ihre Arbeit aus dem Fenster werfen.

Answer 3

Ein sequentielles Lesen ist immer schneller als eines, das eine Kopfsuche (keine Positionssuche) erfordert. Die typische Leistung einer Festplatte für sequenzielles Lesen liegt bei 50-60 MB/s, wobei der Abfall auf einen Worst-Case von ~ 0,4 MB/s sinkt. Sobald die Antriebsköpfe positioniert sind, erhalten Sie die Daten im Zylinder im Wesentlichen kostenlos. Der Dateisystemcache nutzt dies aus, indem er Sektoren aus einem Zylinder vorliest.

Sie haben jedoch keine Kontrolle über die Platzierung Ihrer Daten auf Plattenzylindern. Noch können Sie die Antriebsgeometrie erraten. Beachten Sie, dass der Durchsatz im Laufe der Zeit erheblich schlechter werden kann, wenn das Volume fragmentiert wird. Sie müssen nach perf suchen, indem Sie Daten im Speicher zwischenspeichern. An diesem Punkt machen Sie sich Gedanken über locality of reference.

Answer 4

Sie können die Datei immer im Speicher ablegen und dann über Zeiger und dergleichen darauf zugreifen. Das sollte Ihre Zugriffe normalerweise einfacher machen und schneller.