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
