Hash Index

Last updated Nov 8, 2022 Edit Source

Idea: use a hash table

1. Take a search key and hash it into an integer in the range of 0 to B-1 where B is the number of buckets
2. A bucket array holds the headers of B linked lists, one for each bucket
3. If a record has search key K, store the record by linking it to bucket list number h(K) Implementations
4. We can directly hash a key which points to the record

2. Add a level of indirection: use an array of pointers to blocks to represent the buckets rather than an array holding data itself

Bucket overflow can be handled naively by adding additional pointer to a separate block.

If the number of buckets is fixed from the start, we will end up with many additional pointers to additional overflow buckets. This incurs more I/O as more records are added.

Idea: use only the first i bits output from the hash function to point to a directory.

Increase i when overflow: Update the directory structure: Delete implementations:

1. Merge blocks when removing record
2. Do not merge blocks at all

Unable to allocate different directory for duplicate keys:

i. 2 I/O ii. All blocks needs to be searched: 11 I/O a. Hash index on ID b. B+ tree index on ID to support better range query c. Multi key index on ID and name