On Mon, Apr 4, 2011 at 8:50 PM, Robert Haas
<robertmhaas@gmail.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.