Approximating block accesses in database organizations

Abstract

When data records are grouped into blocks in secondary storage, it is frequently necessary to estimate the number of blocks X _D accessed for a given query. In a recent paper [1], Cardenas gave the expression X _D = m (1 - (1 - 1/ m ) ^k ), (1) assuming that there are n records divided into m blocks and that the k records satisfying the query are distributed uniformly among the m blocks. The derivation of the expression was left to the reader as an exercise.