How a database index works

· 2 min read

#how-it-works#data

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.

How an index finds a row Top row, left to right: a query, the index sorted by id, the row id, and the table row. A dashed path from the query goes down to a box for a full scan when there is no index, and from there up to the table row. Query id = 42 Index sorted by id Row id from the index Table row the data 1 2 3 No index: full scan
Simplified: solid arrows are the indexed path, dashed arrows the path without an index.

Step by step

  1. A query arrives with a condition such as WHERE id = 42.
  2. With no index on id, the database reads every row.
  3. With one, it does a binary search in the index.
  4. The matching index entry holds the row id.
  5. 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