完整後設資料紀錄
DC 欄位語言
dc.contributor.authorCHANG, YIen_US
dc.contributor.authorLEE, CIen_US
dc.date.accessioned2019-04-02T05:59:14Z-
dc.date.available2019-04-02T05:59:14Z-
dc.date.issued1995-09-01en_US
dc.identifier.issn0020-0255en_US
dc.identifier.urihttp://dx.doi.org/10.1016/0020-0255(95)00048-Ten_US
dc.identifier.urihttp://hdl.handle.net/11536/149136-
dc.description.abstractThe 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 dynamic hashing scheme called climbing hashing, which requires no index and has 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. In climbing hashing, when a split occurs, the relative position of the new page (into which a data record may move), to the current page (where the data record is now), is proportional to the number of full expansions. Therefore, it seems like the data record is climbing in the files. (Note that a level is defined as the number of full expansions that have happened thus far.) From our performance analysis, given a fixed load control, the proposed scheme can achieve nearly 96% storage utilization as compared to 78% storage utilization by using linear hashing, which is also verified by a simulation study. Moreover, the proposed scheme can be generalize to have the growth of a file at a rate of n+t-1/n. per full expansion, where t is an integer larger than 1. As t is increased, the average number of overflow pages per home page is reduced, resulting in a decrease of the average number of disk accesses for data retrieval.en_US
dc.language.isoen_USen_US
dc.titleCLIMBING HASHING FOR EXPANSIBLE FILESen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/0020-0255(95)00048-Ten_US
dc.identifier.journalINFORMATION SCIENCESen_US
dc.citation.volume86en_US
dc.citation.spage77en_US
dc.citation.epage99en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:A1995RV24100005en_US
dc.citation.woscount1en_US
顯示於類別:期刊論文