Random file access in a block based file format I am writing a program to store, retrieve and delete "blocks" of data of varying sizes.

The way it currently works is by keeping a database storing the locations of the blocks and the locations of free space in the file.

The file is split into pages such that in each page there are no two free chunk spaces next to each other (During a delete operation, any free chunks which are adjacent are merged into one bigger chunk)

The problem with this is that I am seeing horrible IO performance when removing a bunch of blocks and inserting new ones of different sizes (blocks range from 1k to about 200k and may be written anywhere in the file provided they fit in an existing free chunk in the file. If no such free chunk is found, a new page is created at the end of the file).

Can anyone suggest a way to improve on this, or maybe point me in the right direction?
A starting point for this would be the heap management algorithms, start perhaps here. I remember Knuth in his Art of Computer Programming has a detailed discussion, I believe in volume 1. The algorithms described are good for RAM, adding in the non-uniform access of rotating disks will be quite a challenge...

Isn't it much simpler to use a database and blobs? Your time is valuable too...