From Slow Search to Fast Search Using Indexes

Understanding how indexes improve database performance and why B-Tree indexes are the default in relational databases.

The Problem

Take this example:

The database contains millions of rows. Searching for “Ana” takes a long time.

Current Implementation

The database checks every single row until it finds Ana.

This is called a full table scan.

It’s like reading an entire book just to find one word.

From Slow Search to Fast Search

There’s a better way: use an index.

An index works like the index of a book — it allows you to jump directly to the correct page instead of scanning everything.

Create an Index

CREATE INDEX idx_email ON users(email);

Now, when we search for Ana, the database jumps directly to her row instead of scanning the entire table.

Search Query

SELECT * FROM users
WHERE email = 'ana@email.com';

The Power of Indexes

• Fast searches
• Real-time dashboards
• Scalable applications

Your query isn’t broken — it just needs an index.

Hash Table vs B-Tree for Database Search

Your Case: Searching by Email

SELECT * FROM users
WHERE email = 'ana@email.com';

This is an equality lookup.

What Databases Actually Use

Almost all relational databases use B-Tree indexes by default:

• PostgreSQL
• MySQL
• SQLite
• Microsoft SQL Server

When you run:

CREATE INDEX idx_email ON users(email);

You are almost certainly creating a B-Tree index, not a hash index.

Why B-Tree Instead of Hash?

• Supports equality search (=)
• Supports range queries (>, <, BETWEEN)
• Supports sorting (ORDER BY)
• Efficient disk storage

Hash indexes only work for exact equality, cannot handle ranges or sorting, and are less flexible.

When Are Hash Indexes Useful?

• Only equality lookups
• No need for ordering
• Extremely fast key-based access

Examples:

• Redis (in-memory hash tables)
• PostgreSQL hash indexes (optional, not default)

What Happens Internally

With an index, instead of scanning 10 million rows, the database performs:

• Log₂(10,000,000) ≈ 23 steps

This is why indexed searches feel instant.

Large-Scale Systems

• Relational DB → B-Tree index
• Caching layer → Hash table (Redis)
• Search engine → Inverted index (Elasticsearch)

Practical Advice

• Use a normal index: CREATE INDEX idx_email ON users(email);
• Don’t manually implement a hash table
• Don’t over-engineer

Your database already handles this efficiently.