Database Indexes

1What an Index Actually Is

A table with no index is a pile of rows the engine can only search by reading every single one — a sequential scan. An index is a separate, auxiliary data structure, stored alongside the table, that maps column values to the physical locations of the rows that hold them, so the engine can jump straight to matching rows instead of scanning the whole table.

CREATE TABLE users (
  id       SERIAL PRIMARY KEY,   -- PostgreSQL creates an index for you automatically
  email    TEXT NOT NULL,
  age      INT NOT NULL
);

-- without an index, this reads every row in the table
SELECT * FROM users WHERE email = 'ana@example.com';

CREATE INDEX idx_users_email ON users (email);

-- now the engine can look email up in the index, and jump straight to the row
SELECT * FROM users WHERE email = 'ana@example.com';

An index is not free: it's extra storage, and every INSERT/UPDATE/DELETE on the table must also update every index defined on it. Indexing is a trade — pay on every write, to save on matching reads.

2The Default Structure: B-tree

Unless told otherwise, CREATE INDEX builds a B-tree index — a balanced, sorted tree structure that supports both exact-match lookups and range queries (<, >, BETWEEN, ORDER BY) in roughly logarithmic time. The mechanics of the B-tree itself are covered in 02-b_tree/ — this topic treats it as the default tool and focuses on when and how to reach for it.

CREATE INDEX idx_users_age ON users (age);

SELECT * FROM users WHERE age > 30;              -- range query: B-tree can do this
SELECT * FROM users ORDER BY age LIMIT 10;        -- B-tree's sorted order services this directly

3Primary Keys and Unique Constraints Are Indexes Too

Every PRIMARY KEY and every UNIQUE constraint is implemented as an index automatically — the engine needs fast uniqueness checking on every insert, and a B-tree is exactly the structure that gives it that. This is why id SERIAL PRIMARY KEY lookups are fast without you ever writing CREATE INDEX — the index already exists, created implicitly by the constraint.

4Composite Indexes: Column Order Matters

An index can span multiple columns, and the order you list them in is not cosmetic — it determines which queries the index can actually help with.

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

-- USES the index: customer_id is the leading column
SELECT * FROM orders WHERE customer_id = 42;
SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2024-01-01';

-- CANNOT use this index efficiently: created_at alone skips the leading column
SELECT * FROM orders WHERE created_at > '2024-01-01';

Think of a composite index as a phone book sorted by (last name, first name): you can jump straight to "Smith, John," and you can jump to all the "Smith"s, but you can't jump to all the "John"s without scanning the whole book — the leading column has to be constrained for the later columns' ordering to be useful at all.

5When NOT to Index

Indexing everything is a common beginner mistake — it doesn't come free, and sometimes it doesn't even help:

• Low-cardinality columns (a boolean is_active, or a status with 3 possible values): the index narrows the search so little that a sequential scan is often just as fast, or faster, once the planner accounts for the overhead of jumping between the index and the table.
• Write-heavy tables with rarely-queried columns: every extra index is extra write cost on every INSERT/UPDATE, paid on every write whether or not that column is ever filtered on.
• Small tables: if the whole table fits in a few disk pages, a sequential scan can beat an index lookup outright — there's nothing to save by narrowing a search that's already cheap.

6Covering Indexes

A covering index includes every column a query needs, so the engine can answer the query directly from the index without a second trip to the actual table rows (an "index-only scan"):

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

-- can be answered entirely from the index, no table lookup needed
SELECT status, total FROM orders WHERE customer_id = 42;

This trades index size (it now duplicates status and total, not just customer_id) for skipping the row-fetch step entirely on matching queries.

7How the Planner Decides to Use an Index

Having an index doesn't guarantee the query planner will use it — deciding whether a sequential scan or an index scan is cheaper for a given query is the query planner's job, and it makes that call using table statistics and cost estimates. That decision-making process, and how to read a plan to see which one actually happened, is the subject of 04-query_optimization/ — this topic is about defining the right indexes; that one is about verifying and tuning how they get used.

📋 Quick Reference

Index = auxiliary structure mapping column values -> row locations, paid for on every write
PRIMARY KEY / UNIQUE -> index created automatically
Composite index (a, b) -> usable for queries filtering on `a`, or `a AND b` — NOT `b` alone
Covering index (INCLUDE ...) -> index-only scan, no trip back to the table
Skip indexing: low-cardinality columns, rarely-filtered columns on write-heavy tables, tiny tables

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: dbidx_database_indexes_theory.md · generated by tools/build_lessons.py