optimize human-readable database with index

Question

i need to store a large amount of data - about 10 million entries of the format

unique hash (64 chars), value 1 (5 chars), value 2 (9 chars)

i will be reading and deleting (but not updating) this data in quick succession. for example, i might write 10 lines, then read 3 and delete 3 lines, before moving on to more writes and reads...

its a single threaded desktop program so reads are only initiated after writes and deletes have been completed. i would like to avoid using a database so that the data can be human-readable from the file system and so that people who download and use my program can see it and inspect it for themselves. i expect my users to be running a linux os and my program is written in python.

i have come up with three possible options for how to store this data:

option 1

put the data in a single file. since the hashes are unique i can arrange them in ascending order like an index so as to give log2 N read times. deleting and inserting will happen often and would slow the process down as N gets large.

option 2

use the unique hash as a file name and put the values inside this file. this would be my preferred option so long as there are no obvious performance drawbacks? i know some file systems slow down when a large number of files exist in a single directory. and i really can't make any assumptions about which file system the users of my program will be using. i need to choose a solution which is quick on all file systems.

option 3

use the unique hash to create a directory to store the values in. so for example, if a record has hash abcd then i would create dir and file base_dir/a/b/c/d.txt. does this get around the file system performance issue issue? or is this just as bad as option 2 depending on the type of file system the user is running?

question

so really i'm just looking for help to decide which option to pick. also if you have any other options that are superior to the ones i have listed here i would like to hear them. maybe some database software like mysqli that sores data in human-readable text? that would be ideal really, but i imagine that most databases would use binary for efficiency...

Answer 1

There is a reasonably obvious solution: a directly hashed file store.

To deal with your suggestions:

1. Slowish access, horribly slow delete and insert. Forget it.
2. No file system can give you a million files in reasonable time. Forget it.
3. Doable but complicated to work out a decent scheme. Not my choice.

For a directly hashed file store you divide the file into buckets (say 4000 bytes, holding 80 keys). You devise a hash function of your unique hash that distributes keys evenly across buckets. You place each record in that bucket. You allocate some number of overflow buckets for keys when the bucket they belong in is full.

You can find any record in just over O(1) by a single calculation and a single (bucket) read, followed by searching the bucket for the right record. You can add or delete a record by one extra write. You aim for about 80-90% full, depending on how good your has function is at distributing keys into buckets. if it's too full you will have to go to an overflow bucket too often and that costs performance.

You can easily find details of how to implement this kind of scheme. It's a very old technique from pre-database days. Very fast, reasonably simple and a perfect match for your problem.