"Platzsparende" und "schnelle" Indizes erzeugen

T

tuxedo

Gast
Hallo zusammen,

ich beschäftige mich gerade mit dem Speichern von Datensätzen in einer File und dem "schnellen wiederfinden" dergleichen.

Bei Datenbanken gibt's IDs. Bei Dateisystemen den Dateinamen. Das ganze möchte ich jetzt mit Java innerhalb einer eigenen Datei auf die gleiche Weise machen: Also Datensatz anhand seines Hashs/seiner ID (UUID?) in eine File schreiben und auch wiederfinden ...

Hab mal geschaut wie das bei der HashMap funktioniert:

Da wird der "key" gehashed und mit einer Shift-Operation über die aktuelle Länge/Größe des Datenarrays ein Index ausgerechnet. Ist es Zeit das Array zu vergrößern (weil langsam kein Platz mehr ist), so wird ein doppelt so großes Array erzeugt, und alle Indizes mit der neuen Array-Größe neu berechnet und die Daten umsortiert.

Klingt super. Nur geht das bei einer File nicht ohne jede Menge IO-Operationen: Wenn ich 1.000.000 Einträge in der File habe und die File, sagen wir 100MB groß ist und es jetzt an der Zeit wäre die Dateigröße zu verdoppeln, dann müsste ich 1Mio Einträge mit einer Kapazität von etwa 100MB innerhalb der Datei umkopieren... --> Sehr unschön.

Hat jemand nen Plan wie das DBs machen? Ja, ich weiß, da steckt jede Menge intelligenter Code und viele super-intelligente Algos drinnen. Aber es muss doch da eine "brauchbare" kleine Lösung für geben?

Ich stell mir vor dass das beim Dateisystem auch recht "einfach" geht: Hat man den Namen und Pfad zur File, weiß man wo sie sich befindet. Okay: Bei einer Datei ist das ja auch so: Weiß man an welchem Index in der Datei sich ein Datensatz befindet, hat man ihn. Ich Muss jetzt nur eine ID/Hash/... auf die Position abbilden :-( (einfacher gesagt als getan ...)

Einfach die File so groß machen dass ich sie nie vergrößern muss wäre u.U. Platzverschwendung auf der einen Seite, und auf der anderen Seite "einengung", da der Platz ja "begrenzt" ist...

Any ideas? Mir fehlt das eine oder andere Schlagwort um mit google weiter zu kommen...

- Alex

P.S. Mir geht's hauptsächlich um den Lerneffekt.
P.P.S. Nein, nicht den dass man sowas nicht selbst machen sollte ...Den anderen mit dem "verstehen wie's funktioniert"...
 
B

bygones

Gast
Lucene ist ja gross in dem Bereich - da opensource, kannst du ja mal bei denen vorbeischauen
 

Landei

Top Contributor
Ich würde es wie dazumal DBF machen: Alle Datensätze (mit fester Länge) hintereinander in eine Datei knallen, und den Index (also im Prinzip das Hash-Array) in einer separaten Datei halten. Hash-Kollisionen sind natürlich eine gewisse Herausforderung...
 

Kr0e

Gesperrter Benutzer
Ist vlt ein völlig blöder Tipp, aber wer weiß:

Mit Jdk7 ist es ja möglich mit dem FileSystem provider für ZipFiles, eine ZipFile als DatenSystem zu betrachten. Sprich Dateien darin finden, löschen, erstellen (da bin ich mir nicht sicher, sollte aber gehen).
Damit könntest du innerhalb einer Datei Datensätze ablegen. Ob das aber wirklcih performant ist , müsste getestet werden. Aber kann auch sein, dass das so garnicht geht und ich mich total vertan habe. In dem Fall, sorry.

Gruß,
Chris

Edit: Falls die Zipdateien jedes Mal neugeschrieben werden, ist diese Lösung natürlcih mehr als ungeeigent.
 
Zuletzt bearbeitet:

ThreadPool

Bekanntes Mitglied
[...]
Any ideas? Mir fehlt das eine oder andere Schlagwort um mit google weiter zu kommen...

[...]

Ja, verwende keine statische Hashtabelle. ;) Bei statischen Hashkonstruktionen wirst du immer das Problem haben, dass du irgendwann viel Aufwand in das Neubauen der Tabelle stecken musst. Eine Alternative wäre dynamisches Hashing. Die Alternative zu Hashing sind die guten alten Baum-basierten Indexstrukturen. Und egal ob man Hashing oder Bäume verwendet IMHO ist der Grundaufbau des physikalischen Layouts immer irgendwie ein File das aus "Blöcken" besteht die über die Indexstruktur herausgesucht werden können um aus denen dann die Daten zu fummeln.

Ich kann mich noch dunkel an folgendes Buch erinnern Database Management Systems: Amazon.de: Raghu Ramakrishnan, Johannes Gehrke: Englische Bücher Darin gibt es auch einen Abriss über die physische Speicherung und den grundsätzlichen Aufbau eines DBMS.
 
T

tuxedo

Gast
@Landei
Ja, so hatte ich das ja vor. Aber auch die HashIndex-File will gewartet werden... Das eigentliche Problem hat man damit nur von einer Datei in die nächste verlagert. Der einzige Vorteil der sich dadurch ergibt: Die HashIndex File ist nicht ganz so groß wie die Daten-File, wmit das umsortieren/re-hashen schneller sein sollte.

@bygones
Danke, ich werd' mal reinschauen. Viel Hoffnung hab ich aber nicht.. ist ja ein recht großes Projekt.

@Kr0e
Daran hab ich auch schon gedacht. Für "normale" Dateioperationen ist das sicher schnell genug. Aber für viele kleine lese/schreibzugriffe geht da die Performance mit ziemlicher Sicherheit in die Knie. Aber du hast recht: Ohne es zu testen ist das nur eine nichtbewiesene Annahme.

@ThreadPool
Bei statischen Hashkonstruktionen wirst du immer das Problem haben, dass du irgendwann viel Aufwand in das Neubauen der Tabelle stecken musst.
Hab jetzt ne Nacht drüber geschlagen (und jetzt deine Antwort gelesen). Deine Aussage bestätigt meine nächtlichen Überlegungen... Der "Hash->Index" Algo muss irgendwie an die Filegröße gebunden sein. Ändert sich die, müssen sich die Hashs ebenfalls ändern. Ergo: Aufwendiges neusortieren/re-hashen.

Eine Alternative wäre dynamisches Hashing.

Muss ich mal nach googeln.

Die Alternative zu Hashing sind die guten alten Baum-basierten Indexstrukturen. Und egal ob man Hashing oder Bäume verwendet IMHO ist der Grundaufbau des physikalischen Layouts immer irgendwie ein File das aus "Blöcken" besteht die über die Indexstruktur herausgesucht werden können um aus denen dann die Daten zu fummeln.

Hab ich mir auch schon grob angesehen. Aber ales was ich in meinen Unterlagen vom Studium dazu gefunden habe ist eher "theoretischer" Natur :-( Prinzipiell scheint das aber schon in die richtige Richtung zu gehen.

Ich kann mich noch dunkel an folgendes Buch erinnern Database Management Systems: Amazon.de: Raghu Ramakrishnan, Johannes Gehrke: Englische Bücher Darin gibt es auch einen Abriss über die physische Speicherung und den grundsätzlichen Aufbau eines DBMS.

Danke für den Tipp. Ich werd's mir anschauen.

Gruß
Alex

[EDIT]Über "dynamische Hashs" bin ich eben hier ran geraten: B+-Baum ? Wikipedia ... Liest sich recht interessant.[/EDIT]
 
Zuletzt bearbeitet von einem Moderator:

Kr0e

Gesperrter Benutzer
Hm, mir ist eben noch eingefallen, dass es vlt noch ein weiteres Problem geben könnte:

Was ist, wenn das Programm, dass auf die Datei grade zugreift, abschmiert und ggf. nur die Hälfte dessen speichern konnte, was ursprünglich angedacht war. So einer Art Transaction wie bei Datenbanken müsste man dann vlt noch oben drauf setzen. Wieso nimmst du eigentlcih nicht einfach eine kleine, schlanke NoSQL datendank ?

Ich dachte vlt. an Orient Technologies - Open source solutions built around the Orient DB oder ähnlcihes..


Und neben B+ gibts auch noch Red?black tree - Wikipedia, the free encyclopedia
 
Zuletzt bearbeitet:
T

tuxedo

Gast
Wie ich schon schrieb: Ich will das "dahinter" verstehen. Da bringt's mir nox wenn ich als backend für mein backend ein fertiges NoSQL benutze.

Das mit der Transaction: Jepp, soweit bin ich aber noch nicht.

Den Red-Black-Tree hab ich schon gesehen... Danke.

- Alex
 

Landei

Top Contributor
Was ist, wenn das Programm, dass auf die Datei grade zugreift, abschmiert und ggf. nur die Hälfte dessen speichern konnte, was ursprünglich angedacht war. So einer Art Transaction wie bei Datenbanken müsste man dann vlt noch oben drauf setzen.

Vor Operation Sicherheitskopie erstellen, nach Operation Sicherheitskopie löschen. Alles andere wäre Overkill.
 
S

Spacerat

Gast
Eigentlich hat Landei die Lösung ja schon gebracht... das Ganze heisst Indexsequentielle Datenspeicherung. Man hat eine Datei in welcher die Daten liegen, neue Datensätze werden einfach angehängt. Dann kann man ein oder mehrere Dateien (pro Suchindex/-feld eine) erstellen, welche den Hash, die ID oder was auch immer mit einem Pointer in die Datendatei verknüpfen (Map). Zum Sortieren einer solchen DB muss nicht mal mehr die Datendatei angefasst, geschweige denn komplett geladen werden, man sortiert halt nur den Index.
[EDIT]Das geht aber auch mit Datensätzen unterschiedlicher Länge. Allerdings müssen dazu bereits 2 Werte (Pointer und Länge) gespeichert werden, Datensätze ändern (in ihrer Länge) wird dann aber schwierig, weil...
Um Datensätze zu Löschen, markiert man ihn in der Indexdatei mit einem ungültigen Pointer (und ggf. auch mit einer ungültigen Länge). Der Nachteil -> Fragmentierung der Datendatei. Bei Datendateien mit Datensätzen gleicher Länge kein Problem. Ein neuer Datensatz passt dann auch irgendwo mitten rein, wo vorher einer gelöscht wurde. Ein Kompromiss bietet dass Verfahren, wenn man Datensatzblöcke speichert.
Und noch was: Einen Hash von ganzen Datensätzen benötigst du nicht, besser gesagt, du hast bereits einen. Den Pointer in die Datendatei. Besser geht's nicht.[/EDIT]
 
Zuletzt bearbeitet von einem Moderator:

Ähnliche Java Themen

Neue Themen


Oben