# Database Indexes

## 1. What 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.

```sql
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.

![An index on users.email stores emails in sorted order, each pointing to the row's physical location in the unsorted table heap](diagrams/01-index-to-heap.svg)

## 2. The 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.

```sql
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
```

## 3. Primary 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.

## 4. Composite 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.

```sql
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.

## 5. When 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.

## 6. Covering 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"):

```sql
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.

## 7. How 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.

## 8. 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
```