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