Premium
Efficient combination of index tables and hashing
Author(s) -
Quittner Pál
Publication year - 1983
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380130602
Subject(s) - table (database) , linear hashing , index (typography) , hash table , computer science , dynamic perfect hashing , hash function , database index , auxiliary memory , database , perfect hash function , search engine indexing , double hashing , information retrieval , operating system , computer security , programming language
It is shown that for data stored on direct access devices access time can be reduced without increasing storage demand, through a single level index table which itself is accessible by hashing. If the complete index table can be stored in main memory this method is always superior to direct hashing and to sequentially organized index tables. If the index table is stored on disk it always yields smaller access time than multi‐level index tables and—depending on the size of the index table and on the number of records per track—it is comparable or better than hashing the data directly. Expressions are given to determine in this case which method is more efficient.