Re: Data management algorithm needed

In article <3C30B611.34D7B51B_at_no_spam_today_thanks.com>, "Chris" <spamfree_at_no_spam_today_thanks.com> wrote:

> I need to manage random-sized blocks of data: fetch them quickly, read
> them, write them, etc. When reading and writing such blocks into memory
> or into a file, there is the problem of fragmentation -- when you delete
> a block, how do you re-use the space, particularly when all blocks are
> of odd sizes?
>
> I know that databases typically handle the problem by organizing
> everything into data pages, where each pages has some free space, and
> when the space is filled the page is split. There are different ways of
> organizing and indexing the pages.
>

The row/page (or row/block) paradigm is basically a bet that each object (row) will be roughly the same size, with little deviation. Grouping into blocks means that sizes can average out, with some shared headroom. It's not the best thing for highly variable-size objects.

There are different approaches for the latter. One place to look is the linux kernel. IIRC it allocates memory in blocks sized at 2**n. If an object goes beyond 2**i bytes, it gets a new block of 2**(i+1) bytes, so the emphasis is on rapid scaling instead of space efficiency. I could be remembering this wrong, but it's worth looking at for a real-world example.

> Does anyone know of a good survey of the techniques for solving this
> class of problems? Perhaps a book or a chapter of a book?

There's a book called
_Garbage_Collection:_Algorithms_for_Dynamic_Memory_Management. I haven't read it, but it gets good reviews. See Amazon. Received on Thu Jan 03 2002 - 10:12:45 CET