Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.15 No.2, pp.243-271 (March 1999)
Extended Spiral Hashing for Expansible Files1

Ye-In Chang, Chien-I Lee* and Wann-Bay Chang Liaw
Department of Applied Mathematics
National Sun Yat-Sen University
Kaohsiung, Taiwan 804, R.O.C.
* Institute of Information Education
National Tainan Teacher College
Tainan, Taiwan 700, R.O.C.

The goal of dynamic hashing is to design a function and a file structure that allow the address space allocated to the file to be increased and reduced without reorganizing the whole file. In this paper, we propose a new scheme for dynamic hashing in which the growth of a file occurs at a rate of JISE per full expansion, where s and t are given integers and JISE is smaller than two, as compared to a rate of two in linear hashing. (Note that s is used to denote the number of pages of a file before any split occurs in a full expansion, and t is used to denote the number of pages of the file after full expansion is finished through a number of split operations.) Therefore, extended spiral hashing can maintain more stable performance through file expansions and has much better storage utilization than does linear hashing. Basically, the proposed scheme is based on a modified spiral storage approach, in which the load distribution is uniform after a full expansion. Therefore, extended spiral hashing can also provide better performance than can the original spiral storage approach. Moreover, we have used a modified separator strategy for overflow handling such that retrieval of any data record in extended spiral hashing is upper-bounded by two disk accesses. From our performance analysis and simulation, extended spiral hashing can achieve nearly 96% storage utilization as compared to 78% storage utilization using linear hashing and 88% storage utilization using the spiral storage approach.

Keywords: access methods, dynamic storage allocation, file organization, file system management, hashing

Full Text () Retrieve PDF document (199903_04.pdf : 238,517 bytes)

Received August 5, 1996; revised January 10, 1997
Communicated by Arbee L. P. Chen.
1 This research was supported in part by the National Science Council of Republic of China under Grant No. NSC-82-0408-E-110-135.