Re: Free Space Map data structure

On Tue, 2008-04-08 at 13:38 +0300, 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
> 
> ------------
> Will work on this a little more
 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   6        3          00011            7        0-7        00???         3   8        4
  00100            9        4-5        0010?         1  10        5          00101           11        4-7        001??
       2  12        6          00110           13        6-7        0011?         1  14        7          00111
 15        0-15       0????         4  16        8          01000           17        8-9        0100?         1  18
   9          01001           19        8-11       010??         2  20        10         01010           21
10-11     0101?         1  22        11         01011           23        8-15       01???         3  24        12
  01100           25        12-13      0110?         1  26        13         01101           27        12-15      011??
       2  28        14         01110           29        14-15      0111?         1  30        15         01111
 31        0-31       ?????         5
 
...32........16.........10000.........

seems to be a simple pattern

for each node row (each second row) take binary representation of 
next row, start from end and replace all zeros up to and including 
rightmost one with mask bits.

mask 011?? means (data and 11100) == 01100

I will try to work out some experimental/sample code in python for find
and update in the evening.

---------------
Hannu