Hash indexes in DBMS Theory - Full Explanation

Introduction

Finding data quickly in a large database can be like searching for a needle in a haystack. Hash indexes solve this problem by organizing data so that the database can jump directly to the needed information without scanning everything.

Explanation

Hash Function

A hash function takes a search key and converts it into a number called a hash value. This number points to a specific location where the data might be stored. The function is designed to be fast and to spread keys evenly across possible locations.

The hash function transforms keys into locations to speed up data retrieval.

Buckets

Buckets are storage units where data entries are placed based on their hash values. Each bucket can hold one or more records. When multiple keys hash to the same bucket, the system must handle these collisions carefully.

Buckets group data entries that share the same hash value.

Collision Handling

Sometimes, different keys produce the same hash value, causing collisions. Common methods to handle collisions include chaining, where each bucket holds a list of entries, or open addressing, where the system searches for another free bucket.

Collisions are managed by methods like chaining or open addressing to avoid data loss.

Lookup Process

To find a record, the database applies the hash function to the search key to find the bucket. Then it searches within that bucket for the exact record. This process is usually very fast because it avoids scanning unrelated data.

Lookup uses the hash function to jump directly to the relevant bucket for quick searching.

Limitations

Hash indexes work best for exact-match queries but are not suitable for range queries because hash values do not preserve order. Also, performance can degrade if many collisions occur or if the hash table becomes too full.

Hash indexes are efficient for exact matches but not for range searches or heavily loaded tables.

Real World Analogy

Imagine a large library where books are stored in numbered lockers. Each book's title is converted into a locker number using a special formula. When you want a book, you use the formula to find the locker directly instead of searching every shelf.

Hash Function → The special formula that converts a book title into a locker number.

Buckets → The lockers where books are stored based on the locker number.

Collision Handling → If two books get the same locker number, they are either stacked inside the same locker or placed in nearby lockers.

Lookup Process → Using the formula to find the locker and then looking inside for the exact book.

Limitations → You cannot find books by alphabetical order easily because lockers are assigned by the formula, not by title order.

Diagram

Diagram

┌───────────────┐
│ Search Key    │
└──────┬────────┘
       │ Hash Function
       ▼
┌───────────────┐
│ Hash Value    │
└──────┬────────┘
       │ Points to
       ▼
┌───────────────┐
│ Bucket        │
│ ┌───────────┐ │
│ │ Record 1  │ │
│ │ Record 2  │ │
│ │ ...       │ │
│ └───────────┘ │
└───────────────┘

This diagram shows how a search key is converted by a hash function into a hash value that points to a bucket containing one or more records.

Key Facts

Hash Function → A function that converts a search key into a numeric hash value.

Bucket → A storage location that holds data entries sharing the same hash value.

Collision → When two different keys produce the same hash value.

Chaining → A collision handling method where each bucket holds a list of entries.

Open Addressing → A collision handling method that finds another free bucket for the colliding entry.

Exact-match Query → A search that looks for records matching a specific key exactly.

Code Example

DBMS Theory

class HashIndex:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        # Check if key exists and update
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return
        # Otherwise, add new
        self.buckets[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        return None

# Example usage
index = HashIndex()
index.insert('apple', 'A fruit')
index.insert('car', 'A vehicle')
print(index.search('apple'))
print(index.search('car'))
print(index.search('banana'))

Common Confusions

Hash indexes can be used for range queries.

Hash indexes can be used for range queries. Hash indexes do not preserve order, so they cannot efficiently support range queries like finding all keys between two values.

Collisions mean data is lost or overwritten.

Collisions mean data is lost or overwritten. Collisions are handled by methods like chaining or open addressing to ensure all data is stored safely without loss.

Hash functions always produce unique values.

Hash functions always produce unique values. Hash functions can produce the same value for different keys, which is why collision handling is necessary.

Summary

Hash indexes use a hash function to convert keys into bucket locations for fast data access.

Collisions happen when different keys map to the same bucket and are handled by chaining or open addressing.

Hash indexes are great for exact-match searches but not suitable for range queries.

Practice

1. What is the primary purpose of a hash index in a database?

easy

A. To store data in sorted order

B. To speed up range queries

C. To compress data for storage

D. To speed up exact key lookups

Solution

1. Step 1: Understand the function of hash indexes

   Hash indexes convert keys into hash values to quickly find exact matches.

2. Step 2: Compare with other index types

   Unlike B-tree indexes, hash indexes do not support range queries or sorting.

3. Final Answer:

   To speed up exact key lookups -> Option D

4. Quick Check:

   Hash index = exact key lookup speed [OK]

Hint: Hash indexes are for exact matches, not ranges [OK]

Common Mistakes:

• Thinking hash indexes support range queries
• Confusing hash indexes with sorted indexes
• Assuming hash indexes compress data

2. Which of the following is the correct syntax to create a hash index on a column named user_id in SQL (assuming the database supports hash indexes)?

easy

A. CREATE INDEX idx_user ON users USING HASH (user_id);

B. CREATE HASH INDEX idx_user ON users (user_id);

C. CREATE INDEX idx_user ON users (user_id) HASH;

D. CREATE INDEX idx_user HASH ON users (user_id);

Solution

1. Step 1: Recall standard SQL syntax for hash indexes

   The correct syntax uses CREATE INDEX with USING HASH to specify the index type.

2. Step 2: Analyze each option

   CREATE INDEX idx_user ON users USING HASH (user_id); correctly places USING HASH after the index name and before the column list.

3. Final Answer:

   CREATE INDEX idx_user ON users USING HASH (user_id); -> Option A

4. Quick Check:

   Syntax for hash index = CREATE INDEX ... USING HASH ... [OK]

Hint: Use 'USING HASH' after index name to specify hash index [OK]

Common Mistakes:

• Placing HASH keyword incorrectly
• Omitting USING keyword
• Using non-standard syntax unsupported by SQL

3. Consider the following SQL query on a table with a hash index on email column:

SELECT * FROM users WHERE email = '[e-mail]';

What is the expected behavior of the database when using the hash index?

medium

A. It performs a range scan on the email column

B. It scans the entire table because hash indexes do not support equality

C. It performs a fast exact match lookup using the hash index

D. It returns an error because hash indexes cannot be used in WHERE clauses

Solution

1. Step 1: Understand hash index usage in equality queries

   Hash indexes are designed to quickly find rows matching an exact key value.

2. Step 2: Analyze the query condition

   The WHERE clause uses equality on the indexed column, so the hash index is used efficiently.

3. Final Answer:

   It performs a fast exact match lookup using the hash index -> Option C

4. Quick Check:

   Equality query + hash index = fast lookup [OK]

Hint: Hash indexes speed up exact equality queries [OK]

Common Mistakes:

• Thinking hash indexes do full table scans
• Confusing hash index with range scan
• Assuming hash indexes cause errors in queries

4. A developer created a hash index on the phone_number column but notices that queries with LIKE '%1234' are slow. What is the most likely reason?

medium

A. The hash index is corrupted and needs rebuilding

B. Hash indexes do not support pattern matching or partial searches

C. The database does not support hash indexes on numeric columns

D. The query optimizer ignores all indexes for LIKE queries

Solution

1. Step 1: Understand hash index limitations

   Hash indexes only support exact key lookups, not pattern matching or partial searches.

2. Step 2: Analyze the query pattern

   The LIKE '%1234' pattern searches for suffix matches, which hash indexes cannot optimize.

3. Final Answer:

   Hash indexes do not support pattern matching or partial searches -> Option B

4. Quick Check:

   Hash index ≠ pattern matching support [OK]

Hint: Hash indexes only speed exact matches, not LIKE patterns [OK]

Common Mistakes:

• Assuming hash indexes speed up all LIKE queries
• Blaming index corruption without evidence
• Thinking numeric columns can't have hash indexes

5. You want to optimize a database table for fast lookups on a customer_id column, but also need to efficiently query ranges of order_date. Which indexing strategy is best?

hard

A. Create a hash index on customer_id and a B-tree index on order_date

B. Create hash indexes on both customer_id and order_date

C. Create a B-tree index on customer_id and no index on order_date

D. Create no indexes and rely on full table scans

Solution

1. Step 1: Match index types to query needs

   Hash indexes are best for exact key lookups like on customer_id.

2. Step 2: Use B-tree indexes for range queries

   B-tree indexes efficiently support range queries, so use it on order_date.

3. Final Answer:

   Create a hash index on customer_id and a B-tree index on order_date -> Option A

4. Quick Check:

   Hash for exact, B-tree for range queries [OK]

Hint: Use hash for exact keys, B-tree for ranges [OK]

Common Mistakes:

• Using hash index for range queries
• Not indexing columns needed for fast queries
• Relying on full scans for large tables