Expressions for batched searching of sequential and hierarchical files

Publisher Website
Google Scholar
Abstract
Batching yields significant savings in access costs in sequential, tree structured, and random files. A direct and simple expression is developed for computing the average number of records/pages accessed to satisfy a batched query of a sequential tile. The advantages of batching for sequential and random files are discussed. A direct equation is provided for the number of nodes accessed in unhatched queries of hierarchical files. An exact recursive expression is developed for node accesses in batched queries of hierarchical files. In addition to the recursive relationship, good, closed-form upper- and lower-bound approximations are provided for the case of batched queries of hierarchical files.