An index is a separate, sorted data structure that lets the database find rows without scanning the whole table. It is the single highest-leverage performance fix for most applications, and the most misunderstood: an index is not free, it slows every write, and the wrong index does nothing. This explains how they work and how to choose them, for MySQL and PostgreSQL alike.

How a B-tree index works

Think of the index at the back of a book: terms sorted alphabetically, each pointing to a page. To find a term you do not read the book, you jump to roughly the right place and narrow down. A database B-tree index is the same: the indexed values kept sorted in a balanced tree, so a lookup is a handful of steps (O(log n)) instead of reading every row (O(n)). The trade is that the tree lives on disk and must be updated on every insert, update or delete of an indexed column.

What to index

Index the columns the database has to search or sort on: the ones in your WHERE clauses, your JOIN conditions, and your ORDER BY. A foreign key you join on almost always needs an index (some databases do not create it automatically). A column you only ever select, never filter or sort by, does not.

Composite indexes: column order matters

An index on (status, created_at) is sorted by status first, then by created_at within each status. It serves a query that filters on status, or on status and created_at, or that filters on status and sorts by created_at. It does not help a query that only filters on created_at, because the values are not in date order overall. This is the leftmost-prefix rule: an index on (a, b, c) helps queries on a, on a and b, or on a, b and c, but not on b alone.

-- Serves: WHERE status = ? ORDER BY created_at
-- Serves: WHERE status = ? AND created_at > ?
-- Does NOT serve: WHERE created_at > ?  (status not constrained)
CREATE INDEX orders_status_created ON orders (status, created_at);

Covering indexes

If an index contains every column a query needs, the database answers from the index alone and never touches the table rows. An index on (customer_id, total) covers SELECT total FROM orders WHERE customer_id = ?. Adding a column to an index to make it covering is a common, cheap win for a hot query.

Selectivity: not every column is worth indexing

An index helps in proportion to how many rows it rules out. A column with two values (a boolean, a status with 90 percent in one state) barely narrows anything, so the database often ignores the index and scans anyway. High-cardinality columns (an email, a user ID, a timestamp) are where indexes pay off.

When an index hurts

Every index is a copy of some columns that must be kept in sync. Each insert updates every index on the table; each update of an indexed column moves an entry in the tree. A table with a dozen indexes has slow writes. Index for the queries you actually run, drop indexes nothing uses, and do not add one speculatively.

Reading the query plan

Run EXPLAIN on a slow query. You are looking for an index scan or index seek rather than a sequential or full table scan, and for the row estimate to be small. If the plan shows a full scan on a big table where you expected an index, the index is missing, unusable for that query (wrong column order), or the column is not selective enough.

Special kinds

• ✓Unique index: enforces uniqueness and serves lookups; a primary key is one.
• ✓Partial index (PostgreSQL): indexes only rows matching a condition, e.g. WHERE deleted_at IS NULL, keeping it small.
• ✓Functional / expression index: indexes the result of an expression, e.g. LOWER(email), so a case-insensitive lookup uses it.
• ✓GIN / GiST (PostgreSQL): for JSONB containment, full-text search and trigram matching, not plain equality.

Query pattern, index to add

An index is a sorted shortcut: it makes reads fast and writes a little slower, and only for the queries whose columns it matches. Index the columns you filter, join and sort on, get the composite order right, check the plan with EXPLAIN, and remove the indexes nothing uses.