Linearizing the directory growth in order preserving extendible hashing

Proposes a method of implementing an order-preserving extendible hashing scheme using a balanced hierarchical directory. The directory is implemented as a balanced m-way tree where m=2^θ for some predefined constant θ. This approach gives an almost linear growth in the directory size for both uniform and nonuniform key distributions at the expense of possibly one extra disk. Given records whose pseudokeys are w-bit nonnegative integers, each of value K´<M=2^w , such that the records are grouped into pages of capacity C records, a record retrieval is achieved in at most λ=(w -log₂C)/θ disk accesses