Database Indexing: A Deep Dive
Indexes can make or break your application's performance — here's how they work under the hood and when to use each type.
Slow queries are rarely a database problem — they're an indexing problem. A missing index turns a 2ms lookup into a 2-second full table scan. A misplaced index wastes disk space and slows down writes for zero read benefit. Understanding how indexes actually work changes the way you design schemas and write queries.
How B-Tree Indexes Work
The default index type in PostgreSQL, MySQL, and most relational databases is a B-tree. It's a sorted, balanced tree structure that allows O(log n) lookups instead of O(n) sequential scans.
-- Without an index, this scans every row in the table
SELECT * FROM orders WHERE customer_id = 'cust_abc123';
-- Seq Scan on orders: rows=1,000,000, time=1,847ms
-- With an index, it traverses a tree to find matching rows
CREATE INDEX idx_orders_customer_id ON orders (customer_id);
-- Index Scan using idx_orders_customer_id: rows=47, time=0.8msThe index stores customer_id values in sorted order with pointers to the actual table rows. Instead of reading a million rows, the database walks a tree of maybe 3-4 levels deep.
Composite Indexes and Column Order
A composite index covers multiple columns. The column order determines which queries benefit.
-- ❌ Two separate indexes — only one gets used per query
CREATE INDEX idx_status ON orders (status);
CREATE INDEX idx_date ON orders (created_at);
-- This query can only use ONE of these indexes, then filters the rest
SELECT * FROM orders
WHERE status = 'shipped' AND created_at > '2020-01-01';
-- ✅ Composite index — covers the entire WHERE clause
CREATE INDEX idx_orders_status_date ON orders (status, created_at);
-- Now the database uses one index seek for both conditionsThe leftmost prefix rule matters: a composite index on (status, created_at) supports queries filtering on status alone or status + created_at, but not created_at alone. Think of it like a phone book — you can find all Smiths, or Smith + John, but you can't efficiently find all Johns across all last names.
-- ✅ Uses the composite index (leftmost prefix)
SELECT * FROM orders WHERE status = 'pending';
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2020-01-01';
-- ❌ Cannot use the composite index efficiently
SELECT * FROM orders WHERE created_at > '2020-01-01';Covering Indexes
A covering index includes all columns a query needs, eliminating the need to read the actual table row. This is an index-only scan — the fastest possible read path.
-- Query needs customer_id and total
SELECT customer_id, total FROM orders WHERE status = 'completed';
-- Regular index — finds rows via index, then fetches from table (heap)
CREATE INDEX idx_status ON orders (status);
-- Covering index — all needed columns are IN the index
CREATE INDEX idx_status_covering ON orders (status) INCLUDE (customer_id, total);
-- Index Only Scan: no heap fetches neededThe tradeoff: covering indexes are larger and slower to update. Use them for read-heavy queries on columns that rarely change.
Partial Indexes
Why index rows you never query? Partial indexes cover a subset of the table, saving space and write overhead.
-- ❌ Full index — includes millions of completed orders you rarely query
CREATE INDEX idx_orders_status ON orders (status);
-- ✅ Partial index — only indexes the rows you actually filter on
CREATE INDEX idx_orders_active ON orders (status)
WHERE status IN ('pending', 'processing', 'shipped');// Common use case: "active" records in a soft-delete system
// Only 5% of users are active, but 95% of queries filter on active
// The partial index is 20x smaller and 20x faster to maintainWhen Indexes Hurt
Indexes aren't free. Every INSERT, UPDATE, and DELETE must update all relevant indexes. Over-indexing slows writes and wastes storage.
-- ❌ Over-indexed table — every write updates 8 indexes
-- orders table with indexes on:
-- (id), (customer_id), (status), (created_at), (updated_at),
-- (total), (shipping_method), (payment_status)
-- Each INSERT now writes to 9 locations (1 table + 8 indexes)| Scenario | Index recommendation |
|---|---|
| Read-heavy, few writes (analytics) | Index generously |
| Write-heavy, few reads (event log) | Minimal indexes |
| Mixed workload (typical app) | Index only queried columns |
| Wide table, narrow queries | Use covering indexes selectively |
EXPLAIN Is Your Best Friend
Before adding an index, use EXPLAIN ANALYZE to understand the current query plan. After adding it, verify the index is actually used.
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE customer_id = 'cust_abc123'
AND status = 'pending'
ORDER BY created_at DESC
LIMIT 10;
-- Look for:
-- "Seq Scan" → needs an index
-- "Index Scan" → using an index
-- "Index Only Scan" → best case, covering index
-- "Bitmap Index Scan" → multiple indexes combined
-- "actual time" → real execution time, not estimatesDon't trust the query planner's estimates — always use ANALYZE to see actual execution times. And run ANALYZE on the table after adding data so the planner has current statistics.
Key Takeaways
- B-tree indexes turn O(n) scans into O(log n) lookups — one missing index can make a query 1000x slower
- Column order in composite indexes matters — the leftmost prefix rule determines which queries benefit
- Covering indexes eliminate table lookups — include frequently selected columns with
INCLUDE - Partial indexes save space — only index the rows your queries actually filter
- Over-indexing slows writes — every index is maintained on every mutation
- Always validate with EXPLAIN ANALYZE — don't guess, measure
