Index: A list of key values and the location of their associated records
- Is transferred to main memory when the indexed file is opened
- Index is stored in mass storage as a separate file
An indexed file is made of a data file, which is a sequential file, and an index.
The index itself is a very small file with only two fields: the key of the sequential file and the address of the corresponding record on the disk.
• Each record has a key field
• The storage space is divided into buckets
• A hash function computes a bucket number for each key value
• Each record is stored in the bucket corresponding to the hash of its key
Collisions in Hashing
• Collision: The case of two keys hashing to the same bucket
– Major problem when table is over 75% full
– Solution: increase number of buckets and rehash all data
A hashed file is a random-access file in which a function maps a key to an address.
In direct hashing, the key is the address, and no algorithm manipulation is necessary.
KeyAddress = HashFunction(Key)Address
In modulo division hashing, the key is divided by the file size. The address is the remainder plus 1.