On Mon, Jun 27, 2011 at 10:32 PM, Alexander Korotkov <aekorot...@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.
