Hash indexes in DBMS Theory - Step-by-Step Execution

Concept Flow - Hash indexes

Start: Query with search key

↓

Apply hash function to key

↓

Compute hash value (bucket address)

↓

Access bucket in hash index

↓

Check bucket for matching record

Yes No↓

Return record

The flow shows how a hash index uses a hash function on a search key to find the bucket address, then accesses that bucket to find the matching record or report it missing.

Execution Sample

DBMS Theory

Search key = 42
Hash function: h(key) = key mod 5
Buckets: 0 to 4
Find bucket for key 42
Check bucket for record

This example shows how a hash function maps a search key to a bucket number to quickly locate the record.

Analysis Table

Step	Action	Input	Hash Function Result	Bucket Accessed	Record Found?
1	Receive search key	42	-	-	-
2	Apply hash function	42	42 mod 5 = 2	-	-
3	Access bucket	-	-	Bucket 2	-
4	Search bucket for key	-	-	Bucket 2	Yes
5	Return record	-	-	-	Record with key 42

💡 Record found in bucket 2, search ends successfully

State Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
search_key	N/A	42	42	42	42
hash_value	N/A	2	2	2	2
bucket_accessed	N/A	N/A	Bucket 2	Bucket 2	Bucket 2
record_found	N/A	N/A	N/A	Yes	Yes

Key Insights - 2 Insights

Why do we use a hash function on the search key?

The hash function converts the search key into a bucket number to quickly locate where the record might be stored, as shown in step 2 of the execution table.

What happens if the record is not found in the bucket?

If the record is not in the bucket, the search ends with no result. This is shown by the 'No' branch in the concept flow after checking the bucket.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash value computed for the search key 42?

A 2

B 5

C 42

D 0

💡 Hint

Check Step 2 in the execution table where the hash function result is shown.

At which step does the system access the bucket in the hash index?

A Step 4

B Step 1

C Step 3

D Step 5

💡 Hint

Refer to the 'Bucket Accessed' column in the execution table.

If the hash function changed to h(key) = key mod 3, which bucket would key 42 map to?

A Bucket 1

B Bucket 0

C Bucket 2

D Bucket 3

💡 Hint

Calculate 42 mod 3 and compare with the bucket numbers.

Concept Snapshot

Hash indexes use a hash function to convert a search key into a bucket address.
The bucket stores pointers to records with keys mapping to it.
Searching involves computing the hash, accessing the bucket, and checking for the record.
This method provides fast direct access but works best for equality searches.

Full Transcript

Hash indexes help databases find records quickly by using a hash function on the search key. The hash function converts the key into a bucket number. The system then looks inside that bucket to find the record. If the record is there, it returns it; if not, it reports no match. This process is fast because it avoids scanning many records. The example shows searching for key 42 using a hash function that takes the key modulo 5, resulting in bucket 2. The record is found in bucket 2, so the search ends successfully.