標題: Alternating hashing for expansible files
作者: Chang, YI
Lee, CI
資訊工程學系
Department of Computer Science
關鍵字: access methods;dynamic storage allocation;file organization;file system management;hashing
公開日期: 1-一月-1997
摘要: In this paper, we propose a generalized approach for designing a class of dynamic hashing schemes which require no index and have the growth of a file at a rate of n+1/n per full expansion, where n is the number of pages of the file, as compared to a rate of two in linear hashing. Based on this generalized approach, we derive a new dynamic hashing scheme called alternating hashing, in which, when a split occurs in page k, the data records in page k will be redistributed to page k and page (k + 1), or page k and page (k - 1), according to whether the value of level dis even or odd, respectively. (Note that a level is defined as the number of full expansions happened so far.) From our performance analysis, given a fixed load control, the proposed scheme can achieve nearly 97% storage utilization as compared to 78% storage utilization by using linear hashing.
URI: http://dx.doi.org/10.1109/69.567061
http://hdl.handle.net/11536/789
ISSN: 1041-4347
DOI: 10.1109/69.567061
期刊: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume: 9
Issue: 1
起始頁: 179
結束頁: 185
顯示於類別:期刊論文


文件中的檔案:

  1. A1997WQ61200015.pdf