Database indexes
A database table can have millions of rows. If you ask it 'find the user named Maya' and it has no help, it does the dumbest possible thing: it reads row 1, nope, row 2, nope, row 3, nope… all the way down until it finds her. For a giant table that's brutally slow. An index is a clever little helper that lets the database jump STRAIGHT to the right row instead of reading every single one.
The slow way: scan every single row
Picture the rows of a table just dumped in the order they arrived, like papers tossed in a box in no particular order. To find Maya, there's no shortcut — you have to pick up paper after paper and check the name, one by one, until you hit hers. If she's the very last of a million rows, you read a million rows. That 'check them all, one by one' approach is called a full table scan. If you've met it in algorithms, it's exactly linear search: the work grows in step with the table — twice the rows, twice the looking, on average. Written in big-O it's O(n). It's fine for a tiny table. It is a disaster for a huge one, and it gets worse every day the table grows.
The fast way: an index, like the back of a book
Think about how you find a word in a big textbook. You don't read all 600 pages — you flip to the index at the back, where every word is listed in alphabetical order with its page number. You find your word in seconds and turn straight to that page. A database index is exactly that. Alongside the messy table, the database keeps a small extra structure that lists the values in SORTED order, each paired with a pointer to the row it lives in. To find Maya, the database searches the tidy sorted index — and because it's sorted, it doesn't read that one by one either: it can leap to the middle, see whether 'Maya' comes before or after, and throw away half the index in one step, again and again. If that 'cut it in half each time' move sounds familiar, it's binary search — the index turns a slow O(n) scan into a fast O(log n) lookup. Then the pointer sends it straight to the real row. Found, almost instantly, no matter how big the table got.
Linear vs. binary search, in one breath (no algorithms degree needed)
Without an index, finding a value is like looking for a name in an UNSORTED list: you have no choice but to read every entry — that's linear, slow, grows with the list. With an index, the values are kept SORTED, and searching a sorted list lets you cut it in half every guess — that's binary search, dramatically faster. The whole magic of an index is just: 'keep a sorted copy of the thing you search by, so you can play the cut-it-in-half game instead of reading everything.' You don't need to know how to code binary search to use this — the database does it for you the moment you create an index.
The catch: indexes aren't free
If indexes only made things faster, the database would just index everything and be done. It doesn't — because an index has two real costs. First, space: the index is an extra sorted copy of the column, so it takes up additional storage. Index ten different columns and you're storing ten extra sorted lists alongside your table. Second, and more important: indexes slow down WRITES. Every time you add, change, or delete a row, the database doesn't just touch the table — it must also update every index to keep them correctly sorted, or they'd point to the wrong place. So an index makes reads faster but writes slower. That's the trade: you add indexes to the columns you SEARCH by a lot, and you don't bother indexing columns you rarely look up, because each index is rent you pay on every single write.
It's a tradeoff
| Option | 👍 Pro | 👎 Con |
|---|---|---|
| Add an index on a column | Lookups on that column go from a slow scan-everything (O(n)) to a fast jump (O(log n)) — huge on big tables. | Costs extra storage, and slows every write: each insert/update/delete must also keep the index sorted and correct. |
| No index (just the raw table) | Writes are as fast as possible — adding a row only touches the table, nothing else to maintain. No extra storage. | Every search is a full scan: fine on tiny tables, but painfully slow as the table grows to millions of rows. |
Questions you might have
▸Is an index a copy of the whole table? That sounds wasteful.
No — it copies just the ONE column you search by (say, the name), kept in sorted order, plus a little pointer to each full row. It's much smaller than the table. Think of a book's index: it lists the words and page numbers, not the entire book again.
▸If indexes make lookups so much faster, why not put an index on every column?
Because each index has to be kept up to date on every write. Add a row, and the database must update the table AND every index. Index everything and your writes crawl, plus you waste a lot of storage. So you index only the columns you actually search by often — the rest aren't worth the rent.
▸I don't really know binary search. Do I need to, to understand indexes?
Not at all. The one idea to keep is: searching a SORTED list is way faster than searching a jumbled one, because you can keep cutting it in half. An index simply keeps a sorted copy so the database can do that fast search for you. You never write the search yourself.
▸Why doesn't the database just keep the whole table sorted, instead of a separate index?
Because a table can only be physically sorted one way at a time, but you might want to search by name AND by email AND by date. A separate index per column lets you have a fast sorted lookup for EACH of them at once. Also, re-sorting the entire table on every insert would be far more expensive than nudging a compact index.
▸Does an index make my data more correct or just faster?
Just faster — it changes nothing about WHAT answer you get, only how quickly you get it. The table is still the source of truth; the index is purely a speed shortcut for finding rows. (A special kind, a 'unique index,' can also enforce 'no two rows with the same value,' but its main job is still speed.)
Best read after: What is a server?