Re: Free Space Map data structure

Hannu Krosing wrote:
>   index   tree node  binary mask  mask bits
>     0        0          00000         
>     1        0-1        0000?         1
>     2        1          00001         
>     3        0-3        000??         2
>     4        2          00010         
>     5        2-3        0001?         1
>    ...
>    31        0-31       ?????         5
> ...32........16.........10000.........
> 
> seems to be a simple pattern

Oh, I see. I was thinking that the tree would be of the same height on 
all branches, but your method seems simpler. Though it meens that 
existing nodes need to be assigned to new parents as the tree grows.

Now how to extend this to n-ary trees? Assuming we use a normal binary 
tree stored in an array the usual way, within page, we can treat the FSM 
pages as nodes with fanout of (BLCKSZ - size of headers)/2.

Thanks to the large fanout, the height of that tree is not large, max 3 
levels with default block size (*) and not much more than that with 
smaller block sizes. One idea is to use a separate "fork" for each 
level, that would keep the math simple.

(*) We need to cover max 2^32 heap pages == 2^32 leaf nodes. You can fit 
~4000 leaf nodes on a page. 4000^3 > 2^32.

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