Hash-Based Indexing

Hash-Based Indexing

Uses a hash function to map search keys to index buckets

Hash Function

Computes bucket number from search key (e.g., h(key) mod N)

Bucket

A page (or set of pages) that holds records with the same hash value

Static Hashing

Fixed number of buckets; doesn't adapt to data growth

Hash Index Use Case

Best for equality searches, not suitable for range queries

Overflow Bucket

Used when a bucket becomes full (chaining)

Bucket Overflow Problem

Leads to long chains and slower lookups

Extendible Hashing

Hash index that grows and shrinks dynamically

Global Depth (Extendible Hashing)

Number of bits used in the directory index

Local Depth (Extendible Hashing)

Number of bits a bucket uses to identify its entries

Directory (Extendible Hashing)

Array of 2^global_depth pointers to buckets

Bucket Split (Extendible Hashing)

Occurs when a bucket is full and local depth < global depth

Doubling Directory (Extendible Hashing)

Occurs when local depth = global depth during a split

Directory Shrinking

Allowed if all buckets have local depth < global depth

Linear Hashing

Hash index without a directory; grows one bucket at a time

Split Pointer (Linear Hashing)

Tracks which bucket to split next

Level (Linear Hashing)

Indicates the number of hash bits in use

Hash Function in Linear Hashing

Two functions used: hlevel and hlevel+1

Linear Hashing Growth

Buckets split gradually; no doubling of directory

Hash Index on Primary Key

Faster equality lookup on unique attribute

Hash Index on Secondary Key

May require overflow pages for duplicates

Clustered Hash Index

Not possible — hashing scatters data, can't cluster records

Unclustered Hash Index

Most common; index points to heap records

Hash Index Advantage

Fast equality lookup with O(1) average-case access

Hash Index Limitation

No support for range or ordered queries