Skip to content
Back to DatabasesAll lessons

Databases

Indexes (why lookups get fast)

Without an index: O(n) per lookup. With an index (a hash map): O(1) average per lookup. The tradeoff: indexes use extra memory and slow down writes a little, because the index itself must stay updated.

The idea, in plain English

A database index works just like the index at the back of a textbook. Without it, finding 'photosynthesis' means checking every page one by one. This is a slow scan. With an index, you jump straight to the page number, because the index already knows where everything is.

How it works

  1. 1Without an index, WHERE id = 105 checks every row until it finds a match, or reaches the end. This is a linear scan.
  2. 2CREATE INDEX builds a fast lookup structure ahead of time, like a hash map that points straight from a key to a row. It is built on the column you search most.
  3. 3With the index, WHERE id = 105 jumps straight to the matching row in about one step, instead of checking every row.

When you'd use it

Add an index to any column you filter or join on often, especially in big tables. Primary keys get an index automatically. You add more yourself for columns you search a lot.

Common beginner mistakes

  • Do not add an index to every column 'just in case'. Each index makes INSERT and UPDATE slower and uses more storage.
  • Do not expect an index to help when you are not filtering or joining on that column. Also, a plain index cannot match a column wrapped in a function, such as LOWER(name).

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
SQL: SELECT * FROM products WHERE id = 105 (no index)
Found: Chair, checks: 5
SQL: CREATE INDEX idx_products_id ON products(id);
SQL: SELECT * FROM products WHERE id = 105 (with index)
Found: Chair, checks: 1

Not sure this is the right topic? See the learning paths → or where this leads →