Database Indexing Explained: How Indexes Speed Up Queries

Database indexes are like book indexes — they help the database find rows without scanning the entire table. Without them, even simple queries can take seconds on large tables.

Understanding how indexes work — and more importantly, when they don’t work — is one of the most valuable performance-tuning skills a developer can learn. A well-designed indexing strategy can reduce query times from minutes to milliseconds without changing a single line of application code. Conversely, the wrong indexes, or too many of them, can cripple write performance and waste gigabytes of disk space. This guide covers the fundamentals you need to make informed indexing decisions.

Without an Index (Sequential Scan)

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

Without an index, PostgreSQL reads every row in the users table to find the matching email. For a table with 1 million rows, that’s 1 million comparisons. This is called a sequential scan or full table scan. As your table grows, performance degrades linearly — double the rows, double the scan time.

On a modern SSD, scanning 1 million rows might take 300-500ms. For 100 million rows, that becomes 30-50 seconds. An index reduces this to sub-millisecond lookups regardless of table size.

With an Index (Index Scan)

CREATE INDEX idx_users_email ON users (email);

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

With an index, the database uses a B-tree data structure to find the row in milliseconds:

• Level 1: Check if ‘alice@example.com’ is in the top, middle, or bottom third
• Level 2: Narrow to one-ninth
• Continue until found

A B-tree index on 1 million rows finds any value in about 20 comparisons (compared to 1 million without). This logarithmic scaling means indexes become more valuable as tables grow.

How B-Trees Work Under the Hood

A B-tree stores sorted key-value pairs in a balanced tree structure. Each node contains multiple keys (usually hundreds), making the tree very shallow. For 1 million rows, a typical B-tree is only 3-4 levels deep. The database traverses from the root to a leaf node, following pointers based on comparisons at each level.

The root and upper-level branches are often cached in memory, making lookups extremely fast even on mechanical hard drives. Only the leaf nodes need disk I/O, and even those are typically cached after the first access.

It is important to understand that indexes are separate data structures stored alongside the table. Every INSERT, UPDATE, or DELETE on the table must also update every relevant index. This means indexes consume not only disk space but also CPU and I/O during writes. The trade-off is almost always worth it for read-heavy workloads, but write-heavy tables need careful index budgeting. A table with ten indexes can easily see writes become three to four times slower than the same table with no indexes.

Index Types

When to Choose Each Index Type

B-tree is the default for a reason — it handles 95% of use cases including sorting and range queries. Hash indexes are narrower but can be faster for pure equality lookups in PostgreSQL. GIN (Generalized Inverted Index) excels when you need to search inside composite types like JSONB documents or arrays. GiST is the go-to for geospatial queries with PostGIS. BRIN (Block Range INdex) is specialized for enormous tables where data is naturally ordered — think IoT sensor readings sorted by timestamp — because it only stores summaries of data blocks rather than every single value.

When choosing an index type, consider not just the query pattern but also the data distribution. A B-tree on a UUID column with random inserts will suffer from page splits as new values are inserted throughout the tree, causing fragmentation and write amplification. A BRIN index on an always-increasing column like created_at is tiny and requires minimal maintenance because it only stores min/max values per block range. Understanding these nuances helps you pick the right tool for each workload.

Creating Indexes

-- Single column
CREATE INDEX idx_users_email ON users (email);

-- Unique index (also enforces uniqueness)
CREATE UNIQUE INDEX idx_users_email ON users (email);

-- Multi-column
CREATE INDEX idx_users_name ON users (last_name, first_name);

-- Partial index
CREATE INDEX idx_active_users ON users (email) WHERE active = true;

-- Index on expression
CREATE INDEX idx_users_lower_email ON users (LOWER(email));

Real-World Example: Partial Indexes

Partial indexes are underused but incredibly powerful. Imagine an orders table where 95% of rows are status = 'completed' and only 5% are status = 'pending'. A full index on status is wasteful. Instead:

CREATE INDEX idx_pending_orders ON orders (created_at) WHERE status = 'pending';

This index is tiny, covers exactly the queries that matter (finding pending orders), and saves 95% of the index size.

When to Index

Good candidates for indexing:

-- Columns used in WHERE clauses
SELECT * FROM orders WHERE user_id = 123;

-- Columns used in JOIN conditions
SELECT * FROM orders o JOIN users u ON o.user_id = u.id;

-- Columns used in ORDER BY
SELECT * FROM users ORDER BY created_at DESC;

-- Columns used in frequent UPDATE/DELETE WHERE clauses
DELETE FROM sessions WHERE expires_at < NOW();

The 5% Rule

A practical heuristic: if a query filters to 5% or less of the table, an index almost certainly helps. If it filters to more than 20% of the table, a sequential scan may be faster because the random I/O from index lookups adds overhead. PostgreSQL’s query planner makes this decision automatically based on table statistics.

When NOT to Index

• Small tables (< 1000 rows) — a sequential scan is faster
• Low cardinality columns — gender, status (few distinct values)
• Columns rarely used in WHERE — the index won’t help
• Heavy write workloads — indexes slow down INSERT/UPDATE/DELETE

Each index adds roughly 20-30% overhead to INSERT performance. If you have 10 indexes on a table, inserts can be 3-4x slower than with no indexes. Always benchmark write-heavy tables.

Multi-Column Indexes

CREATE INDEX idx_users_name ON users (last_name, first_name);

This index helps queries that filter by:

• WHERE last_name = 'Smith' — ✓ uses the index
• WHERE last_name = 'Smith' AND first_name = 'John' — ✓ uses the index
• WHERE first_name = 'John' — ✗ does NOT use the index (skipped the first column)

Order matters. Put the most selective column first. If last_name has 10,000 distinct values and first_name has 500, the index tree is more efficient with last_name first because each level eliminates more rows.

The leftmost prefix rule is critical to understand: a multi-column index on (A, B, C) can satisfy queries on A, on (A, B), and on (A, B, C), but not on B alone or (B, C) alone. This means you should order columns by how frequently they appear in WHERE conditions, not just by selectivity. If 90% of your queries filter on status and only 10% filter on status plus created_at, put status first even if created_at is more selective — otherwise the index is useless for most of your queries.

Covering Indexes

A covering index includes all columns needed by a query, allowing PostgreSQL to answer the query entirely from the index without touching the table:

CREATE INDEX idx_covering ON users (email) INCLUDE (name, created_at);

-- Now this query uses ONLY the index:
SELECT email, name, created_at FROM users WHERE email = 'alice@example.com';

This is called an Index-Only Scan and is the fastest way to read data. The INCLUDE columns don’t affect the tree structure — they’re stored only at the leaf level.

EXPLAIN ANALYZE

Check if your index is being used:

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com';

Output shows whether it’s an Index Scan, Bitmap Heap Scan, or Seq Scan:

Index Scan using idx_users_email on users  (cost=0.42..8.44 rows=1 width=42)
  Index Cond: ((email)::text = 'alice@example.com'::text)

Understanding EXPLAIN ANALYZE Output

• cost=0.42..8.44 — The first number is startup cost, the second is total cost. Lower is better.
• rows=1 — Estimated number of rows returned. If this is far off, your table statistics are stale.
• width=42 — Average row width in bytes.
• Index Scan — Reading directly from the index, then fetching rows from the table.
• Bitmap Heap Scan — Reads index entries into a bitmap, then sorts them before reading the heap. Faster when many rows match.
• Seq Scan — Sequential (full table) scan. Usually means no usable index exists or the planner chose not to use one.

Run ANALYZE after bulk inserts to keep statistics current.

Index Maintenance

-- Rebuild an index
REINDEX INDEX idx_users_email;

-- List all indexes for a table
SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'users';

-- Remove unused index
DROP INDEX IF EXISTS idx_unused;

Detecting Unused Indexes

PostgreSQL tracks index usage statistics. Find indexes that are never used:

SELECT
  schemaname, tablename, indexname,
  idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;

Any index with idx_scan = 0 since the last statistics reset is a candidate for removal. Dropping unused indexes speeds up writes and frees disk space.

The Trade-off

Index benefit:  Fast reads  (1000x faster for large tables)
Index cost:     Slow writes + disk space

              No Index    With Index
SELECT *        1 ms         1 ms  (small table)
SELECT *      1000 ms        2 ms  (large table)
INSERT           1 ms        2 ms
UPDATE           2 ms        5 ms
Disk space       100 MB     110 MB

The trade-off table demonstrates that indexes are not free. Each index on a table adds overhead to every write operation. On a typical OLTP workload with 80% reads and 20% writes, a few well-chosen indexes are essential. On an OLAP workload with bulk loads followed by complex analytical queries, you might drop indexes before the load and recreate them afterward. The key takeaway is to index based on actual query patterns, not theoretical possibilities. Use `pg_stat_user_indexes` to find unused indexes and `EXPLAIN ANALYZE` to verify your indexes are actually being used.



## FAQ

**What is the difference between SQL and NoSQL?** SQL databases use structured schemas with tables, relationships, and ACID transactions. NoSQL databases offer flexible schemas, horizontal scaling, and various data models (document, key-value, graph, column-family). Choose based on data structure and access patterns.

**When should I use an index?** Index queries filtering on the indexed column(s), particularly for WHERE clauses, JOINs, and ORDER BY. Avoid over-indexing — each index slows writes and consumes storage. Monitor slow queries to identify indexing opportunities.

**What is database normalization?** Normalization organizes data to reduce redundancy and improve integrity. First Normal Form (1NF) eliminates duplicate columns. Second Normal Form (2NF) removes partial dependencies. Third Normal Form (3NF) removes transitive dependencies.

**How do I choose between PostgreSQL and MySQL?** PostgreSQL offers more advanced features (JSONB, full-text search, custom types, better concurrency). MySQL is simpler to configure and widely available. Both are excellent choices; PostgreSQL is often preferred for complex applications.

**What is a deadlock in databases?** A deadlock occurs when two transactions each hold locks the other needs. The database detects deadlocks and kills one transaction automatically. Reduce deadlocks by accessing tables in the same order across transactions and keeping transactions short.

---

**Related:** Learn [SQL JOINs](/programming/database/sql-joins-explained/) and [normalization](/programming/database/database-normalization/).