Database Indexing : Understand in 3 Minutes

Problem Statement

Database indexing is a performance optimization technique that creates a shortcut for finding data in a database table, much like a book's index helps you locate information without reading every page. You encounter this problem whenever a query is frustratingly slow—like searching for a user by email in a million-row table, filtering orders by date, or joining large datasets. This slowness happens because, without an index, the database must perform a full table scan, checking every single row, which takes far too long as your data grows.

Core Explanation

At its core, a database index is a separate, ordered data structure that holds a subset of your table's columns and a pointer back to the full row. It allows the database to find rows with a specific value incredibly fast, using efficient search algorithms.

Think of it like the index in a textbook:

• Without the index, you must flip through every page to find mentions of "binary trees."
• With the index, you look up "binary trees" and go directly to pages 127, 254, and 311.

Here’s how it works technically:

• You create an index on one or more columns (e.g., email or last_name, first_name).
• The database builds a sorted structure (commonly a B-tree) from the column values.
• This structure enables efficient lookups. To find '[e-mail]', the database navigates the tree instead of scanning.
• Each entry in the index contains the indexed value and a pointer (like a row ID or primary key) to the complete record in the main table.

The key is the sorted data structure. Finding data in a sorted list is exponentially faster for the database engine than checking an unsorted heap of data.

Practical Context

You should consider adding an index when you have queries that are too slow, especially those with WHERE, ORDER BY, or JOIN clauses on specific columns. The most common real-world use cases are speeding up searches on foreign keys (e.g., user_id), unique fields (e.g., username), and frequently filtered columns (e.g., status, created_at).

However, indexes are not free. You should not blindly index every column because:

• Write Overhead: Every INSERT, UPDATE, or DELETE on the table must also update the index, slowing down write operations.
• Storage Cost: Indexes consume additional disk space.
• Maintenance: Too many indexes can make the query planner's job harder, sometimes leading to poor performance.

You should care because proper indexing is the single most impactful way to fix slow queries without changing your application code, directly affecting user experience and infrastructure costs.

Quick Example

Imagine an employees table with 100,000 rows. You often run this query to find employees by last name:

SELECT * FROM employees WHERE last_name = 'Smith';

Without an index, the database checks all 100,000 rows—a full table scan.

With an index on the last_name column:

CREATE INDEX idx_employees_last_name ON employees(last_name);

The database uses the sorted idx_employees_last_name index to find all 'Smith' entries in a handful of steps, then uses the pointers to retrieve only those specific rows. The performance difference can change a query from taking seconds to milliseconds.

Key Takeaway

Create indexes based on your slow queries, not guesses. Use your database's query execution plan tool to identify which scans would benefit from an index. For a deeper dive, the Use The Index, Luke! guide is an excellent free resource.