How a database index works
A database index is a sorted structure that sits next to a table. The idea to keep: it lets the database skip most rows when it looks for one.
The short version
Without an index, a query like WHERE id = 42 makes the database read the table row by row, which is called a full scan. With an index on id, the database searches a separate structure that is sorted by id, and it gets back the id of the matching row. Then it goes straight to that row. Because the search is a binary search, it stays fast when the table grows.
Step by step
- A query arrives with a condition such as
WHERE id = 42. - With no index on
id, the database reads every row. - With one, it does a binary search in the index.
- The matching index entry holds the row id.
- The database then finds that row id in the table, which is also a binary search in SQLite.
| No index | With an index | |
|---|---|---|
| Method | reads every row | searches a sorted structure |
| Time grows with | N | log N |
| Writes | no index to update | index kept in sync |
Why it matters
Reads get faster, but every write must also update the index, so PostgreSQL's docs advise dropping indexes you do not use. The planner decides whether an index is worth using, and a B-tree index cannot help a pattern like LIKE '%bar'.
Sources
- SQLite: Query Planning — full scan without an index, the sorted index, the two binary searches, time growing with N or log N
- PostgreSQL: Indexes, Introduction — full scan versus index, the index kept in sync, the write overhead, dropping unused indexes, the planner's choice
- PostgreSQL: Index Types — B-tree for equality and range queries,
LIKE 'foo%'works butLIKE '%bar'does not