Hashing schemes have been found to be one of the useful access methods for physical database system implementation. In the last decade several schemes have been proposed to extend the applicability of hashing methods to dynamic files. When a very large database system is considered, besides the space utilization and the retrieval time of records, the space utilization and the retrieval time of the directory also become a major concern. In this paper, we propose a new dynamic hashing scheme, based on extendible hashing, whose directory can grow into a multilevel directory. We compare the proposed scheme to two other schemes, the Extendible Hashing and the Extendible Hashing Tree schemes. The simulation results reveal that the proposed scheme is superior than the other two in the aspect of directory space utilization, especially for files with nonuniform record distribution. Furthermore, this scheme can be easily extended to multikey file systems and also has good performance.
|Original language||English (US)|
|Number of pages||14|
|Journal||IEEE Transactions on Knowledge and Data Engineering|
|State||Published - Sep 1991|
Bibliographical noteFunding Information:
Manuscript received July 1, 1989; revised April 30, 1990. This work was supported in part by NSF Grants MIP-8605297 and DCR-8420935. The authors are with the Department of Computer Science, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 9101533.