01 · The question left open
Knowing rows live in pages does not tell you where.
We ended lesson 02 with a working machine. Rows live in 8 KB pages. Pages must occupy a slot in the buffer pool before anything can be read. Hot pages survive the clock sweep, cold pages are evicted.
All true — and all of it assumes someone already knows which page to ask for. Nothing so far provides that. If you ask for a specific customer’s orders, what tells the database that the row is on page 41,912 rather than page 3?
Without an answer, there is only one strategy that is guaranteed to work: look at everything. This lesson is about what that costs, and what changes when you no longer have to.
02 · The model
Shrink the numbers until you can hold them in your head.
Real tables deal in millions of pages, which hides the shape of the problem. So here is the same machine, small enough to count on your fingers. Picture a vault below and a desk above if that helps — it is the last time this lesson will ask you to. Everything after this section is stated in the terms lesson 02 gave us: pages, rows, and the buffer pool.
The table occupies 100 pages. Each page holds 10 rows, so there are 1,000 rows in total. Lesson 02 measured roughly eight 1 KB rows per 8 KB page; we round to ten here purely to keep the arithmetic clean.
The buffer pool has 10 page slots — it can hold a tenth of the table at once. When all ten are full and another page is needed, the clock sweep evicts the least recently used one to make room.
Everything that follows is measured in one unit only: page reads, meaning the number of times the database must go to disk. Not seconds, not CPU. That is the expensive thing, and it is the thing an index changes.
03 · Without the power
Every query starts from scratch, and the buffer pool never helps.
You want one specific row. Nothing tells the database which page holds it, so there is only one option: read page 1 and check its ten rows, read page 2 and check its ten rows, and keep going.
Suppose the row lives on page 73. That is 73 page reads to answer one query.
And the buffer pool did not help once. It holds ten pages, so by the time the scan reaches page 73 it is holding pages 64 to 73. Pages 1 to 63 were read, scanned, and evicted to make room for the pages that came after them.
Now ask for a row on page 12. It was in memory moments ago — the scan for page 73 evicted it. So this query starts at page 1 and walks again. Twelve more reads.
That is the failure mode in one sentence: the buffer pool is always full, but never full of the right thing. Every page is read once and discarded before it is ever wanted again. You are paying the full price of memory and receiving none of its benefit.
One honest correction, and it makes things worse
The count above assumes the scan can stop at page 73 because it found what it wanted. A real sequential scan usually cannot stop early — nothing guarantees there isn’t another matching row further on, so it must read to the end. The realistic number is not 73 page reads. It is 100.
Full memory. Wrong working set. Another disk walk.
04 · The power
A second structure, small enough to keep, that says where everything is.
What an index is
In one sentence: an index is a small, sorted side-structure that maps the values in a column to the location of the rows holding them — so the database can go straight to a row instead of searching for it.
An index does not copy your rows. Each entry holds exactly two things: the key it is sorted by, and a pointer to the page where that row lives. Nothing else.
That is the entire reason it is small enough to be useful. A row in this table is roughly 800 bytes — ten of them fill an 8 KB page. An index entry on a single column is closer to 30 bytes. So a table page holds 10 rows, while an index page holds about 250 entries.
Rows to index1,000
1,000 entries ÷ 250 entries per index page
Leaf pages needed4
How it works
The entries are kept in sorted order, and sorted order is what makes a lookup cheap. You never scan; you narrow. Each comparison throws away a large part of what remains, instead of eliminating one row at a time.
But sorting alone is not enough on disk. "Jump to the middle and compare" still costs a page read every time you jump, and you would do that repeatedly. So the structure stores the narrowing itself — it writes down, in advance, which page to look at next.
What a B-tree is
A B-tree is a stack of sorted pages. The bottom level, the leaves, holds every entry in order. Each level above holds signposts: keys up to here live on that page; keys up to there live on the next one. You start at the single page on top and follow signposts down until you reach a leaf.
The B stands for balanced, and it earns its place: every leaf sits the same distance from the top. So every lookup costs the same number of page reads. There is no unlucky row.
Every leaf is one step below the root.
How PostgreSQL builds ours
B-tree is PostgreSQL’s default index type — a plain CREATE INDEX gives you one
unless you ask for something else. For our 1,000 rows it comes out two levels deep:
- 4 leaf pages, holding 250 sorted entries each.
- 1 root page above them, holding four signposts — one per leaf.
Five pages in total, against the table’s 100. A lookup reads the root, then the one leaf the root pointed at, then the one table page holding the row. Three page reads.
And when the table grows, the tree gets taller rather than wider — which is remarkably slow growth. One level covers 250 rows, two cover 62,500, three cover more than 15 million. That is why even an enormous table stays three or four pages away from any row you ask for.
Five index pages exist. One lookup touches only two of them.
The magic
Now watch what that does across three requests in a row, on a buffer pool of ten slots.
| Request | Without an index | With an index | Why |
|---|---|---|---|
| Row on page 73 · cold | 73 | 3 | Root, then leaf, then the one table page that holds the row |
| Row on page 12 · next | 12 | 1 | The index pages are still resident, so only the table page is read |
| Row on page 73 · again | 73 | 0 | Index and page 73 are both still in the pool. Nothing is read at all |
Read the last row twice. Without the index, asking the same question again costs exactly what it cost the first time — 73 reads, forever. With the index, the second ask is free.
05 · Why memory suddenly works
The index did not add memory. It brought you under the limit.
This is the insight worth carrying out of the lesson, and the speed-up tends to distract from it.
Before: one query had to examine all 100 pages, and only 10 could be held at once. The requirement was ten times the capacity, so caching was mathematically pointless — nothing you kept was worth keeping, because everything was evicted before it was wanted again.
After: one query needs 3 pages — root, leaf, and the table page. The five index pages settle permanently into five slots, because every single lookup touches them. That leaves five slots for whichever table pages the traffic keeps asking for.
Pages one query needs · before100
10 slots available — the requirement exceeds capacity 10×
Pages one query needs · after3
Nothing physical improved. The disk is not faster and the buffer pool is not larger. The index changed a single number — how many pages one query must examine — from 100 down to 3, and that number was the only thing standing between you and a working cache.
06 · The bargain
Why this is the one to reach for first.
Used well, an index is the best bargain in this course. A few pages of keys turned a hundred page reads into three, then into one, then into none — on hardware that did not change and a database that did not shrink by a single row.
Nothing else you will meet gives you that much for that little. Every technique after this one costs more to build, more to reason about, and more to live with once it is in place. So reach for this one first, and reach for it often.
That is not the whole story, though, and the next lesson tells the other half. An index is cheap to use. It is not at all cheap to keep.
The Old Dragon “Three pages where there were a hundred. Enjoy that tonight, keeper — tomorrow I will show you what it eats.”