Welche Möglichkeiten bietet Java um Records in Dateien zu sp

[ixanos]

Welche Möglichkeiten bietet Java um Records in Dateien zu speichern und auszulesen?

--------------------------------------------------------------------------------

Hallo zusammen

Ich habe folgende Record-Struktur:

Record:
int a1;
int[] a2;

Beispiel: Record No1 = 14,{15,25,36}
Record No2 = 67,{15,25,36,45,56,78,89}

Ich möchte diese Records in eine Datei speichern können und dann aber auch die Möglichkeit haben auf beliebiges Record zuzugreifen. Die Datei würde im Regelfall 500.000 Records haben.Und ein normales Szenario wäre zu sagen: Gib mir Das Record No 123000 und es sollte dann etwas in folgender Form zurückgeben: 78, {45,23}. also einen int und ein Array von ints (genaue anzahl variiert von 1 bis 100.000 oder mehr !!!).

RandomAccessFile nehme ich an, kann hier nicht eingesetzt werden da man nicht wissen würde bei welches Byte man anfangen muss zu lesen. Man würde nicht wissen wo das 123000 Record anfängt da das array in jedem Record eine variierende Länge hat, und eins nach dem anderen alle Records auslesen bis das 123000e kommt ist auch keine realistische Lösung.

Hat jemand von euch schonmal so eine Problematik gehabt? Wie sollte man hier vorgehen? Die Datei ist viel zu gross um davon auszugehen dass man genug Speicher hat um diese in ein ArrayList oder Vector zu laden!

Gruss
Ioannis

 

[SlaterB]

viele Menschen hatten schon solche Problem und erfanden sich ein mysteriöses Spezialprogramm,
wie hieß es nochmal? ach ja, Datenbank!

du kannst es natürlich auch in einer Datei speichern,
am besten mit einer Index-Datei dazu, 500.000 mal x Bytes lang,

um den 123.000 Eintrag zu finden, gehe an eine ausrechenbare Position in die Indexdatei,
lies dort die Position in der Hauptdatei, vielleicht noch die Anzahl der zu lesenen Bytes,
und greife in der Hauptdatei auf die richtige Stelle zu,

deine seltsame Struktur kannst du zumindest zum Speichern als ein einzelnes int-Array darstellen, Position 0 enthält die Nummer

 

[ixanos]

wenn ich eine index-datei anlegen würde um über diese auf die Hauptdatei zuzugreifen dann würde jede Änderung z.B. des 101 Records ein update für die restlichen 500.000 - 101 Records verursachen. Die Index Datei müsste dann praktisch neu kreiert werden sobald ein einziges Record modifiziert würde, da ja dann die Anfang-Offsets aller Records die nach dem 101 Record sind, nicht mehr stimmen würden.

ich wollte die Datenbank-Lösung erstmal nicht berücksichtigen da dieses die Portabilität der Datei beeinträchtigen würde. Es kann aber sein dass diese unvermeindbar werden wird

 

[SlaterB]

dass sich die Offsets ändern, ist ein Problem der Hauptdatei, nicht der Indexdatei
dort wird nur der Aufwand sichtbar, dies zu verwalten

du könntest ein inkrementelles System einführen,
du hast die Indexdatei, die vielleicht alle x-tausend Änderungen neu aufgebaut wird,
nebenbei hast du noch ein Datei mit den Änderungen (und/ oder im Arbeitsspeicher)
da steht dann 'in Hauptdatei alles nach Position 234.900 um 4020 Bytes nach rechts verschoben'

zur Bestimmung einer Position also den Index aus der Datei lesen und noch im Arbeitsspeicher 1-1000 Schritte durchlaufen,
von denen vielleicht 900 die Position hin und her schupsen,

mit etwas Mühe kannst du vielleicht auch im Hauptspeicher die Änderungen etwas voranalysieren,
so dass für bestimmte Bereiche der Hauptschups schon vorberechnet ist und nur noch 10 Detailschritte berücksichtigt werden müssen

(die 1000 Hauptschupse müssten bei jeder Änderung aktualisiert werden, quasi als Mini-Abbild des Index-Aktualisierens-Problem)


-------
wenn du eh Einträge nur einzeln liest, dann ist generell zu überlegen,
ob du die 500000 Einträge nicht lieber auf 50-500 einzelne Dateien aufteilst,
würde die obigen Probleme um den Faktor 50/ 500 verringern
(aber vielleicht neue machen )

 

[ixanos]

ja. Es ist eine gute Idee, neben der Indexdatei auch eine "Modifications"-Datei anzulegen und ab und zu eine optimierung (Neu-Aufbau der Haupt- und Indexdatei vorzunehmen).

Nur zur Info es handelt sich hier um einen Inverted-Index und das array zeigt die Positionen eines Wortes (Term) innerhalb einer Datei. Deswegen muss man davon ausgehen dass man auf mehrere Records zugreifen würde und nicht nur auf ein einzelnes.

 

[Tellerrand]

wenn ich eine index-datei anlegen würde um über diese auf die Hauptdatei zuzugreifen dann würde jede Änderung z.B. des 101 Records ein update für die restlichen 500.000 - 101 Records verursachen. Die Index Datei müsste dann praktisch neu kreiert werden sobald ein einziges Record modifiziert würde, da ja dann die Anfang-Offsets aller Records die nach dem 101 Record sind, nicht mehr stimmen würden.

Da hiltft zum Beispiel die Einteilung in Blöcke, man teilt also die "Hauptdatei" so auf:
| Inhalt | Blocknumnmer |
Falls ein Eintrag größer ist als die Größe des "Inhalt" Feldes, so nimmt man einfach einen zusätzlichen Block und referenziert ihn als Blocknummer im alten.
Auslesen funktioniert dann nach dem Motto: Lese Inhalt -> Wenn Blocknummer nicht 0 lese den durch "Blocknummer" referenzierten Block.

(Die Größe des "Inhalt" - Feldes ist dann alelrdings immer ein Kompromis zwischen Speicherplatzverschwendung und Zugriffszeit.)

Um nun durch den Löschvorgang keinen Speicherplatz zu verschwenden kann man das selbe Prinziep verwenden, so dass die Blocknummer von leeren Blöcken dann auf den jeweils nächsten leeren Block zeigt.

 

[ixanos]

Ja. Blocks zu benutzen ist eine sehr gute Idee! somit wäre eine Modifikationsdatei nicht mehr notwendig und man könnte mit einer einzigen Datei auskommen. Man könnte dann auch zusäzlich Golomb Coding benutzen um die integers zu komprimieren, somit wäre der benötigte Platz noch weniger. gute Idee. danke.

 

[SlaterB]

wenn die ersten x00.000 Blöcke für den ersten Block jedes Eintrags reserviert sind und es auch nicht mehr Einträge werden als an Reserve freigelassen ist,
dann fällt auch die Indexdatei weg

 

[ixanos]

Ja. Stimmt! Dann wäre auch die Indexdatei überflüssig.
einziger Nachteil hier dass die Offests alle erst ab x00.001 erscheinen würden und deswegen Grosse Zahlen verwendet werden würden. Da ist dann die Komprimierung notwendig. Aber ist sicherlich eine sehr gute Idee.

 

[SlaterB]

naja, wenn alle Offsets über x00.000 liegen, dann kann diese Zahl ja weglassen
und als konstanten Faktor dazurechnen

aber die zusätzlichen Blocks dürften doch so zahlreich sein, dass sie eh von 1 aus schnell in dieser Region sind,
anderenfalls wird wohl soviel Platz freigelassen, dass der Platz für die eine Blockzahl zigfach übertroffen wird ,

na das kann man ewig weiterspinnen

 

[ixanos]

Hallo

Ich möchte mich bei euch ("SlaterB" und "Tellerrand") für eure Unterstützung bedanken.
Dieses Thema ist für mich jetzt als Thread abgeschlossen.

Gruss
Ioannis