Speichern dynamischer Objekte mit wachsenden Listen auf der Festplatte

Question

okay, also entwickelte ich bisher ein System im Hauptspeicher, das viele verschiedene Objekte aufweist, und jedes Objekt speichert Listen anderer Objekte im System. Jetzt möchte ich dies in den hartnäckigen Speicher bewegen. Ich suche nicht nach der offensichtlichen Antwort, ein DBMS zu verwenden, da der Punkt ist, dass ich eine benutzerdefinierte Datenbank für mein System schreibe.

Jetzt für jedes Objekt legte ich eine ID zu. Die IDs können in einer Tabelle aufgenommen werden, um den Block und den Offset für den Speicherort der Daten für dieses Objekt zu finden. Jetzt hat jedes Objekt Listens / Sets, die auf andere Objekte im System hinweisen. Natürlich sind sie in der Speicherung von 8 Byte (mit Longs nach den IDs) IDs, mit denen die anderen Objekte gefunden werden können. Jetzt ist meine Frage hier, dass ich weiß, dass die Listen im Laufe der Zeit wachsen werden, damit sie Platz brauchen, um zu wachsen. Mein bester Gedanke, um die Listen zu speichern, so dass ich nicht um Objekte umgehen muss, wenn sie wachsen, ist, dass jede Liste eine ID genauso wie die Objekte zugewiesen hat, so dass sie in einem Tisch wie die Objekte aufgenommen werden können sie auf der Festplatte.

Jetzt hat jeder Listenteil einen eingestellten zugewiesenen Speicherplatz zum Speichern von 10 Objekten und dann ist das ID des nächsten Listenteils, wenn er weitere Objekte enthält. Dies scheint eine anständige Art zu scheint, es zu tun und mit ständig wachsenden Gegenständen umzugehen, aber ich frage mich, ob es bessere Ansätze gibt. Ich würde die Indexe im Speicher speichern (Platzzulassung), so dass die Lookup in einem Speicher angegeben ist, die Lookup ist im Speicher, dann würde es 1 E / A dauern, um die Daten und Listen-IDs von der Festplatte zu finden. Dann wenden Sie für jede Liste, die Sie durchlaufen möchten, eine weitere Lookup und E / A für alle 10 Objekte in der Liste oder weniger, wenn der Block zwischengespeichert ist.

Die Anzahl der E / A ist nicht schrecklich und ich würde versuchen, den Ort der Listenabschnitte zu behalten, um unnötige E / As zu beseitigen, aber ist es eine bessere Art, dies zu tun? Bin ich Recht, die von dem Objekt getrennten Listen zu versuchen, oder sollte ich die Methoden zum Speichern mit den Daten des Objekts in Betracht ziehen. Meine Sorge, das zu tun, ist, dass eine Liste wächst, dass es in eine andere Liste ausgeführt wird, und muss dann fragmentiert werden, und dies kann komplizierter werden. Alle Vorschläge werden geschätzt und danke im Voraus.

Answer 1

Ihre Vorstellung davon, diese erweiterbaren Listen zu haben, ist gut. Ich denke, Ihre Erklärung fehlt einiger Details (dh: Bestellgelistete oder nicht, was meinen Sie damit, indem Sie versuchen, Listen von Objekten zu trennen, ein Diagramm dieser Listen können helfen).

Ich würde einen sortierten Index im Speicher zum schnellen Zugriff aufbewahren. Der Index hätte Listen-ID und Speicherort auf der Festplatte. Wenn Sie sich an Range-Abfragen interessieren, gehen Sie mit einem B-Baumansatz, ansonsten können Sie einen HashMAP verwenden, um diese Intences zu speichern.

Eine weitere Verbesserung, wenn Sie auf den Listen suchen, soll sie sortiert halten ... oder zumindest sortiert sortiert, so dass Sie ähnliche Listen in demselben Chunk gruppieren können. Dies würde die Suche in den Listen beschleunigen, wenn Sie alle so oft speichern, um den Speicher zu speichern, die Grenzen jedes Chunks (Knoten mit Werten B / W 1-9, 10-25 usw.). Merge Sort ist wahrscheinlich die beste Sortierung für Listen. Oder noch besser, wenn Sie Knoten in den Listen in den richtigen Ort einfügen, sodass die Liste immer sortiert ist. Dann schauen Sie mit binärer Suche nach oben. Wenn Daten nicht ordnungsgemäß indexiert und nicht sortiert sind, werden Sie mehrmals für Abfragen zur Festplatte gehen, und in diesem Fall geben Sie in diesem Fall eine lineare Zeit wegen der Plattenzeit.

Sie können auch Datenknoten der 10% angesehensten Knoten / Listen erheben.

Abhängig von der Größe dieser Listen (und wie viele C-Brocken Sie für sie haben), können Sie einige RAID verwenden, damit Sie einige parallele Lese- / Schreibvorgänge erhalten können.