Skip site navigation (1) Skip section navigation (2)

Re: Free Space Map data structure

From: "Brendan Jurd" <direvus(at)gmail(dot)com>
To: "Heikki Linnakangas" <heikki(at)enterprisedb(dot)com>
Cc: PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Free Space Map data structure
Date: 2008-04-08 08:54:43
Message-ID: 37ed240d0804080154t4558806bo599ddbffd29e5676@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
-----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          5
 2    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-----

In response to

Responses

pgsql-hackers by date

Next:From: Dave PageDate: 2008-04-08 08:59:08
Subject: Re: Free Space Map data structure
Previous:From: Heikki LinnakangasDate: 2008-04-08 08:33:20
Subject: Free Space Map data structure

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group