Course contentsShow
← Computer Science
Lesson 445 of 2,87210. Hash TablesFree lesson

Database Indexing with Hash Tables

Hash-based indexes for fast equality lookups in databases, contrasting with tree-based indexes for range queries.

Database Indexing with Hash Tables

You'll learn how databases use hash tables to enable lightning-fast equality searches on indexed columns.

The Core Idea

When you query a database with something like SELECT * FROM users WHERE email = 'user@example.com', the database could scan every single row—slow! Instead, databases build indexes: data structures that speed up lookups. Hash tables are one powerful indexing option.

A hash-based index works just like the hash tables you've studied: the database hashes the indexed column's value (like an email address) and uses that hash to quickly locate the corresponding row(s). This provides O(1) average-case lookup for exact-match queries.

When Hash Indexes Shine

Hash indexes excel at equality comparisons:

  • WHERE id = 42
  • WHERE username = 'alice'
  • WHERE email = 'user@example.com'

They're perfect for dictionary-like lookups where you know the exact value you're searching for.

The Limitation: No Range Queries

Here's the critical tradeoff: hash functions scatter values unpredictably. Even though "alice" and "alex" are alphabetically close, their hash values could be miles apart in the table. This means hash indexes cannot efficiently handle:

  • Range queries: WHERE age BETWEEN 20 AND 30
  • Sorting: ORDER BY name
  • Prefix matching: WHERE name LIKE 'A%'

For these operations, databases use tree-based indexes (like B-trees) that maintain sorted order.

Choosing Your Index Type

Think of it as choosing the right tool:

  • Hash index = phone book organized by hashed names (fast exact lookup, can't browse alphabetically)
  • Tree index = traditional phone book (slower exact lookup, but supports ranges and sorting)

Key Takeaway: Hash-based database indexes provide O(1) equality lookups but cannot support range queries or ordering—that's where tree-based indexes are essential.