What is a Database Index?

Without an index, finding a row means checking every row — a full table scan. An index is a separate, ordered data structure that lets the database jump straight to the rows that match, at the cost of extra storage and slower writes to keep it up to date.

The Problem: Linear Search Doesn’t Scale

Imagine a users table with ten million rows and a query like WHERE email = 'a@b.com'. Without an index, the database has no choice but to read every row and check the email column on each one — an O(n) operation that gets slower in direct proportion to table size. Double the rows, double the scan time.

-- Without an index: sequential scan across the full table
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'a@b.com';

-- Seq Scan on users  (cost=0.00..185000.00 rows=1 width=120)
--   Filter: (email = 'a@b.com'::text)
--   Rows Removed by Filter: 9999999

An index turns that into an O(log n) lookup, because the underlying structure is organized so the database can eliminate most of the table with each comparison, the same way you’d find a word in a dictionary by repeatedly halving the range instead of reading every page.

B-Trees: The Default Structure

Most relational databases index with a B-tree (technically a B+tree) by default. It keeps keys sorted and balanced, so every lookup takes roughly the same number of steps regardless of where the value falls, and range queries (WHERE created_at > '2026-01-01') are efficient because the leaves are linked in sorted order.

CREATE INDEX idx_users_email ON users (email);

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'a@b.com';

-- Index Scan using idx_users_email on users
--   (cost=0.42..8.44 rows=1 width=120)
--   Index Cond: (email = 'a@b.com'::text)

The cost estimate dropping from 185,000 to roughly 8 is the entire point: the planner switched from reading the whole table to walking a tree with a handful of levels.

Composite Indexes and Column Order

An index on multiple columns is only useful as a prefix match — an index on (last_name, first_name) speeds up queries filtering on last_name alone or on both columns together, but does nothing for a query filtering on first_name alone. Column order matters and should follow your actual query patterns, most selective or most commonly filtered column first, unless you have a specific range-query reason to do otherwise.

CREATE INDEX idx_orders_customer_status
  ON orders (customer_id, status);

-- Uses the index efficiently
SELECT * FROM orders WHERE customer_id = 42 AND status = 'pending';
SELECT * FROM orders WHERE customer_id = 42;

-- Cannot use this index at all
SELECT * FROM orders WHERE status = 'pending';

Covering Indexes

A covering index includes every column a query needs, so the database can answer entirely from the index without touching the underlying table row at all — this is usually called an “index-only scan.”

CREATE INDEX idx_orders_covering
  ON orders (customer_id, status) INCLUDE (total_amount);

SELECT status, total_amount
FROM orders
WHERE customer_id = 42;
-- Index Only Scan, no heap fetch needed

Index Types at a Glance

The Cost: Every Write Pays For It

Indexes aren’t free. Every INSERT, UPDATE, or DELETE has to update every index on the affected columns, not just write the row. A table with six indexes pays that cost six times on every write, plus the storage each index consumes on disk.

Reading an Execution Plan

The fastest way to know whether an index is actually being used is to ask the query planner, not to guess. EXPLAIN ANALYZE shows the real plan and real timings, and the two signals worth scanning for first are Seq Scan (probably missing an index) versus Index Scan or Index Only Scan (index is doing its job), and the estimated row count versus actual rows, which flags stale statistics when they diverge wildly.

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders
WHERE customer_id = 42 AND status = 'pending'
ORDER BY created_at DESC
LIMIT 20;

Run this before and after adding an index, on production-scale data if at all possible — indexes that look great on a thousand-row dev database don’t always tell you what happens at ten million rows.

Takeaway

An index trades write cost and storage for read speed by maintaining a sorted, searchable structure alongside the table — usually a B-tree, letting lookups go from O(n) to O(log n). Match column order in composite indexes to your actual query filters, consider covering indexes for hot, narrow read paths, and audit for unused indexes periodically, since every index you don’t need is pure overhead on every write.