ITPEC FE Morning April 2022 Question 29

Hash index — a hash function calculates the storage location from the key, and different keys can give the same result, a collision.

A hash index applies a hash function to the key value and uses the result directly as the storage address, for example the remainder after dividing by the number of buckets. The range of addresses is far smaller than the range of keys, so distinct keys must sometimes map to the same address: with division by 7, keys 10 and 17 both give 3. Such keys are called synonyms, and the index resolves the collision by chaining or by probing another location.

Answer (c)

Why not others:

• •(a) B+ tree index — finds a key by comparisons down a balanced tree of sorted keys, not by calculating an address; each key value has its own leaf entry.
• •(b) Bitmap index — keeps one bit string per distinct column value, one bit per row; nothing is calculated from a key.
• •(d) Inverted index — maps each word or value to the list of records that contain it, as in full-text search; it is looked up, not calculated.

Key rule: Only hashing turns a key into an address by calculation, and because many keys share few addresses, a hashing scheme must always handle collisions.

Databases · AI-written, may contain errors