Lesson 08 · Storage engines · Module 1

The Shape of an Index

Rung one of the scaling ladder is "add an index", and it is the rung that most often removes the need for every rung above it. Which makes it worth knowing what you are actually adding — because the shape of a B-tree explains, in one picture, every query it can and cannot help.

The win in this lesson: given a query and an index, you will be able to say whether the index applies — including the cases that surprise people, like why LIKE 'foo%' is fast and LIKE '%bar' cannot be.

1. Pages, not rows

The unit a database reads is not a row. It is a page — a fixed-size block, 8 KB in PostgreSQL by default, fetched whole. Everything about index design follows from that single fact: the currency is how many pages must I touch, and a page holding one useful row costs the same as a page holding two hundred.

A B-tree is a structure built to keep that number small:

"PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages."
PostgreSQL 18 documentation, B-Tree Indexes · Implementation

Three levels is enough for a very large table, because each page holds hundreds of entries — so the fan-out is hundreds per level. That is why a B-tree lookup is a handful of page reads rather than a number that grows with your data.

Two details from that picture do most of the work later. The leaves are sorted and linked sideways, so once you have found the start of a range you never go back up. And the top levels are tiny — the root and internal pages are well under 1% of the index, so they stay in memory, and the only read that genuinely costs you is the last one.

2. What sorting buys, and what it forbids

A B-tree is a sorted structure, and every capability it has comes from that:

"B-trees can handle equality and range queries on data that can be sorted into some ordering. In particular, the PostgreSQL query planner will consider using a B-tree index whenever an indexed column is involved in a comparison using one of these operators: < <= = >= >"
PostgreSQL 18 documentation, Index Types

And it can hand back rows already in order: "B-tree indexes can also be used to retrieve data in sorted order" — which is why an ORDER BY that matches an index is free, and one that does not is a sort over the whole result.

Now the case worth memorising, because it is the clearest demonstration that you understand the shape:

"The optimizer can also use a B-tree index for queries involving the pattern matching operators LIKE and ~ if the pattern is a constant and is anchored to the beginning of the string — for example, col LIKE 'foo%' or col ~ '^foo', but not col LIKE '%bar'."
PostgreSQL 18, Index Types

Why that is not a limitation, but the definition

Think of a phone book. "Surnames starting with Mc" is one lookup and then a walk — everything matching is adjacent, because the book is sorted by the start of the word. "Surnames ending in -son" has no adjacency at all; the matches are scattered through the whole book, so you must read every page. A B-tree is a phone book. A prefix is a range, which is the only thing sorting ever gives you. If a query cannot be expressed as "start here, walk until here", no B-tree in the world will help it — and that is a property of the question, not of the index.

The same logic explains the composite-key rule you may have met as folklore: an index on (a, b) serves WHERE a = ? and WHERE a = ? AND b = ?, but not WHERE b = ? alone. Sorted by a first means rows with a given b are scattered — the "-son" problem again. This is also Lesson 02's clustering key, one layer down: the same idea that made "the last fifty messages" a contiguous read.

3. What it costs on write

Reads are the advertised feature. The bill arrives on writes:

"New leaf pages are added to a B-Tree index when an existing leaf page cannot fit an incoming tuple. A page split operation makes room for items that originally belonged on the overflowing page by moving a portion of the items to a new page… Page splits must also insert a new downlink to the new page in the parent page, which may cause the parent to split in turn. Page splits 'cascade upwards' in a recursive fashion."
PostgreSQL 18, B-Tree Implementation

So an INSERT is not one write. It is a write to the table, plus a write to every index on that table, occasionally plus a page split that rewrites two pages and touches the parent — and very occasionally a root split that adds a level to the whole tree.

Which gives the actual rule about indexes, the one that is more useful than "add an index": every index you add taxes every write, forever, to make some reads cheaper. An unused index is not free and not harmless; it is a permanent tax collected on behalf of a query nobody runs.

4. Check yourself

5. Back to your world

Before anyone proposes a replica, a cache, or a shard, the question is whether the query plan is reading pages it did not need to. Run EXPLAIN (ANALYZE, BUFFERS) and read the buffer counts, not the timings — pages touched is the currency, and it is stable across a warm cache and a cold one.

Ask me things. "walk me through EXPLAIN output properly" · "when is a hash or GIN index the right answer instead?" · "what is a covering index and when does it pay?" · "how do LSM-trees differ, and why did Cassandra pick one?" (that is Lesson 09) · "I think you should index every column that appears in a WHERE clause. Grill me."