Implementation of multi-key extendible hashing as an access method for a relational DBMS

Extendible hashing addressing schemes have been introduced to resolve collisions and improve storage utilization by dynamically adjusting the address space and modifying the hash function. Recently, generalizations of extendible hashing have been proposed which allow multi-attribute keys to be used for improved partial-match query performance. In this paper the design and implementation of a multi-key extendible hashing access method for a relational DBMS is presented. The results of an experimental evaluation of performance of multi-key extendible hashing in a testbed relational DBMS suggest that for a wide class of queries it constitutes a viable alternative to ISAM-like files. The limitations of multi-key extendible hashing files and research problems which have to be solved before a practical access method for a relational DBMS can be developed are also discussed.