Carleton University
Technical Report TR-77
July 1985
Linearizing the Directory Growth in Order Preserving Extendible Hashing
E.J. Otoo
Abstract
We propose a method of implementing an order preserving extendible hashing scheme using a balanced hirarchical directory. The directory is implemented as a balanced m-way tree where m = 28 for some predefined constant 0. This approach gives an almost linear growth in the directory size for both uniform and nonuniform key distributions at the expense of possible one extra disk. Given records whose pseudo-keys are w-bit nonnegative integers, each of value K’ < M = zw , such that the records are grouped into pages of capacity C records, a record retrieval is achieved in at most >. = (w – log2 C)/0 disk accesses.