Database Indexing

Build the mental model

Without an index, finding rows matching a condition requires a full table scan — the database reads every single row and checks it, an O(n) operation that gets slower as the table grows, no matter how selective the query is. An index is a separate, auxiliary data structure (most commonly a B-tree) that keeps a sorted mapping from column values to row locations, so a lookup can binary-search the tree in O(log n) and jump straight to matching rows, much like a book's index lets you skip to a page instead of reading cover to cover. This speed isn't free: every INSERT, UPDATE, or DELETE must also update every index on that table, and each index consumes additional disk space, so a table with ten indexes has noticeably slower writes than one with two. Indexing the wrong column (low-cardinality columns like a boolean flag barely narrow the search) or over-indexing (adding indexes 'just in case') often costs more in write overhead and storage than it ever saves on reads.

Connect it to a real scenario

The Tutorial Platform runs a query like 'find all lessons where slug = X' on essentially every page load, so the lessons table has an index on slug — turning what would be a full scan of thousands of rows into a near-instant lookup. But early on, an engineer also added an index on 'is_published' (a boolean with only two possible values), which barely narrows anything and just slows down every content update without meaningfully speeding up reads — a textbook case of indexing low-cardinality data. Auditing which columns actually appear in WHERE/JOIN clauses, not guessing, is what keeps the index set useful.

Without an index, matching rows requires an O(n) full table scan.
A B-tree index is a sorted structure enabling O(log n) lookups, like a book's index.
Every index slows writes and costs storage — indexing the wrong column can cost more than it saves.

Try the working example

text

WITHOUT INDEX (full table scan)          WITH INDEX (B-tree on `slug`)
+-------------------------+               +---------------------+
| row 1: slug="go-intro"  | check         | B-tree (sorted)     |
| row 2: slug="rust-fn"   | check         |      [go-intro]     |
| row 3: slug="cdn-edge"  | check <- MATCH|     /            \   |
| row 4: slug="sharding"  | check         | [cdn-edge]  [rust-fn]|
| ... (10,000 more rows)  | check x 10000 +---------------------+
+-------------------------+               lookup("cdn-edge")
O(n) — cost grows with table size          -> binary search, O(log n)
                                            -> jump straight to match

Trade-off: every INSERT/UPDATE/DELETE must also update the B-tree.
More indexes = slower writes + more disk space, even if reads are fast.

You should see

The diagram shows an index turns O(n) reads into O(log n) lookups, but every write must also update that index structure.

5-minute try-it

The Tutorial Platform's quiz_attempts table has columns user_id, lesson_id, score, attempted_at. For the query pattern 'show a user's attempt history ordered by time', decide which column(s) you'd index and why.

One important caution

Indexing a low-cardinality column (a boolean/status flag) barely narrows the search since so many rows share the same value, making the index nearly as slow as a scan.

Adding an index on every column 'just in case' significantly degrades write performance while rarely-queried indexes waste storage.

Wikipedia — Database index — System Design