Größer als Speicher Datenstrukturen und wie sie typischerweise behandelt werden

Question

Angenommen, ich habe eine Datei-basierte Datenstruktur wie ein B + Baum. Mein Verständnis ist, dass die Daten voraussichtlich auf der Festplatte gespeichert werden, aber der Index wird normalerweise im Speicher geladen. Was ist, wenn Sie eine so große Datei haben, dass selbst ihr Index nicht in den Speicher passt? Wie wird das normalerweise gehandhabt? Zweitens, da der Index ein Baum ist, kein linearer Satz von Daten, wie wird er normalerweise auf der Platte angeordnet?

Ich bin im Grunde neugierig, wie es in realen Projekten (wie Berkeley DB) getan wird. Offensichtlich interessiere ich mich für breite Striche. Ich hoffe, eine Idee zu bekommen, damit ich einen Kontext habe, wenn ich in den B-Tree-Abschnitt meines Datenbankbuches stoße (oder jogge meinen Speicher von CS XYZ von vor Jahren)

Answer 1

B-Bäume sind für Seiten- Systeme, bei denen ein bestimmter Knoten in eine Seite passt. Um einen Eintrag in einem B-Baum zu finden, müssen Sie nur jeweils eine Seite laden, damit Sie das tun können.

Sogar die Aktualisierung von ihnen erfordert nicht eine große Anzahl von Seiten im Speicher zur gleichen Zeit - ich stelle mir vor, die schwierigste Operation ist ein Löschen, wenn Knoten reorganisiert werden, aber wenn es sorgfältig implementiert wird, könnte auch getan werden relativ wenige Seiten im Speicher.

Answer 2

Sie möchten vielleicht einen Blick auf SQLite werfen. Die code base ist viel kleiner als Berkeley DB, es ist Public Domain, es ist sehr klar organisiert und kommentiert, und die out-of-source documentation ist ausgezeichnet. Lehrte mich viel über btrees in der realen Welt

Answer 3

Um Ihre erste Frage zu beantworten, eine Datenstruktur, die zu groß ist, um in den Speicher zu passen, ist in der Regel in "Seiten" unterteilt, in der Regel haben alle Seiten die gleiche Größe und jede Seite enthält Teil der Datenstruktur, um die Daten zu verwenden, die Sie laden und die Seiten entladen.

Eine weitere gebräuchliche Option (die in RDBMS normalerweise nicht verwendet wird, aber häufig bei XML- und Mediendateien verwendet wird) ist das Streaming, bei dem Sie die Daten in der Reihenfolge verarbeiten, indem Sie den nächsten Abschnitt laden und den vorherigen verwerfen.

Und das beantwortet auch Ihre zweite Frage, wenn Sie Paging verwenden als die Dateistruktur ist eine Folge von Seiten der gleichen Größe, wenn Sie Streaming als die Daten sollten in der Reihenfolge, die Sie verwenden werden, ausgelegt werden es (im Falle eines Baumes wird es wahrscheinlich abhängig von Ihrer Anwendung entweder DFS oder BFS Bestellung sein).