A unified analysis of batched searching of sequential and tree-structured files
Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou · ACM Transactions on Database Systems · 1989
A direct and unified approach is used to analyze the efficiency of batched searching of sequential and tree-structured files. The analysis is applicable to arbitrary search distributions, and closed-form expressions are obtained for the expected batched searching cost and savings. In particular, we consider a search distribution satisfying Zipf's law for sequential files and four types of uniform (random) search distribution for sequential and tree-structured files. These results unify and extend earlier research on batched searching and estimating block accesses for database systems.