You add an index to the users table on email, and the lookup that used to take two seconds now runs in under a millisecond. You feel good. Then you add an index on every column "just in case," and inserts start slowing down. You remove an index from a production table, the query plan changes, and a report that ran fine for months now takes forty seconds.
Indexes are one of the most impactful and most misunderstood tools in database engineering. Teams often treat them as a free performance upgrade. Add one when things feel slow, add more for safety. The actual tradeoff is more specific: indexes make certain reads faster at the cost of every write touching that table and extra storage on disk. Knowing exactly when that tradeoff is worth it requires understanding what an index actually does.
TLDR
- An index is a separate sorted structure with pointers back to the real rows, so the database can find matches without scanning the whole table.
- The default B-tree supports equality, range, and prefix queries in logarithmic time.
- Every index speeds up specific reads but slows writes and costs storage, and the query planner decides whether to use it at all.
What problem an index solves#
Without an index, a database must read every row in a table to find the ones that match a query's filter condition. For a table with ten million rows, finding the one user with email = 'alice@example.com' means the database must scan all ten million rows before returning a result. This is called a sequential scan (or full table scan), and it is O(n) in time.
An index stores a precomputed, sorted version of the column values along with pointers (row addresses, called heap pointers in PostgreSQL) back to the actual table rows. Finding a value in a sorted structure takes logarithmic time, not linear time. For ten million rows, that is roughly 23 comparisons instead of ten million comparisons.
The physical intuition is the same as a book index. Instead of reading every page to find "B-tree," you scan the alphabetical index at the back, find the page numbers in a few seconds, and jump directly to those pages. The database does the same thing.
Mental model: the lookup chain#
Every database index has two parts: the lookup structure and the heap pointer.
The lookup structure maps column values to physical locations. The heap pointer is the address of the row in the actual table. When the database uses an index to answer a query, it:
- Searches the index structure for the matching values.
- Reads the heap pointers for those matches.
- Fetches the actual table rows from those addresses.
For a query that retrieves only indexed column values, some databases can avoid step 3 entirely using a covering index (or index-only scan). This matters because disk I/O is the most expensive part of a lookup, and skipping the heap fetch removes one of the two disk accesses.
| Without index | With index |
|---|---|
| Read all N rows | Search sorted index: O(log N) |
| Filter in memory | Follow heap pointers to matching rows |
| Return matches | Return matches |
| O(N) time | O(log N) time |
How a B-tree index works step by step#
The B-tree (Balanced Tree) is the default index type in PostgreSQL and most relational databases. The PostgreSQL documentation describes it as a multi-level tree structure where each level can be used as a doubly-linked list of pages.
A B-tree has three node types: the root, internal nodes, and leaf nodes. Leaf nodes contain the actual indexed values paired with heap pointers. Internal nodes contain separator keys that guide navigation. All leaf nodes are at the same depth, which guarantees that every lookup takes the same number of steps regardless of which value is searched.
Root lookup
The database starts at the root node and compares the query value against the separator keys stored there. Each separator points to a child subtree covering a range of values.
Internal traversal
The database follows the pointer to the correct child subtree and repeats the comparison. It descends one level per comparison until it reaches a leaf.
Leaf scan
At the leaf level, the database finds the exact value (or the first value in a range) and reads the associated heap pointers.
Heap fetch
The database uses the heap pointers to read the actual table rows from disk. For a range query, it scans the leaf-level linked list sideways to collect all matching entries without re-traversing the tree.
This structure gives B-trees their key properties: logarithmic lookup time, efficient range scans (because leaves are linked), and support for equality (=), range (<, >, BETWEEN), and pattern prefix (LIKE 'foo%') queries. As the PostgreSQL index types documentation notes, B-tree is the default when no USING clause is specified because it covers the broadest set of query shapes.
-- Create a B-tree index (default)
CREATE INDEX idx_users_email ON users (email);
-- This query can now use the index
SELECT * FROM users WHERE email = 'alice@example.com';
-- Range queries also benefit
SELECT * FROM users WHERE created_at BETWEEN '2025-01-01' AND '2025-06-01';
-- Pattern prefix works
SELECT * FROM users WHERE username LIKE 'alice%';
-- But trailing wildcards do NOT use the index
-- SELECT * FROM users WHERE username LIKE '%alice'; -- full scan
Index types beyond B-tree#
PostgreSQL supports seven index types, each suited to a different access pattern. Understanding the others clarifies when B-tree is not the right choice.
| Index type | Best for | Operators |
|---|---|---|
| B-tree | Equality, ranges, sorting | =, <, >, BETWEEN, IN, LIKE 'x%' |
| Hash | Equality only, faster than B-tree for = | = only |
| GiST | Geometric, nearest-neighbor, fuzzy | &&, @>, <-> |
| GIN | Arrays, full-text search, JSONB | @>, @@, ? |
| BRIN | Time-series, physically sorted large tables | <, >, = on correlated data |
| SP-GiST | Non-balanced structures (k-d trees, tries) | Geometric, IP ranges |
For vector embeddings, PostgreSQL's pgvector extension adds its own HNSW and IVFFlat index types on top of this set. They are covered in detail in how vector search works.
A Hash index stores 32-bit hash codes and supports only equality comparisons. It is faster than a B-tree for pure equality lookups but cannot support range queries or sorting. BRIN (Block Range Index) is extremely space-efficient for very large tables where values are correlated with their physical insertion order. Timestamps on an append-only events table are a classic case. GIN is the right choice for indexing JSONB documents or full-text search tsvector columns.
The query planner decides whether to use an index#
Creating an index does not guarantee it will be used. The query planner (the part of the database that transforms SQL into an execution plan) decides whether an index scan is cheaper than a sequential scan by estimating costs.
The PostgreSQL EXPLAIN documentation describes the planner's output as one line per node in the plan tree, showing the basic node type plus the cost estimates the planner made. The cost number is not in seconds; it is an abstract unit proportional to disk page reads and CPU work.
EXPLAIN SELECT * FROM orders WHERE customer_id = 42;
-- Possible output with index:
-- Index Scan using idx_orders_customer_id on orders
-- (cost=0.43..8.45 rows=12 width=96)
-- Index Cond: (customer_id = 42)
-- Possible output without index (or for a large return fraction):
-- Seq Scan on orders
-- (cost=0.00..4821.00 rows=1000000 width=96)
-- Filter: (customer_id = 42)
The planner prefers a sequential scan when it estimates that a large fraction of the table will be returned, because sequential reads are physically faster per page than the random I/O of following heap pointers across a large result set. As the PostgreSQL docs note, random_page_cost defaults to 4.0, meaning the planner assumes a random disk read is four times more expensive than a sequential one. On SSDs, this ratio is much lower, and reducing random_page_cost in the server configuration often helps the planner prefer index scans.
The planner uses table statistics (maintained by ANALYZE) to estimate how many rows a filter will return. Stale statistics (from a table that changed significantly since the last ANALYZE) cause the planner to make bad estimates, which can lead to index scans being chosen when a sequential scan would be faster, or vice versa.
Use EXPLAIN ANALYZE, not just EXPLAIN
EXPLAIN shows estimates. EXPLAIN ANALYZE actually executes the query and shows real row counts and timing. When the estimated rows differ wildly from actual rows, stale statistics are usually the cause. Run ANALYZE table_name; and check again.
Write overhead: why more indexes is not always better#
Every index is a separate data structure that must be updated whenever a row is inserted, updated, or deleted. A table with ten indexes pays ten write penalties for every change.
For an INSERT, the database must add the new row to the table heap and add an entry to each index for the indexed column values. For an UPDATE, if an indexed column changes, the old index entry must be removed and a new one added. For a DELETE, the old index entry must be marked as dead (in PostgreSQL, it is cleaned up lazily by vacuum).
This overhead accumulates. A table with many indexes on a high-write workload (an event log, a metrics table, or a message queue) can spend more time maintaining indexes than storing data. The write path becomes dominated by index maintenance rather than the business logic.
| Operation | Heap work | Index work (per index) |
|---|---|---|
| INSERT | Write row to heap page | Add entry to index |
| UPDATE (indexed column) | Write new row version | Remove old entry, add new entry |
| UPDATE (non-indexed column) | Write new row version | No work |
| DELETE | Mark row as dead | Mark index entry as dead |
Where indexing goes wrong#
Over-indexing. Adding an index to every column is the most common mistake. An index is only useful if it is selective, meaning it narrows the result set significantly. An index on a status column with only three possible values (active, inactive, pending) gives the planner little to work with for most queries, because it must still fetch a large fraction of rows.
Index on low-cardinality columns. For a column with few distinct values and no filtering combination that produces a small result set, the planner will typically prefer a sequential scan. The index adds write overhead and storage cost with no read benefit.
Missing composite index order. A composite index on (a, b) supports queries filtering on a alone, or on both a and b. It does not efficiently support queries filtering on b alone. Column order in composite indexes must match the query's filter patterns.
Unused indexes from old features. Indexes accumulate as features evolve. PostgreSQL tracks index usage in pg_stat_user_indexes. Indexes with zero or near-zero scans over a long window are candidates for removal.
Index bloat. On tables with heavy updates or deletes, dead index entries accumulate faster than autovacuum removes them. This inflates index size and slows both reads (more pages to traverse) and writes (more fragmentation). Monitoring index bloat and tuning autovacuum are routine DBA tasks on active tables.
How to debug a slow query#
Start with EXPLAIN ANALYZE. Look for:
- Seq Scan on a large table with a low row estimate: the planner thinks the filter is selective but is doing a full scan. Run
ANALYZEto refresh statistics, then check again. - Index Scan with high actual rows: the query returns more rows than expected. Consider whether the index is truly selective for this use case.
- Nested Loop with large outer relation: often indicates a missing index on the inner table's join key.
- High
actual timeon a Bitmap Heap Scan: the index is used, but heap fetching is slow. Consider a covering index to avoid the heap fetch.
-- Check which indexes exist on a table
SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'orders';
-- Check index usage statistics
SELECT schemaname, tablename, indexname, idx_scan, idx_tup_read, idx_tup_fetch
FROM pg_stat_user_indexes
WHERE tablename = 'orders'
ORDER BY idx_scan ASC;
-- Force or prevent index use for testing
SET enable_indexscan = off; -- Force seq scan
SET enable_seqscan = off; -- Force index scan
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
RESET enable_seqscan;
Practical Examples#
The selective filter#
A payments table with 50 million rows. A query fetches all payments for one customer. That customer has 12 payments. An index on customer_id reduces the work from 50 million row reads to 12 heap fetches, a clear win. The index is highly selective.
The reporting query#
A finance report needs all payments in the last 30 days. If 5 million of the 50 million rows are recent, the planner may choose a sequential scan over an index on created_at. Reading 50 million rows sequentially can be faster than following 5 million random heap pointers across the disk. This is the case where removing an index or changing the query can help.
The composite index for a common filter#
Queries on orders almost always filter by both user_id and status = 'pending'. A composite index (user_id, status) serves this pattern efficiently. An index on user_id alone works for the same queries, but a composite index allows an index-only scan when only those two columns are needed in the output, removing the heap fetch entirely.
-- Composite index covering the query pattern
CREATE INDEX idx_orders_user_status ON orders (user_id, status);
-- This query can use an index-only scan
SELECT order_id, created_at FROM orders
WHERE user_id = 101 AND status = 'pending';
-- (Assumes order_id and created_at are not in the index — heap fetch still needed)
-- Add them to the index for full coverage
CREATE INDEX idx_orders_user_status_cover
ON orders (user_id, status)
INCLUDE (order_id, created_at);
Key Takeaways#
A database index is a read-optimization data structure with explicit write and storage costs. B-trees, the default, support equality, range, and prefix queries in logarithmic time by maintaining a balanced sorted tree with linked leaf pages.
The query planner decides whether to use an index based on estimated cost. It uses table statistics from ANALYZE to estimate selectivity. When statistics are stale or random_page_cost is misconfigured for your hardware, the planner makes bad decisions. EXPLAIN ANALYZE is the tool for debugging those decisions.
Add indexes for specific, frequent, high-selectivity query patterns. Remove unused indexes using pg_stat_user_indexes. Composite indexes must be ordered to match query filter patterns. On write-heavy tables, fewer targeted indexes usually outperform many broad ones.
FAQ#
Why does the database sometimes ignore my index?
The query planner's cost estimate suggests a sequential scan is cheaper. This happens when the filter has low selectivity (matches a large fraction of rows), when statistics are stale (run ANALYZE), or when random_page_cost is set too high for your storage hardware. Use EXPLAIN ANALYZE to see which path was chosen and why.
What is a covering index?
A covering index includes all columns needed to answer a query without accessing the main table heap. PostgreSQL supports this with the INCLUDE clause: CREATE INDEX ON orders (user_id) INCLUDE (status, created_at). When the query only needs columns that appear in the index, the database skips the heap fetch entirely, which can significantly reduce I/O for large result sets.
How does an index affect INSERT and UPDATE performance?
Every index on a table adds one write operation to each INSERT. For UPDATE, only indexes on columns that changed require work. For DELETE, index entries must be marked dead and later cleaned by vacuum. On tables with hundreds of thousands of inserts per second, the number of indexes is a direct multiplier on write latency. Profile with and without indexes using EXPLAIN ANALYZE and real load to measure the actual tradeoff.
When should I use a partial index?
A partial index covers only rows that satisfy a filter condition. For example, CREATE INDEX ON orders (user_id) WHERE status = 'pending' is a small index that only covers pending orders. This is useful when a large table has a minority subset that gets disproportionately queried. Partial indexes are smaller, faster to build, and have lower write overhead than full-table indexes.
How often should I run ANALYZE?
PostgreSQL's autovacuum daemon runs ANALYZE automatically based on the number of row changes since the last analysis, controlled by autovacuum_analyze_threshold and autovacuum_analyze_scale_factor. For tables that change rapidly or have query plans that change after bulk loads, manually running ANALYZE table_name; immediately after the load ensures the planner has fresh statistics for the next queries.
