Re: GSoC proposal: Fast GiST index build

The technique can be very briefly described in following rules. 

M = number of index keys fitting in RAM;

B = number of index keys in one page;

1) Additional buffers of M/(2*B) pages each is attached to all nodes of some levels. Levels are selected with step floor(log(M/4B, B))), leaf nodes don't contain buffers. I.e. nodes in levels i*floor(log(M/4B, B))), i = 1,2,3,... contain buffers (numbering is going from down to up, level 0 contain leaf nodes).

2) When entry reaches node with buffer, it is placed into buffer.

3) When buffer is overflowed it runs down into lower buffers or leaf pages.

4) When split occurs in node with buffer, then this buffers splits into two buffers using penalty function.