Indexes and B-trees.

An index is a small, sorted copy of one column of a table, kept next to it, so the database can jump straight to the rows you want instead of reading every row to find them. It is the same trick as the alphabetical index at the back of a book.

It’s the single biggest speed lever you have in a database. The right one can make a query thousands of times faster, and the wrong set of them can quietly halve how fast you can write data in. If you ever keep logs of what your ranker showed and what people clicked, both of those will happen to you. “Why is this query slow?” and “why not index every column?” are also two of the most common database questions in interviews, and both have a precise answer.

You’ve already seen why reading from memory is about a thousand times faster than reading from an SSD in How slow is slow?, and how disks move data in fixed-size chunks in What happens when you save a file?. In Why not a JSON file? you built a store that could find one key fast but couldn’t keep keys in order. This lesson fixes that, and it sets up Transactions and Nearest neighbors at scale, which asks how you’d index things that can’t be sorted at all.

Today

• Say exactly what an index is, physically: a second, sorted copy of some columns, stored in the same fixed-size chunks the table uses, with each entry pointing back at its row.
• Explain how a wide, shallow tree of those chunks finds one row among a billion in about four reads from disk, and do the arithmetic yourself from the chunk size and the key size. (This tree is the B-tree.)
• Read the report Postgres prints when you ask how it ran a query, and say why it chose to read the whole table, use the index, or something in between, including when it ignores your index on purpose.
• Choose the column order for an index built on several columns at once, and know when an index holds everything a query needs, so the table itself never gets read.
• Explain why every index slows down writes, measure by how much, and describe the alternative design that writes faster by only ever appending (the LSM-tree, used by RocksDB and Cassandra).

Before this, do How slow is slow? (memory versus SSD, about 1,000x apart) and What happens when you save a file? (data moves in fixed-size blocks, and the operating system keeps recently used ones in spare memory). Plan on one evening for the Postgres half and one for writing the tree yourself.

The Problem

You log every click on your ranker’s results into a table: who clicked, which document, for which query, how long they stayed. After a few months it has 5 million rows. You write the obvious query for a debugging dashboard:

SELECT * FROM clicks WHERE user_id = 4242;

It takes 200 ms. Fine, until the dashboard runs it for 50 users per page load, and now each page takes 10 seconds. Someone on the team says “just add an index”, you run one line, and the same query takes 0.1 ms. Two thousand times faster, from a line of SQL that took one second to run.

That’s suspicious. Nothing about the data changed. The CPU didn’t get faster. So where did 199.9 ms go? And if indexes are this good, why doesn’t the database just index every column for you?

It doesn’t, because there’s a bill. A week later the ingestion job that writes those clicks has slowed to half its speed, because someone added five indexes “to be safe”. Same trade, other side.

By the end of this lesson you’ll know what an index is on disk, roughly byte for byte, and you’ll be able to predict both numbers above before running anything.

The Idea

A phone book, and what the machine does instead

Imagine a box of 5 million index cards, one per click, in the order they happened. To find all of user 4242’s clicks you have to look at every card. That’s a full table scanfull table scanReading every row of a table and checking each one against the condition. Postgres calls it a Seq Scan (sequential scan). Cost grows with the size of the table, not the size of the answer., and its cost has nothing to do with how many cards you want. Finding one card or a thousand, you read all 5 million.

A phone book is the fix everyone knows. Names are sorted, so you open near the middle, see “M”, jump back toward “G”, and land on the right page in a few flips. Two things make that work: the entries are sorted by the thing you search for, and you can jump to the middle of the book instead of reading from the front.

But your clicks can only be sorted one way, and you want to search by user, by document, by time. So you don’t sort the box. You build a second, small box next to it: one card per click, holding only user_id and a note saying where the real card is (“box position 1,844,210”). Sort the small box by user_id. Now you binary search the small box, read the notes, and pull exactly the real cards you need.

That small sorted box is an indexindexA separate data structure, stored alongside a table, that holds copies of one or more columns in sorted order (or hashed), each with a pointer to the row it came from. It exists only to make lookups fast.. That is the whole idea. Everything else in this lesson is about how to make the small box fast on a real disk, and what it costs to keep it sorted.

What’s actually on disk

Postgres stores a table as a file chopped into pagespagesFixed-size blocks that a database reads and writes as one unit. 8 KB in Postgres, 16 KB in MySQL’s InnoDB, 4 KB by default in SQLite. The database never reads less than one page. of 8 KB. Rows go into pages in roughly the order they arrive, wherever there’s space. This file is called the heapheapIn Postgres, the table’s main file: rows stored in pages in no particular order. Nothing to do with the heap data structure, or with your process’s heap from the stack-and-heap lesson. It means “a pile”., meaning “a pile”, nothing more. Every row has an address: which page, and which slot inside the page. Postgres calls that address the ctidctidA row’s physical address in Postgres: (page number, slot number). For example (1844, 3) means slot 3 of page 1,844. Indexes store this to point at rows., written like (1844,3).

An index on user_id is a different file. Its entries are (user_id, ctid) pairs, kept in user_id order, also stored in 8 KB pages.

Two things to notice already.

The index is a copy. It duplicates the user_id column, plus 6 bytes of address and a few bytes of bookkeeping per row. On the 5-million-row table you’ll build, the table is 365 MB and the primary-key index alone is 107 MB. Copies take space, and copies have to be kept in sync. Hold onto that; it’s the whole write-cost story later.

Sorted isn’t enough. If the index were one long sorted file of 13,000 pages, you could binary search it: about log₂(13,000) ≈ 14 jumps, each a separate page read. From How slow is slow?, a random SSD read is around 80 µs, so 14 of them is about 1.1 ms, and on Bayer’s spinning disk with ~10 ms seeks, 140 ms. Better than a full scan, but each jump only rules out half of what’s left. We can do much better by ruling out 99.7% per jump.

B-trees: make every jump count

Here’s the trick. Reading one page costs the same whether you use 8 bytes of it or all 8,192. So when you read a page, make it carry as much direction as possible.

Take the sorted index and cut it into pages of a few hundred entries each. Those are the bottom layer, the leaf pagesleaf pagesThe bottom level of a B-tree. Leaves hold the actual index entries (key plus row pointer), in sorted order, and each leaf links to the next one.. Now make a page that lists, for each leaf, the first key in it and the leaf’s page number: “keys from 1 to 13,580: page 1; from 13,581: page 2; …”. That’s a signpost page, an inner pageinner pageA B-tree page above the leaves. It holds only separator keys and pointers to child pages, like the letter tabs on a phone book. Also called an internal or branch node.. If one signpost page can’t hold all the leaves, make several, and a signpost page above them. Keep going until one page sits at the top: the rootrootThe single page at the top of a B-tree. Every search starts here..

That’s a B+treeB+treeThe B-tree variant every major database uses: inner pages hold only separator keys for steering, all entries live in the leaves, and the leaves are chained left to right so you can walk them in order.. To find a key, read the root, pick the child whose range covers your key, read it, repeat until you’re at a leaf. One page per level.

The drawing has three keys per page so it fits. A real page holds hundreds, and that number is everything.

Why it’s always about four levels

The number of children one inner page can point to is its fan-outfan-outHow many children one B-tree page points to. Roughly page size divided by the size of one entry. High fan-out means a short tree.. Let’s work it out for the primary key of your clicks table, a bigint (8 bytes):

• One leaf entry in Postgres is the 8-byte key, plus an 8-byte header that includes the 6-byte row address, plus a 4-byte slot in the page’s directory. Call it 20 bytes.
• A page is 8,192 bytes, minus a few dozen of header. Postgres fills leaves to 90% when it builds an index, so about 8,150 × 0.9 / 20 ≈ 367 entries per leaf. Inner entries are about the same size, so the fan-out is also in the high 300s.
• 5,000,000 rows / 367 ≈ 13,600 leaf pages. That’s 13,600 × 8 KB = 107 MB, which is exactly the size Postgres reports for this index. The arithmetic is real.
• 13,600 leaves / 367 ≈ 37 inner pages. 37 fits in one root. Height: 3.

Each extra level multiplies capacity by ~367. Three levels hold about 367³ ≈ 49 million keys. Four levels: 18 billion. That’s why the answer to “how deep is the index?” is almost always 2 to 4, whether the table has a thousand rows or a billion.

Now turn that into time, using the latency ladder. Each level is one page read.

• All from SSD, nothing cached: 3 or 4 reads × ~80 µs ≈ 0.3 ms.
• Realistically: the root and second level are tiny (one page, then a few dozen), get touched by every query, and so stay in RAM, either in Postgres’s own cache or the OS page cachepage cacheThe kernel’s copy of recently used file data in spare RAM. Covered in the files-and-disks lesson. A “disk read” that hits it costs microseconds, not tens of microseconds.. A cold lookup costs maybe 1 or 2 real SSD reads, plus one for the table page. Well under a millisecond.
• All in RAM: a few microseconds, mostly binary searching inside each page.

Compare a full scan of a 5 GB table at ~3 GB/s: well over a second. Play with the numbers. Push rows to 10 billion. Make the key 256 bytes (a long text column). Switch to 16 KB pages like MySQL.

Notice how little anything moves. Ten thousand times more rows adds about two levels. A 32x bigger key costs one or two. This is the payoff of a fan-out in the hundreds: logarithmlogarithmHow many times you multiply by a base to reach a number. log base 367 of 49 million is 3. Logarithms grow so slowly that “log of the table size” is nearly a constant in practice. base 367 grows absurdly slowly. A binary tree would be log base 2: about 23 levels for 5 million rows, 23 page reads, and that’s why databases never use binary trees on disk.

Keeping it sorted: inserts and page splits

Searching is the easy half. The hard half is that new rows keep arriving, and the leaves must stay sorted.

To insert key 42: walk down exactly as for a search, to the leaf where 42 belongs, and slide it into place inside that page. Most of the time the page has room and that’s it: one page changed.

When the leaf is full, the database performs a page splitpage splitWhen a B-tree page is full and needs one more entry: allocate a new page, move the upper half of the entries into it, and add a separator key pointing at the new page to the parent.. Take a new empty page, move the top half of the entries into it, link it into the leaf chain, and tell the parent: “keys from here up now live in the new page”, which means inserting one separator key into the parent. If the parent is full too, it splits, and pushes a separator into its parent. In the worst case the split climbs all the way up, the root splits, and a new root is made above it.

That last step is the clever part. A B-tree grows at the top, not the bottom. Every leaf is always at the same depth, so the tree is always perfectly balanced, and no search is ever unlucky. Nobody has to rebalance anything.

Try it below. The pages here hold 3 or 4 keys so splits happen often. Insert 22, then 23, then 24. The first splits a leaf; the third splits a leaf, which overflows its parent, which splits the root, and a new root appears: every leaf is now one level deeper at once. Then search for keys and compare the two counters: the tree reads one page per level, the scan reads leaf pages from the left until it finds the key.

Two things the toy shows that are true of the real thing:

1. The search cost is the height, and the height barely moves. With 3 keys per page you’ll reach height 4 at around 40 keys; with real pages of ~367 keys, height 4 holds tens of billions of rows.
2. Pages are often not full. A split leaves two half-full pages. After random inserts, B-tree pages average about 70% full (a classic result, and what you’ll measure in Postgres in Break It). The “+5 in order” button shows the opposite pattern: ever-increasing keys always land in the rightmost leaf. This toy splits 50/50, so ascending inserts leave a trail of half-empty leaves. Real databases detect this case and split the rightmost page unevenly, keeping the old page full, which is why an auto-incrementing key gives you a compact index.

The other half of the lookup: back to the table

The index leaf gives you a ctid, not the row. To return SELECT *, Postgres must still read the table page the row lives on. So “find one row by primary key” is really 3 index pages plus 1 table page, which is exactly what you’ll see in EXPLAIN (ANALYZE, BUFFERS): Buffers: shared hit=1 read=3, four 8 KB pages, one of which (the root) was already cached.

If the query matches many rows and they’re scattered across the table, that’s one table page per row. Fifty-six clicks for user 4242 means fifty-six different table pages, because that user’s clicks arrived at fifty-six different times and landed wherever there was space. Hold that thought: it’s the reason the planner sometimes refuses your index.

Clustered vs secondary indexes

There are two ways to arrange the table and its indexes, and the databases you’ll meet disagree.

Postgres: a heap plus secondary indexes. The table is the unordered pile. Every index, the primary key included, is a separate B-tree whose leaves point at ctids. That makes every index a secondary indexsecondary indexAn index stored separately from the table, whose leaf entries point at where the row lives. A table can have many..

MySQL InnoDB, SQLite, SQL Server (usually): a clustered index. The table is a B-tree, keyed by the primary key, and its leaves hold the entire row. That’s a clustered indexclustered indexAn index whose leaves contain the full rows, so the table itself is stored sorted by that key. A table can have only one, because rows can only be physically sorted one way.. Rows are physically sorted by primary key, so a primary-key range scan reads consecutive pages, with no jumping. Secondary indexes on that table store the primary key value instead of a physical address, so looking up by a secondary index means two descents: one down the secondary index to find the primary key, another down the clustered index to find the row.

Neither is better, but it matters when you choose primary keys: on InnoDB, a random key like a UUID scatters inserts across the whole table, and every secondary index carries a copy of that 16-byte key.

In Postgres, if rows happen to be stored roughly in key order, an index range scan reads neighbouring table pages anyway. Postgres measures this per column as correlationcorrelationA statistic Postgres keeps per column, from -1 to 1: how closely the physical order of rows matches the sorted order of that column. 1 means sorted on disk. Visible in the pg_stats view.. Your created_at column will have correlation near 1, because clicks are inserted in time order. user_id will be near 0.

Covering indexes: skip the table entirely

If every column the query needs is already in the index, why visit the table at all? A covering indexcovering indexAn index that contains every column a particular query needs, so the database can answer from the index alone without visiting the table. lets Postgres do an index-only scanindex-only scanA plan that reads only index pages. In Postgres it still checks a small visibility map to know whether each row is visible to this transaction; after VACUUM, almost no table pages are touched..

You can make one two ways. Put the extra columns in the key, (user_id, dwell_ms), or carry them as passengers that aren’t part of the sort order: CREATE INDEX ... ON clicks (user_id) INCLUDE (dwell_ms). On your table, averaging dwell_ms over 1,000 users (50,000 rows) took 66 ms with a plain index on user_id, reading 30,846 table pages, and 2.9 ms with the covering index, reading about 140 index pages and zero table pages.

The catch is the one from before: the index is a copy, and now a bigger one.

Composite indexes and the leftmost-prefix rule

A composite indexcomposite indexAn index on several columns at once, sorted by the first column, then by the second within ties of the first, and so on. Also called a multi-column index. on (user_id, created_at) is sorted like a phone book sorted by last name, then first name. All of user 12’s entries are together, in time order; then all of user 88’s; and so on.

That ordering decides which queries it helps, and it is the most useful single fact about indexes in practice.

The general rule is the leftmost-prefix ruleleftmost-prefix ruleA composite index on (a, b, c) can be used efficiently for conditions on a, on a and b, or on a, b and c: any prefix of its columns from the left. A condition on b alone can’t use the sort order, because b is only sorted within each value of a.. An index on (a, b, c) is sorted by a first, so it helps queries that pin down a; or a and b; or all three. It’s nearly useless for b alone, the way a phone book sorted by last name doesn’t help you find everyone called “Wei”.

A good recipe for ordering columns:

1. Columns compared with = go first.
2. Then at most one column used for a range (>, BETWEEN) or for ORDER BY. After a range, later columns can’t narrow the search, because within the range they aren’t sorted.
3. Then, optionally, INCLUDE the columns you only read, to make it covering.

For the dashboard query, WHERE user_id = ? AND created_at >= ? ORDER BY created_at LIMIT 20, that gives (user_id, created_at). The index even hands rows back already in created_at order, so the sort and the LIMIT are free: Postgres reads 20 entries and stops.

Selectivity, and why the planner ignores your index

Postgres doesn’t run the first plan it thinks of. Its query plannerquery plannerThe part of the database that considers several ways to run a query (scan the table, use this index, use that one, in what order to join) and picks the one its cost model says is cheapest. Also called the optimizer. estimates the cost of each option and picks the cheapest. It estimates using statistics gathered by ANALYZE: for each column, the most common values and how often they appear, a histogram of the rest, the number of distinct values, and the correlation.

The key number is selectivityselectivityThe fraction of rows a condition matches. user_id = 4242 matches 56 of 5M rows (0.001%, very selective). country = ‘US’ matches 39% (not selective at all).. If a condition matches a tiny fraction of rows, the index wins by a mile. If it matches a big fraction, the index loses, for a reason you can now work out yourself:

• A sequential scan reads the 46,729 table pages in order, which disks and the OS do at full speed (readahead, big requests).
• An index scan reads index pages plus one table page per matching row, in random order. If 39% of rows match and they’re spread evenly, nearly every page has a match. You end up reading the whole table anyway, in random order, plus the index.

Postgres prices a random page read at 4x a sequential one by default (random_page_cost = 4, seq_page_cost = 1), a number chosen in the spinning-disk era. Somewhere around a few percent of rows, depending on row width and correlation, the lines cross and it switches to a scan.

Between “a few rows” and “most rows” there’s a middle option, the bitmap scanbitmap scanA two-step plan: first scan the index and collect the addresses of all matching rows into a bitmap of table pages, then read those pages in physical order. Turns random table reads into sorted ones. Appears as Bitmap Index Scan + Bitmap Heap Scan., which collects all the matching addresses first, sorts them by page, and then visits each needed page once, in order.

There’s a subtle trap here that your measurements will show. On your table, country = 'FR' matches only 5.6% of rows, and the planner used a bitmap scan. It still read every one of the 46,729 table pages, because with about 107 rows per page, almost every page holds at least one French click. Selectivity in rows isn’t what matters. Selectivity in pages is.

So, the usual reasons Postgres ignores your index:

1. The condition isn’t selective enough (above). The planner is usually right.
2. The query wraps the column in something. WHERE lower(email) = ..., WHERE user_id + 0 = 4242, WHERE created_at::date = .... The index is sorted by the column, not by lower(column). Fix: write the condition on the bare column, or build an expression indexexpression indexAn index on the result of an expression, like lower(email), rather than on a raw column. Postgres can then use it for queries that contain that exact expression..
3. The leftmost column isn’t constrained. A query on created_at alone can’t use (user_id, created_at) for seeking.
4. The table is tiny. If it fits in a few pages, reading them all is cheaper than a descent.
5. The statistics are stale or wrong. After a big load, until ANALYZE runs (autovacuum does it eventually), the planner may think the table is empty or the value rare. Correlated columns fool it too, because it assumes conditions are independent.
6. The cost settings don’t match your hardware. On SSDs, random reads aren’t 4x worse. Many people set random_page_cost to around 1.1. Change it if you measure that the index plan really is faster, not before.

The bill: what every index costs on write

Now the other side. When you INSERT a row into a table with five indexes, Postgres:

1. Writes the row into a heap page.
2. For each index: descends from the root to the right leaf and inserts an entry, possibly splitting pages.
3. Records all of those page changes in the WALWALWrite-ahead log. Postgres writes every change to this append-only log, and fsyncs it at commit, before changing data pages on disk. After a crash it replays the log. The files-and-disks lesson is the background., so they can be replayed after a crash.

So one row becomes six B-tree or heap insertions, and if the indexed values are random, each lands on a different leaf, probably one not in cache. An UPDATE is worse than you’d guess: Postgres never overwrites a row in place; it writes a new version of the row elsewhere, so every index needs a new entry pointing at it too. (There’s an optimization, HOT updateHOT updateHeap-only tuple update. If no indexed column changed and the new row version fits on the same page, Postgres skips adding new index entries. One reason not to index columns you update constantly., that skips the index work when no indexed column changed and the new version fits on the same page.)

This gives you write amplification: one logical write causes many physical ones. Indexes also cost space, cache (index pages compete with table pages for RAM), and VACUUM time.

When writes dominate: LSM-trees

A B-tree updates data in place: find the page, change it, write it back. Each insert is a small random write, and with many indexes and random keys, that’s a lot of random I/O. Some systems take in far more writes than reads: event logs, metrics, message stores, the click log itself at large scale. For them, there’s a different design.

Remember the trick from Why not a JSON file?: appending to a log is the cheapest write there is. The LSM-treeLSM-treeLog-structured merge-tree. A storage design that buffers writes in a sorted in-memory table, flushes it to disk as immutable sorted files, and merges those files in the background. Used by RocksDB, LevelDB, Cassandra, ScyllaDB, HBase. (log-structured merge-tree) builds a whole index out of that idea.

1. Write: append the change to a log on disk (for crash safety), then insert it into the memtablememtableThe in-memory, sorted part of an LSM-tree, usually a skip list or balanced tree. All new writes go here first. Typically tens of megabytes., a sorted structure in RAM. That’s it. No disk page was read or rewritten.
2. Flush: when the memtable reaches some size (RocksDB’s default is 64 MB), write it to disk in one sequential pass as an SSTableSSTableSorted string table. An immutable file of key-value pairs in sorted order, with a small index of where each block starts. Written once, never modified, eventually merged away.: a sorted, immutable file. Start a fresh memtable.
3. Compact: in the background, merge SSTables together (like the merge step of merge sort), keeping only the newest version of each key and dropping deleted ones. That’s compactioncompactionBackground merging of an LSM-tree’s sorted files into fewer, larger ones, discarding overwritten and deleted entries. Costs disk bandwidth, keeps reads fast.. Files are organized into levels, each roughly 10x bigger than the last.

Reads are where you pay. A key might be in the memtable or in any of the files, so a lookup may have to check several places, newest first. Two things keep that tolerable. Each file has a small sparse index, so checking one file costs at most one block read. And each file has a bloom filterbloom filterA compact bit array that answers “is this key in the set?” with either “definitely not” or “maybe”. With about 10 bits per key it says “maybe” wrongly about 1% of the time. Lets a reader skip files that can’t contain the key., so most files that don’t contain the key are skipped without touching the disk at all.

The trade, roughly:

Rule of thumb: read-heavy with updates to existing rows, B-tree. Ingest-heavy, append-mostly, LSM. Postgres and MySQL are B-tree databases. RocksDB is an LSM engine embedded in many systems (including as a MySQL storage engine), and Cassandra and ScyllaDB are LSM databases.

Hash indexes

Last, the simplest one. If you only ever ask “is key X here, and where?”, you don’t need sorting at all. A hash indexhash indexAn index that hashes each key to a bucket, giving roughly one-step equality lookups. It has no order, so it can’t do ranges, sorting, or prefix searches. hashes the key to a bucket and looks there. It’s the dict of indexes: O(1) lookups, no order.

Postgres has them (CREATE INDEX ... USING hash, crash-safe since version 10), but they only support =, and a B-tree descent is already only 3 or 4 mostly-cached pages, so B-tree stays the default. Hash indexes shine in memory: Redis is essentially a giant hash table, and the Bitcask design keeps a hash table of key → file offset in RAM over an append-only log, which is exactly the store you build in Why not a JSON file?.

Build It

Everything lives in ~/workbench/indexes/. Part one is Postgres: make a big table, feel the scan, add indexes, read the plans. Part two you write yourself: a B+tree.

# Docker
docker run --name pg -e POSTGRES_PASSWORD=pg -p 5432:5432 -d postgres:17
docker exec -it pg psql -U postgres

# or Homebrew
brew install postgresql@17
brew services start postgresql@17
"$(brew --prefix postgresql@17)/bin/psql" postgres

\timing on
CREATE TABLE clicks (
  id         bigint PRIMARY KEY,
  user_id    int         NOT NULL,
  doc_id     int         NOT NULL,
  query      text        NOT NULL,
  dwell_ms   int         NOT NULL,
  country    text        NOT NULL,
  created_at timestamptz NOT NULL
);

INSERT INTO clicks
SELECT g,
       (random() * 99999)::int + 1,                 -- ~100k users, ~50 clicks each
       (random() * 999999)::int + 1,                -- ~1M docs
       'query ' || (random() * 50000)::int,
       (random() * 60000)::int,
       (ARRAY['US','US','US','US','IN','DE','BR','JP','GB','FR'])[1 + (random()*9)::int],
       timestamptz '2026-01-01 00:00+00' + g * interval '5 seconds'   -- time order = insert order
FROM generate_series(1, 5000000) AS g;

VACUUM ANALYZE clicks;

SELECT pg_size_pretty(pg_relation_size('clicks'))      AS table_size,
       pg_size_pretty(pg_relation_size('clicks_pkey')) AS pk_size,
       pg_relation_size('clicks') / 8192               AS table_pages;

CREATE EXTENSION pageinspect;
SELECT level, fastroot FROM bt_metap('clicks_pkey');   -- level of the root: 2 means height 3
SELECT * FROM bt_page_stats('clicks_pkey', 1);         -- one page: live_items, avg_item_size, free_size

SELECT * FROM clicks
WHERE user_id = 4242 AND created_at >= '2026-06-01'
ORDER BY created_at
LIMIT 20;

SELECT count(*) FROM clicks
WHERE created_at >= '2026-06-01' AND created_at < '2026-06-02';

# bptree.py
from bisect import bisect_left, bisect_right

class Leaf:
    __slots__ = ("keys", "vals", "next")      # next: the leaf to the right, or None

class Inner:
    __slots__ = ("keys", "kids")              # len(kids) == len(keys) + 1

class BPlusTree:
    def __init__(self, order: int = 64):
        """order = max keys per node. Start with a single empty leaf as the root."""

    def _find_leaf(self, key) -> tuple[Leaf, list[Inner]]:
        """Descend from the root. Return the leaf where key belongs, and the path of
        inner nodes above it (you'll need the path to push splits upward)."""

    def search(self, key):
        """Return the value for key, or None."""

    def insert(self, key, val) -> None:
        """Insert or overwrite. If the leaf overflows, split it and push a separator
        into the parent; repeat upward; if the root splits, make a new root."""

    def range(self, lo, hi):
        """Yield (key, val) for lo <= key < hi, in order, using the leaf chain."""

    def height(self) -> int: ...

import random, bisect
def check(order: int, n: int = 200_000) -> None:
    t, ref = BPlusTree(order), {}
    for k in random.sample(range(10_000_000), n):
        t.insert(k, k * 2); ref[k] = k * 2
    s = sorted(ref)
    # 1. every key found with the right value; a missing key returns None
    # 2. 200 random ranges: list(t.range(lo, hi)) == the slice of s between lo and hi
    # 3. print t.height()
for order in (3, 4, 64, 256):
    check(order)

Measure

Fill this in. Run each query twice and keep the second (the first pays for loading pages into cache). Your Postgres version and disk will differ from mine; the ratios shouldn’t.

What the numbers should tell you:

Scan vs index: about 2,000x. The scan read 46,729 pages to return 56 rows; the index read 3 index pages and 56 table pages. That ~790x gap in pages explains most of it; the rest is CPU spent checking 5 million rows. Three processes made the scan 3x faster, but no parallelism closes a 790x gap in work.

The primary key lookup is 4 pages: 3 index levels and 1 table page. That matches the height arithmetic exactly, and bt_metap should report root level 2.

The US query is the honest surprise. The planner chose the scan, but forcing the index was a little faster on my Mac (86 ms vs 112 ms). Everything was already in RAM (365 MB fits easily in the page cache of a 48 GB machine), so “random” reads cost the same as sequential ones and random_page_cost = 4 was too pessimistic. On a cold cache or slower disk the planner would be right. This is exactly when people lower random_page_cost on SSD machines. Check whether your run agrees.

The FR query reads every page despite matching 5.6% of rows, because the matches are spread across all pages. Pages, not rows.

Composite order: 23 vs 7,322 pages for the same query. With (user_id, created_at) the matches are contiguous and the LIMIT 20 stops after 20 entries. With (created_at, user_id) Postgres walks every entry since June 1 checking user_id, and fetches table pages as it goes. Flip to the daily report and the winner flips too: 70 pages vs a full scan. Indexes are designed for queries, not for columns.

Covering: 66 ms to 2.9 ms by not visiting 30,846 table pages.

Writes: the primary key is nearly free, random-key indexes aren’t. Ascending keys (id, created_at) append to the rightmost leaf. Random keys (user_id, doc_id, query) touch a different leaf each time. Bulk inserts got 11x slower with five indexes; single-row inserts only 2x slower, because each one also pays a commit. (On macOS, Postgres’s default commit doesn’t force the SSD’s own cache to flush, which is why one-row commits are so cheap here; see Files, disks and fsync. Expect fewer rows per second on Linux with a real flush.)

Your B+tree vs a sorted list: 6 s vs 280 s. insort finds the spot with a fast binary search but then has to shift every element after it one slot to the right. On average that’s a quarter of a million pointers, about 2 MB of memory moved per insert, around 2 TB in total. That is exactly why databases don’t keep one big sorted array on disk: each insert would rewrite half the file. The B+tree only ever shifts entries inside one small node. And the dict beats both by 40x, because hashing doesn’t keep anything in order. That’s the hash index trade, measured.

Break It

1. Random primary keys. Create three tables with a two-column schema (id, v int) and insert 3 million rows into each: id as ascending bigint; as (random() * 1e15)::bigint; as uuid from gen_random_uuid(). Time each and compare index sizes. On my Mac: 9.5 s and 64 MB; 29 s and 79 MB; 96 s and 123 MB. Then REINDEX the random-bigint table and check again (it shrank to 64 MB). The random keys produced pages about 73% full on average instead of 90%, from splits all over the tree, and the UUID index is bigger again because each key is 16 bytes. Every insert dirties a different leaf, and Postgres writes a full copy of each page into the WAL the first time it changes after a checkpoint, so random keys also multiply WAL volume. This is why people use time-ordered IDs (UUIDv7, snowflake IDs) for big tables.

2. Stale statistics. Create a new table, insert 1 million rows where every country is 'US', run ANALYZE, then insert 1 million 'FR' rows and immediately EXPLAIN a query for 'FR' before autovacuum notices. Watch the estimated rows (rows=) differ wildly from the actual. Run ANALYZE and see the plan change. Most “Postgres randomly picked a terrible plan” stories are this.

3. Break your B+tree on purpose. Change the inner-node split to keep the middle key in the right half (as the leaf split does) instead of moving it up. Run your checker. Which test fails first, and why does search still work for most keys? Then put the off-by-one in _find_leaf (use bisect_left) and find which keys go missing. Your checker should catch both; if it doesn’t, it isn’t checking enough.

4. Index everything. Index every column of clicks and rerun the bulk insert. Compare pg_indexes_size('clicks') to the table size (indexes bigger than the table is common), then check pg_stat_user_indexes.idx_scan after your dashboard queries: most were never used once, and every one was paid for on every insert.

Explain It Back

Answer out loud, in plain words, as if in an interview. Then check.

Go Deeper

• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3: “Storage and Retrieval”. The best single explanation of hash indexes, SSTables, LSM-trees and B-trees side by side, and where this lesson’s LSM section comes from. Read it next.
• Markus Winand, Use The Index, Luke! A free online book about indexing for developers. The chapters on the leaf chain, composite index column order and “functions in the where clause” are the practical companion to this lesson.
• PostgreSQL docs: Chapter 11, Indexes and Using EXPLAIN. Covers multicolumn indexes, index-only scans, expression indexes, and how to read every line of a plan. The B-tree chapter also explains deduplication.
• Douglas Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys, 1979. The classic survey: B-trees, B+trees, why they won. Short and readable.
• Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil, “The Log-Structured Merge-Tree (LSM-Tree)”, Acta Informatica, 1996. The original LSM paper. Read the introduction for the cost argument; it’s still the clearest statement of why batching writes wins.
• Alex Petrov, Database Internals (O’Reilly, 2019), Part I. Goes deep on B-tree page layouts, splits, merges, and LSM compaction strategies, with diagrams. The book to read if you want to build a storage engine.
• CMU 15-445/645 Database Systems (Andy Pavlo), the B+tree and index lectures. Free on YouTube. Fast, opinionated, and full of what real systems actually do.
• The Postgres source: src/backend/access/nbtree/README. How Postgres’s B-tree handles many readers and writers at once (the Lehman and Yao design). Read it once your own B+tree works and you wonder what happens when two inserts split the same page.

Connections

This lesson stands on How slow is slow?: the whole B-tree design is “minimise the number of ~80 µs page reads”. It’s also Files, disks and fsync one layer up: pages, the page cache and the WAL are the same machinery.

Next, Transactions explains why Postgres writes new row versions instead of updating in place, which is where the HOT-update detail came from. Caching and Redis is the hash-index idea taken to its extreme, entirely in RAM. And Nearest neighbors at scale asks the question this lesson can’t answer: B-trees work because keys can be sorted. Embeddings can’t be sorted in any useful way, so how do you index 100 million of them?