Hash indexes in DBMS Theory - Mini Project: Build & Apply

Understanding Hash Indexes in Databases

📖 Scenario: You are working with a simple database system that uses hash indexes to speed up data retrieval. Hash indexes help find data quickly by using a hash function to map keys to specific locations.Imagine a library where each book has a unique ID number. Instead of searching every shelf, the library uses a hash index to know exactly which shelf to check.

🎯 Goal: Build a basic hash index structure step-by-step to understand how keys map to buckets and how to retrieve data efficiently.

📋 What You'll Learn

Create a dictionary representing data records with unique keys

Define a hash function to map keys to bucket numbers

Use the hash function to create a hash index mapping buckets to keys

Add a final step to retrieve keys from a specific bucket

💡 Why This Matters

🌍 Real World

Hash indexes are used in databases to quickly locate data without scanning the entire dataset, improving search speed.

💼 Career

Understanding hash indexes is important for database administrators and developers to optimize data retrieval and design efficient database systems.

1

Create the data records dictionary

Create a dictionary called records with these exact entries: 101: 'Book A', 102: 'Book B', 203: 'Book C', 304: 'Book D', and 405: 'Book E'.

DBMS Theory

# Create the records dictionary with the given keys and values
# Your code here

Hint

Use curly braces {} to create a dictionary with the given key-value pairs.

2

Define the hash function

Define a function called hash_function that takes a key and returns the remainder when the key is divided by 3 using the modulus operator %.

DBMS Theory

records = {101: 'Book A', 102: 'Book B', 203: 'Book C', 304: 'Book D', 405: 'Book E'}
# Define the hash_function that returns key % 3
# Your code here

Hint

The modulus operator % gives the remainder of division. Use it to map keys to buckets 0, 1, or 2.

3

Create the hash index mapping buckets to keys

Create an empty dictionary called hash_index. Use a for loop with variables key and value to iterate over records.items(). Inside the loop, use hash_function(key) to get the bucket number. Add the key to the list of keys in hash_index for that bucket. If the bucket does not exist, create a new list.

DBMS Theory

records = {101: 'Book A', 102: 'Book B', 203: 'Book C', 304: 'Book D', 405: 'Book E'}
def hash_function(key):
    return key % 3

# Create hash_index dictionary and fill it using a for loop
# Your code here

Hint

Check if the bucket exists in hash_index. If not, create an empty list before adding keys.

4

Retrieve keys from a specific bucket

Create a variable called bucket_to_check and set it to 2. Then create a variable called keys_in_bucket that gets the list of keys from hash_index for bucket_to_check. Use the get() method with an empty list as the default value.

DBMS Theory

records = {101: 'Book A', 102: 'Book B', 203: 'Book C', 304: 'Book D', 405: 'Book E'}
def hash_function(key):
    return key % 3

hash_index = {}
for key, value in records.items():
    bucket = hash_function(key)
    if bucket not in hash_index:
        hash_index[bucket] = []
    hash_index[bucket].append(key)

# Set bucket_to_check to 2 and get keys_in_bucket from hash_index
# Your code here

Hint

Use the get() method on hash_index to safely retrieve keys for the bucket.

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