ABSTRACT FAST SEARCH IN MAIN MEMORY DATABASES

The objective of this paper is to develop and analyze high performance hash based search methods for main memory databasea. We define optimal search in main memory databases as the search that requires at most one key comparison to locate a record. Existing hashing techniques become impractical when they are adapted to yield optimal search in main memory databases be-cause of their large directory size. Multi-directory hash-ing techniques can provide significantly improved direc-tory utilization over single-directory hashing techniques. A multi-directory hashing scheme, called fast search multi-directory hashing, and its generalization, called controlled search multi-directory hashing, are presented. Both methods achieve linearly increasing expected di-rectory size with the number of records. Their perfm-mance is compared to existing alternatives. Index Terms: controlled search, extendible hssh-ing, linear hashing, main memory databases, multi-directory hashing, optimal search, performance analy-sis.