How a Database Index Actually Works: B-Trees, Seq Scans, and the Cost Nobody Mentions

The same query. 4.2 seconds, then 3 milliseconds. Same data, same machine, same SQL. The only thing that changed was one line:

CREATE INDEX idx_customers_email ON customers(email);

Most explanations of indexing start at "it's like the index in a book" — and then stop. That analogy is fine as far as it goes, but it skips the part that actually matters: why the database is slow without one, and what it costs you to add one. So let's start a level below the index.

Throughout, one running example: BrewBox, a coffee shop with a customers table of 5,000,000 rows, and one query their login page runs on every single page load:

SELECT * FROM customers WHERE email = 'sara@mail.com';

---

First principles: what a table actually is

Here's the thing nobody tells you up front. A table is a pile of rows on disk, written one after another in the order they arrived. That's it. Nothing about it is sorted.

Sara signed up 3 million rows ago, sandwiched between whoever signed up just before and just after her. Her row isn't in an alphabetical slot. There is no alphabetical slot. There's just insert order.

So when you ask for WHERE email = 'sara@mail.com', the database genuinely does not know where that row is. And it has no clever way to guess, because nothing about the layout of the file correlates with email addresses.

The full table scan

With no idea where Sara is, the database has exactly one option: look everywhere.

Row 1 — not Sara. Row 2 — not Sara. Row 3 — not Sara. All the way down. Five million reads, to return one row. That's a full table scan (Postgres calls it a Seq Scan), and it's not the database being dumb — it's the database having no alternative.

And it's worse than a one-time 4.2-second hit, because this is a login page. Every page load does the whole thing again. Ten users online means ten full scans of five million rows, concurrently, competing for the same disk.

---

Enter the index

Now the one line of SQL:

CREATE INDEX idx_customers_email ON customers(email);

Notice what this doesn't do. It doesn't change your table. It doesn't change your query — you still write the same SELECT, and the planner just quietly starts using the index. Nothing in your application code changes.

What it builds is a second structure, on the side. And that structure holds only two things per row:

1. the indexed column (the email), and
2. a pointer to where that full row physically lives on disk.

Not the whole row. Just the value and the address. And critically — it is kept sorted.

That's the entire trick, and it's worth saying plainly: sorted means you can skip. Once the values are in order, you no longer have to look at something to rule it out. You can rule out half the remaining data with a single comparison.

The B-tree: three hops, not five million reads

Concretely, that sorted structure is a B-tree. Searching it is the game of "higher or lower," and every guess throws away most of what's left:

• Is sara@mail.com before or after "m"? After → go right. (Half the index just disappeared.)
• Before or after "sar"? Take that branch.
• Three hops down, and you're on the exact entry — holding a pointer straight to Sara's row.

The reason this scales so absurdly well is that a B-tree is wide, not deep. Each node holds hundreds of keys, so the tree fans out fast. Five million rows is only about three levels deep. Ten times the data doesn't cost ten times the work — it costs roughly one more hop.

The payoff

3 rows read instead of 5,000,000. 4.2 seconds → 3 milliseconds. Roughly 1,400× faster, with the same query, the same data, and the same machine.

---

The cost nobody mentions

Here's the part that gets left out of every "just add an index" answer.

An index is a copy. It's a real structure that lives on disk, so it costs disk. That's the small cost.

The real cost is this: every write has to keep it true. Insert one customer and the database doesn't do one write — it writes the row, and then it also updates every index on that table, because an index that doesn't know about Sara is an index that lies.

Six indexes on customers? One INSERT becomes seven writes. Same for updates and deletes. Index every column "just in case," and your reads get fast while your writes quietly crawl.

So an index is not free speed. It's a trade: faster reads, slower writes.

	No index	With an index
Lookup by that column	Full scan — reads every row	~3 hops down a B-tree
Rows read to find one	5,000,000	3
Query plan	Seq Scan	Index Scan
Scaling	Linear — 10× rows, 10× work	Logarithmic — 10× rows, ~1 more hop
Cost of one INSERT	1 write	1 write + 1 per index
Disk	Just the table	Table + a copy of the column
Best for	Write-heavy tables, tiny tables	Columns you filter, join, or sort on

The verdict: what to index, and what not to

Index the columns you actually filter, join, or sort on — the ones in your WHERE, your JOIN ... ON, your ORDER BY. Those are the columns where a sorted side-structure buys you something real.

Don't index everything else. An index nobody queries is pure cost: disk you pay for and writes you slow down, forever, in exchange for nothing. A few good indexes beat a dozen speculative ones.

Two practical notes:

• Tiny tables don't need indexes. If the whole table fits in a page or two, scanning it is the fast path — the planner will often ignore your index anyway, and it's right to.
• Low-cardinality columns are usually a bad fit. An index on a boolean is_active can't skip much — half the table matches either way. Indexes pay off when the value is selective enough to eliminate most rows.

---

The same idea, one layer up: indexes in AI systems

If you work on LLM or RAG systems, you've already met this exact trade — just wearing a different hat.

When a RAG pipeline retrieves context, it's answering "which of my 5,000,000 chunks are closest to this query embedding?" The naive answer is the same as BrewBox's: compare against all of them — a full scan, just with cosine similarity instead of =. It works fine at ten thousand vectors and falls over at ten million, for precisely the reason above: linear scaling.

So vector databases do the same thing a relational database does: build a sorted-ish side-structure that lets you skip. A B-tree can't do it (embeddings have no meaningful "before m"), so the structure is different — typically HNSW, a navigable graph you greedily hop through, which I break down in Vector Search — how HNSW finds nearest neighbours. But the shape of the deal is identical:

• Same payoff: don't touch most of the data. Hops, not a scan.
• Same cost: the index is a copy that costs memory, and every insert has to update it — which is exactly why re-embedding a large corpus is slow, and why some vector stores make you rebuild rather than insert cheaply.
• Same discipline: index the thing you actually query on.

The one extra wrinkle: a B-tree lookup is exact, while a vector index is approximate — HNSW may miss a true nearest neighbor, and you tune that recall/latency trade knowingly. Beyond that, if you understand why CREATE INDEX makes reads fast and writes slow, you already understand why your vector store behaves the way it does. It's the same bargain: pay on write, save on read.

---

Where your 4.2 seconds went

Here's the one thing to actually do with this. Take your slowest endpoint, grab the query it runs, and put EXPLAIN in front of it:

EXPLAIN ANALYZE SELECT * FROM customers WHERE email = 'sara@mail.com';

Read the plan. If you see Seq Scan on a big table, that's not a mystery anymore — that's the database telling you, in plain language, that it's reading every row because you never gave it another option. You just found your 4.2 seconds.

And if you see Index Scan, the index is doing its job. The remaining question is the other half of the trade: are you paying for any indexes nobody reads?

Want the visual version? Watch the reel.