[MUD-Dev] caved in: Algorithms for for storing free space.

[J C Lawrence]

On Sat, 4 Apr 1998 18:45:19 PST8PDT 
Ben Greear<greear at cyberhighway.net> wrote:

> I'm sure this has been done many times before, but any quick hints
> would be welcome.  I want to keep with a single db-file approach,
> wich rules out the (really cool) idea involving powers of 2 that was
> posted recently...

Look at the file formats used for tdbm.  In paticular read the Usenix
paper which details main of the design processes used to arrive at
their final model  (non-stupid people).

Essentially they interspersed the index thru the data sets by using a
paged model, using a chaining structure of directory blocks and data
segments.  I've done tests on it with variant sizes of data blocks.
Its quite as performant as their charts suggest (see the Usenix
paper).

Again, YOODA is another good one to look at.

--
J C Lawrence                               Internet: claw at null.net
(Contractor)                               Internet: coder at ibm.net
---------(*)                     Internet: claw at under.engr.sgi.com
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...