Skip to content

Hash Index

In one line

Hash indexes use hash tables for O(1) equality lookups — fastest for = queries but can't do ranges or sorting.

In simple words

A hash index stores key values in a hash table. The key is run through a hash function that maps it to a bucket, where the row location is stored.

Advantages:

  1. O(1) equality lookups — faster than B-Tree's O(log n) for exact matches
  2. Simple structure — less overhead than B-Tree

Disadvantages:

  1. No range queries — can't find values between A and B
  2. No sorting — can't help with ORDER BY
  3. No prefix matching — can't help with LIKE 'abc%'
  4. Hash collisions — multiple keys may hash to the same bucket

Use hash indexes when you only need exact equality lookups (e.g., session ID lookup, key-value stores). PostgreSQL supports hash indexes; MySQL's InnoDB doesn't use them directly (uses adaptive hash caching).

Example

sql
-- Create a hash index (PostgreSQL)
CREATE INDEX idx_session_hash ON sessions(session_id) USING HASH;

-- This query uses the hash index (fast O(1)):
SELECT * FROM sessions WHERE session_id = 'abc123xyz';

-- These queries CANNOT use the hash index:
SELECT * FROM sessions WHERE session_id > 'abc'; -- range: no
SELECT * FROM sessions ORDER BY session_id; -- sort: no
SELECT * FROM sessions WHERE session_id LIKE 'abc%'; -- prefix: no

-- Use B-Tree instead if you need ranges or sorting
CREATE INDEX idx_session_btree ON sessions(session_id); -- default B-Tree

Hash indexes are O(1) for equality but useless for ranges, sorting, or prefix matching. Use them only for exact key lookups.

Common confusions

  • Confused with: B-Tree index

    The difference: Hash indexes are O(1) for equality lookups but can't do ranges or sorting. B-Tree indexes are O(log n) but support ranges, sorting, and prefix matching. Hash is faster for = only; B-Tree is more versatile.

Related terms

Related Resources

Related Lessons

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to glossary