Re: Free Space Map data structure

Hannu Krosing wrote:
> On Tue, 2008-04-08 at 12:26 +0300, Hannu Krosing wrote:
> 
>> Probably we could do without sparse files, if we find an efficient way
>> to compute the "add order" of leaf and parent pages for above algorithm.
> 
> if we always add only the minimal needed set of parents then the order
> will look something like
> 
>  1: 0
>  2: 1 
>  3: (0-1) 
>  4: 2 
>  5: (0-3) 
>  6: 3 
>  7: (2-3) 
>  8: 4
>  9: (0-7)
> 10: 5
> 11: (4-5)
> 12. 6
> 13: (4-7)
> 13: 7
> 14: (6-7)
> 
> seems pretty regular  :)
> 
> and is probably easy to expand into pages

That's what I thought when I started thinking about this, but even after 
spending a good few hours sketching i on a whiteboard, I still couldn't 
figure out what the actual formula behind that is. I feel like I'm 
missing something obvious textbook algorithm here, so please help me out 
if you can spot a pattern in that. If there isn't one, we could build a 
lookup table for enough levels by hand, but...

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com