Performance analysis of a main memory multi-directory hashing technique (Q1209985)

Hashing permits fast access to both disk-based and main memory-based databases. The retrieval time in main memory databases consists of the time to follow the address pointers plus the time to compare the key values. We define optimal search in main memory databases as the search that requires at most one key comparison to locate a record. Extendible hashing becomes impractical when it is adapted to yield optimal search because of its large directory size. Multi-directory hashing techniques can provide significantly improved directory utilization over extendible hashing. The objective of the paper is to analyze the directory utilization of a main memory hashing technique, called Extendible Root Multi-Directory Hashing (ERMH), ERMH uses a tree-structured hash directory of height one. The size of the leaf subdirectories is fixed and the root subdirectory expands to allow for more records. ERMH requires at most one key comparison to locate a record and its expected directory size is \(O(m^{4/3})\), where \(m\) is the number of inserted records.