Indexes in depth

Why indexes exist

Without an index, finding rows means reading the whole table (a full scan). An index is a separate, sorted structure that maps column values to row locations, so the database can jump to the right rows. Most relational indexes are B-trees (see the storage engines lesson): shallow, sorted trees that make lookups and range scans fast.

The trade is always the same: faster reads, slower writes, more storage. Every insert, update and delete must also update each affected index.

What a B-tree index is good at

• Equality: WHERE id = 42.
• Ranges: WHERE created_at >= ... AND created_at < ....
• Sorting: ORDER BY created_at can be satisfied by index order, avoiding a sort.
• Prefix matches: LIKE 'abc%' (but not LIKE '%abc').

It does not help when the query hides the column in a function (WHERE LOWER(email) = ...) unless you index that expression, or when the column has so few distinct values that the index barely narrows anything.

Composite indexes and column order

A composite index on (a, b, c) is sorted by a, then b within each a, then c. It can be used for queries that use a leftmost prefix:

Query uses	Can use the index?
a	Yes
a, b	Yes
a, b, c	Yes
b only	Not efficiently
a, c	Partly (uses a)

Ordering rules of thumb:

1. Equality columns first, then the range or sort column last.
2. Among equality columns, put the more selective (narrowing) one first if queries sometimes use only one of them.
3. Design indexes around real queries, not columns in isolation.

100%

Figure SDA-DDV-02-1 · How a composite index narrows a query · © forcsguy.com

Covering and included columns

If an index holds every column a query needs, the database reads only the index (an index-only scan) and skips the table. Some databases let you add non-key columns with INCLUDE, so the index is wide enough to cover a hot query without making the sort key longer.

Clustered versus secondary indexes

• A clustered index defines how the table rows themselves are stored: the table is the B-tree ordered by the key (InnoDB's primary key works this way). Range scans on the key are fast, and there is one per table.
• Secondary indexes are separate structures. In InnoDB a secondary entry stores the primary key, so a lookup is two steps (index, then clustered key). In PostgreSQL, the table is a heap and every index points at row locations.

Consequence: in a clustered design, a random primary key (like a random UUID) scatters inserts across the tree and fragments it; sequential or time-ordered keys insert at the end and stay compact.

Other index types (know they exist)

• Hash: equality only.
• Unique: enforces uniqueness and is also an index.
• Partial/filtered: index only the rows you query (WHERE status = 'PENDING'), small and fast.
• Full-text and inverted: search words in text.
• Spatial (GiST, R-tree): geographic queries.
• GIN / JSON indexes for arrays and JSON fields.

Choosing indexes

1. Start from the slow or frequent queries (see the query optimisation lesson).
2. Index columns used in WHERE, JOIN and ORDER BY; always index foreign keys you join on.
3. Prefer few well-designed composite indexes to many single-column ones.
4. Drop unused indexes (databases can report index usage); they only cost.
5. Check the plan after creating one: databases ignore indexes they judge unhelpful.

Common mistakes

Indexing low-selectivity columns alone (a boolean); wrapping an indexed column in a function; leading wildcard searches; too many indexes on a write-heavy table; and forgetting that a type mismatch (comparing text to a number) can prevent index use.

Real-world reading