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