Performance Analysis of the Generalised Disc Modulo Allocation Method for Multiple Key Hashing Files on Multi-disc Systems

In an information retrieval system, a file is a collection of records. Since a file is usually large and cannot be wholly stored in primary memory, it is generally divided into buckets and stored in discs. Each time we need information about the file, a query is used to retrieve some records from the disc. And each time the disc is accessed, an entire bucket is brought into primary memory. If the whole file is stored on a disc, only one bucket can be accessed at a time. Since the disc access time is considerably larger than the primary memory retrieval time, the time taken to respond to a query can be simply measured in terms of the number of distinct disc accesses. The number of distinct disc accesses that must be issued to respond to a query is equal to the number of buckets which contain at least one record satisfying the query. If a file is stored on several independently accessible discs, several buckets which reside on different discs can be accessed at one disc access time. In this case the response time to a given query is proportional to the maximum number of buckets needed to be examined on a particular disc. It is obvious that different methods of allocating buckets in the file among discs always result in different response time to a given query. Therefore, given a file designed primarily for all possible queries and an w-disc (m > 1) system, it is important to allocate all buckets into m discs in such a way that the maximal possible disc access concurrency is achieved when examining the required buckets.