9.1 What is an index, exactly?

How an index works

In a book: The index is a sorted list of words, each pointing to page numbers. Because it's sorted, you don't read it from the start either: you flip straight to "C".

In the system: An index is a separate data structure that stores the values of one or more columns, kept sorted (or otherwise organised for fast lookup), each with a pointer to the row where that value lives.

Now the database keeps a sorted list of every user_id with where each matching row is. A query like WHERE user_id = 7 can jump to 7 instead of checking every row.

Three things to be exact about:

• It's a copy. The index duplicates the indexed column's values. It costs disk space and memory.
• The database keeps it in sync, automatically. Every insert, update and delete updates the index too (9.7).
• The database decides whether to use it. You never say "use this index" in normal SQL. The query planner chooses the cheapest way to answer each query, with or without an index (9.6).

Most databases create an index automatically for the primary key and for unique constraints. Everything else you add yourself.

Memory code: "A sorted copy that points to the page."