An index is a separate, sorted structure that lets the database find rows without scanning the whole table — like the index at the back of a book. It speeds reads and slows writes.

B-tree: the default index

A B-tree (B+tree) keeps keys sorted in a shallow, balanced tree: a lookup touches ~3–4 pages even for millions of rows (O(log n)), and because keys are sorted it also serves ranges, prefixes and ORDER BY.

Query shape	Can a B-tree on `col` help?
`col = 5`, `col IN (…)`	Yes — seek
`col > 5`, `BETWEEN`, `LIKE 'abc%'`	Yes — range scan
`ORDER BY col`, `MIN/MAX(col)`	Yes — already sorted
`LIKE '%abc'`, `lower(col) = …`, `col + 1 = 6`	No — needs a full scan (or an expression index)

Reading a query plan

EXPLAIN QUERY PLAN (SQLite) shows how a query will run; read the detail column. SCAN = read every row; SEARCH … USING INDEX = jump straight to matching rows.

SQL

EXPLAIN QUERY PLAN
SELECT * FROM events WHERE user_id = 42;

Output

id | parent | notused | detail
---+--------+---------+------------
2  | 0      | 216     | SCAN events

SQL

CREATE INDEX idx_events_user ON events (user_id);

EXPLAIN QUERY PLAN
SELECT * FROM events WHERE user_id = 42;

Output

id | parent | notused | detail
---+--------+---------+------------------------------------------------------
3  | 0      | 61      | SEARCH events USING INDEX idx_events_user (user_id=?)

Engine	Show the plan	Run and measure
SQLite	`EXPLAIN QUERY PLAN …`	`.timer on` in the shell
PostgreSQL	`EXPLAIN …`	`EXPLAIN (ANALYZE, BUFFERS) …`
MySQL	`EXPLAIN …` / `EXPLAIN FORMAT=TREE`	`EXPLAIN ANALYZE …`
SQL Server	Estimated plan (Ctrl+L)	Actual plan, `SET STATISTICS IO ON`

Composite indexes and the leftmost-prefix rule

An index on (user_id, created_at) is sorted by user_id, then by created_at within each user — like a phone book sorted by surname, then first name. It helps queries that constrain a leftmost prefix of its columns.

SQL

CREATE INDEX idx_events_user_time ON events (user_id, created_at);

EXPLAIN QUERY PLAN SELECT * FROM events WHERE user_id = 42 AND created_at >= '2024-03-01';
EXPLAIN QUERY PLAN SELECT * FROM events WHERE user_id = 42;
EXPLAIN QUERY PLAN SELECT * FROM events WHERE created_at >= '2024-03-01';

Output

id | parent | notused | detail
---+--------+---------+----------------------------------------------------------------------------
3  | 0      | 51      | SEARCH events USING INDEX idx_events_user_time (user_id=? AND created_at>?)

id | parent | notused | detail
---+--------+---------+-----------------------------------------------------------
3  | 0      | 62      | SEARCH events USING INDEX idx_events_user_time (user_id=?)

id | parent | notused | detail
---+--------+---------+------------
2  | 0      | 216     | SCAN events

The third query cannot use the index: without user_id, the created_at values are scattered across the whole index. Column order rule of thumb: equality columns first, then the range/sort column.

Covering indexes

If the index contains every column the query needs, the engine answers from the index alone and never touches the table.

SQL

CREATE INDEX idx_events_user_kind ON events (user_id, kind);

EXPLAIN QUERY PLAN
SELECT kind, COUNT(*) FROM events WHERE user_id = 42 GROUP BY kind;

Output

id | parent | notused | detail
---+--------+---------+--------------------------------------------------------------------
6  | 0      | 55      | SEARCH events USING COVERING INDEX idx_events_user_kind (user_id=?)

PostgreSQL / SQL Server (INCLUDE)

-- PostgreSQL 11+ / SQL Server: extra payload columns stored in the leaf, not part of the key
CREATE INDEX idx_orders_cust ON orders (customer_id) INCLUDE (order_date, status);

Other kinds of index

SQL

CREATE UNIQUE INDEX ux_users_name ON users (name);                          -- also a constraint
CREATE INDEX idx_events_buy ON events (created_at) WHERE kind = 'buy';      -- partial
CREATE INDEX idx_emp_lower_name ON employees (lower(name));                 -- expression

EXPLAIN QUERY PLAN SELECT event_id FROM events WHERE kind = 'buy' AND created_at >= '2024-03-25';
EXPLAIN QUERY PLAN SELECT * FROM employees WHERE lower(name) = 'sara';

Output

id | parent | notused | detail
---+--------+---------+-----------------------------------------------------------------
2  | 0      | 183     | SEARCH events USING COVERING INDEX idx_events_buy (created_at>?)

id | parent | notused | detail
---+--------+---------+-----------------------------------------------------------
3  | 0      | 61      | SEARCH employees USING INDEX idx_emp_lower_name (<expr>=?)

Index type	Good for	Where
B-tree	Equality, ranges, sorting — the default	All
Hash	Equality only	PostgreSQL, MySQL MEMORY
GIN / full-text	Arrays, JSONB, text search	PostgreSQL, MySQL `FULLTEXT`, SQLite FTS5
GiST / R-tree / spatial	Geometry, ranges, nearest neighbour	PostgreSQL, MySQL, SQLite R*Tree
BRIN	Huge, naturally ordered tables (time series)	PostgreSQL
Bitmap	Low-cardinality columns in warehouses	Oracle

Clustered vs non-clustered

The cost side

Every INSERT, DELETE and indexed-column UPDATE must update every index — write-heavy tables should have few.
Indexes take disk and memory (buffer cache).
Low-selectivity columns (status with 4 values, booleans) rarely benefit alone — the planner prefers a scan when a large fraction of rows match.
Unused and duplicate indexes ((a) next to (a, b)) are pure cost; drop them.

How does an index speed up a query?

Why might a query not use an index?

Clustered vs non-clustered index?