Abstract
Since a file is usually stored on a disk, the response time to a query is dominated by the disk access time. In order to reduce the disk access time, a file can be stored on several independently accessible disks. In this paper, we discuss the problem of allocating buckets in a file among disks such that the maximum disk accessing concurrency can be achieved. We are particularly concerned with the disk allocation problem for binary Cartesian product files. A new allocation method is first proposed for the cases when the number (m) of available disks is a power of 2. Then it is extended to fit the cases where m is not a power of 2. The proposed algorithm has a "near" strict optimal performance for a partial match query in which the number of unspecified attributes is greater than a small number (5 or 6).
Original language | English (US) |
---|---|
Pages (from-to) | 138-147 |
Number of pages | 10 |
Journal | BIT |
Volume | 26 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1986 |
Bibliographical note
Funding Information:This work was supported in part by NSF Grant DCR-8405498.
Keywords
- Cartesian product files
- D.4.2
- D.4.3
- D.4.8
- H.3.3
- disk allocation
- file structures
- multi-key hasing
- partial match retrieval