Re: Looking for a file format

On Sep 24, 6:12 am, Florian Brucker <t...@xxxxxxxxxxxx> wrote:
I have a data structure that could probably be best described as a
collection of linked hash-tables: Each item is a hash, where the keys
differ from item to item. Some of the values of each item's hash can
(and will) be links/pointers/references to other items.

What I'm looking for is a way to store this kind of data on hard disk,
i.e. I'm looking for ideas for a suitable file format. Issues:

- The data is not read-only: Changing values and adding/removing keys of
the hashes is a central point of the whole application.

- The set of possible keys cannot be narrowed down (as they are selected
by the user). Nevertheless one would like to have possibilities to use
the keys in similiar fashion as database columns for searching.

- The data is too big to fit it into RAM as a whole. The format needs to
support a read/write cache in a nice way.

- The links to other items must be stored in a sensible way, i.e.
looking up an item by some kind of id must be supported in a fast way.

So basically this boils down to some kind of mini-filesystem in a file.
I know that I'll probably have to trade speed against file size, etc.,
but right now I'm rather looking for general ideas on how to approach
this problem. I had a hard time finding any information about such
formats, probably because I couldn't think of any good keywords to
search for. Any pointers to papers/implementations/descriptions of
similar systems are greatly appreciated.

Look up (using google or whatever):
sdbm
gdbm
ndbm
pure-db
qdbm
tdb
tdbm
tinycdb

These are on-disk hash tables used to form dictionaries (for the most
part). Occasionally {by the adventurous} they are used as general
purpose database files. A couple of these are read-only after
creation unless you reform the whole thing from scratch.


.

Relevant Pages

  • Looking for a file format
    ... Some of the values of each item's hash can ... i.e. I'm looking for ideas for a suitable file format. ... The set of possible keys cannot be narrowed down (as they are selected ... support a read/write cache in a nice way. ...
    (comp.programming)
  • Re: Hash of hash in perl
    ... > I have data in the following format ... > to populate the above hash of the hash. ... Extracting the keys might be the only speed bump. ...
    (comp.lang.perl.misc)
  • Re: Suggestion for an AES Based Hash Function
    ... amateurs posting here seem to favour cyphers, I go for hash functions. ... Rather than trying to use a strong one-way compression function would ... I have used a fixed set of keys in two places. ... preferred to have the first round keys fixed and to start deriving ...
    (sci.crypt)
  • Suggestion for an AES Based Hash Function
    ... amateurs posting here seem to favour cyphers, I go for hash functions. ... Rather than trying to use a strong one-way compression function would ... The round function ... I have used a fixed set of keys in two places. ...
    (sci.crypt)
  • Re: sort unique
    ... given that a hash table is not ... IMO if the vendor's algorithm does something "obvious", ... function to eliminate keys that hash to the same bucket per some ... strings of random lengths, and two strings are ...
    (comp.lang.lisp)