Hash Index

A completely different indexing approach from B+ Tree — trading range query ability for blazing fast exact lookups.

How It Works

Apply a hash function to the key → get a bucket location → store row pointer there.

hash('bob@gmail.com') → bucket 42 → row pointer → full row

INSERT email = 'bob@gmail.com'   → hash = 42 → bucket[42]
INSERT email = 'alice@gmail.com' → hash = 17 → bucket[17]
INSERT email = 'carol@gmail.com' → hash = 42 → COLLISION → chain in bucket[42]

Lookup — O(1)

SELECT * FROM users WHERE email = 'bob@gmail.com'

Step 1: hash('bob@gmail.com') → bucket 42     O(1)
Step 2: go to bucket[42]                       O(1)
Step 3: compare email, follow ptr to row       O(1)

Total → O(1)   faster than B+ Tree O(log n)

The Big Weakness — No Range Queries

SELECT * FROM users WHERE age BETWEEN 20 AND 30  -- IMPOSSIBLE with hash index

hash(20) → bucket 91
hash(21) → bucket 14  (completely different bucket!)
hash(22) → bucket 67  (no ordering preserved at all)

Hash vs B+ Tree

	Hash Index	B+ Tree Index
Lookup speed	O(1)	O(log n)
Range queries	Impossible	Fast
ORDER BY	Cannot help	Supports
LIKE queries	Cannot help	Prefix only
Equality (=)	Fastest	Fast
Collision handling	Needed	Not applicable

Where Hash Indexes Are Used

• PostgreSQL: explicit hash index with CREATE INDEX ... USING HASH
• MySQL InnoDB: Adaptive Hash Index (AHI) — automatically built in memory on hot B+ Tree pages
• MySQL MEMORY engine: hash indexes by default

Hash Collisions

• Chaining (most common): Each bucket holds a linked list. Multiple entries per bucket.
• Linear Probing: If bucket full → try bucket+1, bucket+2...
• Worst case: all keys collide → same bucket → degrades to O(n) linear scan