Re: Free Space Map data structure

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Tue, Apr 8, 2008 at 6:33 PM, Heikki Linnakangas  wrote:
>  For example:
>
>     9
>   4     9
>  2 4   0 9
>
>  The leaf nodes correspond the heap pages, so page #0 has 2 units of free
> space, page #1 has 4, page #1 is full and page has 9.
>
>  Let's work through a couple of examples:
>
>  To search for a page with 3 bytes of free space, start from the top. We see
> that the topmost node has value 9, so we know there is a page somewhere with
> enough space.

If I understand your design correctly, this claim isn't true.  If the
topmost node reports 9 bytes free, could you not have seven pages each
with 1 byte free, and an eighth page with 2 bytes free?
         9   4          52    2    2    3
1 1 1 1 1 1 1 2

So you'd actually end up walking two levels down the left hand side of
the tree, discovering not enough space, and then walking two levels
down the right hand side to again discover not enough space.

(Apologies if the above is somehow misguided)

Otherwise seems like a cool structure.

Cheers,
BJ
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: http://getfiregpg.org

iD8DBQFH+zLI5YBsbHkuyV0RAhD+AKDiH3S2vG7bSYMR6JvmUK5nfK/5zQCaA+kA
Gc1wGRty/5zBvRqDBZ/pt+4=
=5tcB
-----END PGP SIGNATURE-----