ESTIMATING BLOCK ACCESSES IN A B+-TREE WHOSE LEAF RECORDS ARE OF ARBITRARY SIZE†

摘要

For batched searching of a B+-tree file, previous formulas which estimate the number of block accesses fail when the blocking factor at the leaf level is less than one. We overcome this weakness by developing both an exact formula and an approximate formula to estimate the number of block accesses in a batched search of a B+-tree file where the blocking factor at the leaf level may be less than one. © 1997 Elsevier Science Ltd