In the study of data storage and retrieval involving secondary storage devices, for example, magnetic disks, a simplified model of storage that is often used is that each access takes a constant amount of time. However, if some information about the accesses is known, the model should take into consideration the inherent characteristics of the storage devices. In this paper, we assume a more refined model of storage that takes into consideration the seek time, the latency time, and the transmission time of disk accesses separately. We analyze the time required to randomly access a set of records residing on a set of consecutive cylinders on a magnetic disk a number of times, say n, for n ≥ 1. This problem may arise, for example, in the processing of queries that involve several relations in a relational database system. We also analyze the more general situations in which the n operations may represent retrievals, insertions, or deletions, or a combination of them. We assume that the dynamic file structure linear hashing is used for locating and organizing the records. A linear hashing file does not employ any directory and its primary data buckets are assumed to be contiguous, therefore the data area of a linear hashing file corresponds closely to the disk space on a set of consecutive cylinders.

Two new file organizations based on Linear Hashing are proposed for partial match retrieval. The first organization introduces a load-balancing scheme whereby overflow records are stored temporarily in other primary buckets so that the allocation of overflow buckets are deferred. The second organization defers the physical splitting of underflow buckets, so that the records belonging to underflow buckets can be retrieved together. These two techniques are then combined together to form a new variation of Linear Hashing. Compared with the original scheme, the performance of these organizations for partial match retrieval are improved, both in terms of storage utilization and retrieval time.

A hashing-based dynamic file structure is introduced for partial match retrieval using overflow bucket sharing. The sharing of overflow buckets is dynamic in the sense that an overflow bucket is shared by a varying number of primary buckets according to the local conditions of the file. The use and sharing of overflow buckets defers splitting of the data buckets, thereby increasing the storage utilization. For the same reason, plus the fact that the sharing is dynamic, the growth of the directory is slowed down. Under the proposed organization, the records are stored more compactly in the data buckets, and for those partial match queries in which few attributes are specified, groups of neighboring directory entries have high probability of being referenced together, so that the retrieval costs for these types of partial match queries are reduced. This file organization is found to be space efficient and is also time efficient for queries in which the number of specified attributes is small.