Course contentsShow
← Computer Science
Lesson 1689 of 2,87238. Database Transactions and IndexingFree lesson

Hash Index Structure

Understand the internal structure of hash indexes: hash functions, buckets, and the mapping from keys to disk locations.

Hash Index Structure

What you'll learn: You'll understand how hash indexes physically organize data using hash functions, buckets, and key-to-location mappings.

The Internal Architecture

A hash index works like a giant filing cabinet with numbered drawers. When you want to store or find a record, you don't search sequentially—you apply a hash function to the key, which tells you exactly which drawer (bucket) to open.

Core Components

Hash Function
A mathematical function that takes your search key (like a customer ID or email) and converts it into a bucket number. For example, hash(key) = key % 1000 might map any key to one of 1,000 possible buckets.

Buckets
Storage locations on disk where records (or pointers to records) are kept. Each bucket has a fixed address and can hold multiple entries. Think of them as labeled slots in memory or disk blocks.

Key-to-Location Mapping
The process works like this:

  1. You provide a search key
  2. The hash function computes: bucket_number = hash(key)
  3. The index jumps directly to that bucket's disk location
  4. It scans entries within that bucket to find your exact record

Why This Structure Matters

Unlike B-Trees that traverse multiple levels, hash indexes offer O(1) average-case lookup—one hash computation, one disk read to the bucket. However, if multiple keys hash to the same bucket (collisions), that bucket might overflow into a linked chain of additional disk blocks, degrading performance.

The structure is simple: an array of bucket pointers, each pointing to a disk page. Compact, fast for equality searches (WHERE id = 42), but useless for range queries since nearby keys scatter across random buckets.

Key Takeaway:
Hash indexes use a hash function to map keys directly to bucket addresses on disk, enabling constant-time lookups for exact-match queries but requiring collision handling when multiple keys share the same bucket.