How Database Indexes Work: B-Trees, Composite Indexes and Query Plans

A missing index is one of the most common causes of slow applications. A query that takes 2 seconds scanning a million rows can take 2 milliseconds with the right index. Indexes aren't free, though, and the wrong ones waste memory and slow down writes. This guide explains how indexes work so you can design them deliberately.

Examples use PostgreSQL, but the concepts apply to most relational databases.

#Key takeaways

• An index is a separate, sorted data structure that lets the database find rows without scanning the whole table.
• Most indexes are B-trees, which are great for equality, ranges, sorting and prefix matches.
• In composite indexes, column order matters: equality columns first, then range or sort columns.
• Covering indexes can answer queries without touching the table.
• Use EXPLAIN (ANALYZE) to see what the database actually does, and index for real query patterns.
• Every index slows writes and uses storage. Remove unused ones.

#The problem indexes solve

Without an index, finding WHERE email = 'ana@example.com' means a sequential scan: read every row and check it. That's O(n). Fine for 1,000 rows, painful for 50 million.

An index is like a book's index: sorted keys pointing to locations, so the database jumps straight to matching rows.

#How B-tree indexes work

A B-tree is a balanced tree optimized for disk and memory pages:

text                    [ M ]
                 /         \
         [ D  H ]           [ R  W ]
        /   |   \          /   |   \
   [A-C] [E-G] [I-L]   [N-Q] [S-V] [X-Z]   ← leaf pages: sorted keys + row pointers,
                                              linked left-to-right for range scans

• Each node holds many keys (hundreds per page), so the tree is shallow. Even billions of rows need only a few levels.
• Lookups are O(log n): a handful of page reads.
• Leaves are linked, so range queries (BETWEEN, >, ORDER BY) scan sequentially after finding the start.

B-trees support =, <, >, BETWEEN, IN, ORDER BY, and prefix LIKE 'abc%'. They don't help with LIKE '%abc' (leading wildcard) or functions applied to the column, unless you index the expression.

#Creating and using an index

sqlCREATE INDEX idx_orders_customer_id ON orders (customer_id);

SELECT * FROM orders WHERE customer_id = 42;   -- can use the index

For large production tables, create indexes without blocking writes where your database supports it (in PostgreSQL, CREATE INDEX CONCURRENTLY).

#Composite (multi-column) indexes

An index on (customer_id, created_at) is sorted by customer_id, then by created_at within each customer, like a phone book sorted by last name, then first name.

sqlCREATE INDEX idx_orders_customer_created ON orders (customer_id, created_at DESC);

This index efficiently supports:

sqlWHERE customer_id = 42                                   -- ✅ leftmost prefix
WHERE customer_id = 42 AND created_at > '2026-01-01'     -- ✅ equality + range
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20 -- ✅ no sort needed
WHERE created_at > '2026-01-01'                          -- ❌ skips the leading column

Rules of thumb for column order:

1. Columns used with equality first.
2. Then the column used for range filtering or sorting.
3. Consider selectivity, but query patterns matter more.

One well-designed composite index often replaces several single-column indexes.

#Covering indexes (index-only scans)

If an index contains every column a query needs, the database can answer from the index alone, without visiting the table:

sqlCREATE INDEX idx_orders_customer_cover
  ON orders (customer_id, created_at DESC) INCLUDE (status, total);

SELECT created_at, status, total
FROM orders WHERE customer_id = 42
ORDER BY created_at DESC LIMIT 20;   -- index-only scan possible

#Other useful index types

sqlCREATE INDEX idx_users_lower_email ON users (lower(email));
CREATE INDEX idx_jobs_pending ON jobs (created_at) WHERE status = 'pending';

#Reading query plans with EXPLAIN

Never guess. Ask the database:

sqlEXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;

textLimit  (actual time=0.041..0.058 rows=20 loops=1)
  ->  Index Scan using idx_orders_customer_created on orders
        Index Cond: (customer_id = 42)
        Buffers: shared hit=5
Planning Time: 0.12 ms
Execution Time: 0.08 ms

What to look for:

• Seq Scan on a large table for a selective query usually means a missing or unusable index.
• Estimated vs actual rows far apart → stale statistics (run ANALYZE) or skewed data.
• Sort nodes with large inputs → an index matching the ORDER BY could remove them.
• Nested loops over many rows → possibly missing indexes on join columns.

The planner may legitimately choose a sequential scan when a query returns a large fraction of the table. Reading most pages sequentially can be faster than random index lookups.

#Why an index isn't being used

• A function wraps the column: WHERE date(created_at) = .... Use a range condition or an expression index.
• Implicit type casts: comparing a text column to a number.
• Leading wildcard: LIKE '%term'. Use full-text or trigram indexes.
• Low selectivity: WHERE is_active = true when 95% of rows are active.
• The query doesn't use the leading column of a composite index.
• Stale statistics.

#The cost of indexes

• Slower writes: every insert, update or delete must also update each affected index.
• Storage and memory: indexes compete with data for cache space.
• Maintenance: bloat, and occasional reindexing on write-heavy tables.

Audit periodically: find unused indexes via the database's statistics views and drop them; look for duplicate or redundant indexes (an index on (a) is usually redundant if you have (a, b)).

#An indexing workflow

1. Identify slow or frequent queries from query statistics (for example, pg_stat_statements) and slow-query logs.
2. EXPLAIN ANALYZE them.
3. Design indexes for the actual filter, join and sort patterns.
4. Test with production-like data volumes.
5. Deploy without locking (concurrent creation), and verify with EXPLAIN in production.
6. Monitor write latency and index usage over time.

Indexes are the first line of database scaling, well before replicas or sharding (database scaling: replication and sharding).

#FAQ

#Should I index every column in WHERE clauses?

No. Index columns based on actual query patterns, selectivity and how often queries run. Too many indexes slow writes and waste memory. Composite indexes often serve multiple queries.

#Do foreign keys need indexes?

Often, yes. Indexing foreign key columns speeds up joins and prevents slow scans when parent rows are updated or deleted. Some databases index them automatically; PostgreSQL does not.

#How many indexes is too many?

There's no fixed number. The right set depends on read/write ratio and query patterns. Watch for unused indexes and rising write latency, and make sure each index earns its keep.

#What's the difference between clustered and non-clustered indexes?

A clustered index defines the physical order of table data (as in MySQL InnoDB's primary key). Non-clustered (secondary) indexes are separate structures pointing to rows. PostgreSQL tables are heaps, so all its indexes are secondary.