On Mon, Jun 27, 2011 at 10:32 PM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:
I didn't have an estimate yet, but I'm working on it.
Now, it seems that I have an estimate.
N - total number of itups
B - avg. number of itups in page
H - height of tree
K - avg. number of itups fitting in node buffer
step - level step of buffers
K = 2 * B^step
avg. number of internal pages with buffers = 2*N/((2*B)^step - 1) (assume pages to be half-filled)
avg. itups in node buffer = K / 2 (assume node buffers to be half-filled)
Each internal page with buffers can be produces by split of another internal page with buffers.
So, number of additional penalty calls = 2*N/((2*B)^step - 1) * K / 2 =(approximately)= 2*N*(1/2)^step
While number of regular penalty calls is H*N
Seems that fraction of additional penalty calls should decrease with increase of level step (while I didn't do experiments with level step != 1).
Also, we can try to broke K = 2 * B^step equation. This can increase number of IOs, but decrease number of additional penalty calls and, probably, increase tree quality in some cases.
------
With best regards,
Alexander Korotkov.
