Re: GSoC proposal: Fast GiST index build

On Mon, Apr 4, 2011 at 8:50 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> OK. Could you briefly describe the algorithm you propose to
> implement, bearing in mind that I haven't read the paper?
>

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.

----
With best regards,
Alexander Korotkov.