B-tree indexes explained from first principles

In the last two posts I covered how PostgreSQL executes a query and how it finds your data, and in the second one I described what a B-tree index looks like and then moved on to scan types. This post goes back and starts from the bottom. Not "what does the structure look like", but "why does it have that shape, what does it cost me, and how do I decide which columns go in it".

If you only keep one idea from this post, keep this one: a B-tree is a sorted list that has been engineered so you can find a spot in it, and change it, while touching very few pages. Everything else follows from that.

Start with the problem

Imagine the simplest possible index: a sorted array of (key, row address) pairs. Finding a key is a binary search, which is fast in memory. But a database doesn't live in memory. It lives on disk, and it reads in 8 KB pages. A binary search over a million-entry array on disk touches around twenty different places, and each one is potentially a separate page read. Worse, the moment you insert a key in the middle, you'd have to shift everything after it.

A B-tree fixes both problems with one trick: make each node as wide as one page. Instead of choosing between two children at each step, you choose between hundreds. That single decision is what keeps the tree shallow, and a shallow tree is what makes the rest of this work.

Why a lookup touches so few pages

Every page in the index holds many entries. For a simple integer key, an index entry plus its bookkeeping is on the order of 20 bytes, so a page holds a few hundred of them. The real number depends on key width, alignment, fill factor and whether it's an internal or leaf page, so treat it as an illustration, not a Postgres constant. For intuition, call it a fanout of roughly 300.

That means:

• One level can point to about 300 pages.
• Two levels reach about 90,000 pages worth of entries.
• Three levels reach roughly 27 million entries.
• Four levels reach into the billions.

The cost of a lookup is the number of levels, because the traversal touches about one index page per level on the way down. So finding one row among tens of millions of entries means visiting only three or four index pages, and that is the whole reason an index exists. Those visits aren't necessarily physical disk reads: Postgres has its own buffer cache, and the operating system has another one underneath it.

Level 0 (root)       1 page      ── compare, pick one child
Level 1              ~300 pages  ── compare, pick one child
Level 2 (leaf)       ~90,000     ── binary search the page, find the key

Inside each page, the entries are sorted, so choosing the right child is a binary search over a few hundred keys already in memory. The expensive part is never the comparing. It's getting the page into memory, and the top levels of a busy index are read so often that they basically live in the buffer cache permanently. In practice the pages a lookup actually has to fetch from disk are often just the leaf and the heap page it points to.

You can check the depth of a real index yourself, no guessing needed:

CREATE EXTENSION IF NOT EXISTS pgstattuple;
 
SELECT tree_level, leaf_pages, avg_leaf_density
FROM pgstatindex('orders_pkey');

tree_level is the number of levels above the leaves, so a value of 2 means a lookup visits three index pages. It's usually a smaller number than people expect.

Ranges come almost for free

Because the leaves are sorted and linked to their neighbors, a range query does one descent to find where the range starts, then walks sideways. WHERE created_at >= '2026-09-01' costs one lookup plus however many rows you actually read. The same property is why an index can return rows already sorted, which matters again in the composite section below.

What writes cost

Reads are the happy path. Here is the part that gets left out of most "add an index" advice: an index is a second copy of part of your data that Postgres has to keep in sync, in sorted order, on every write.

Inserts

Inserting a row means writing it into the table, and then, for every index on that table, descending that index to find the correct leaf and inserting an entry there. A table with five indexes does one heap write and five separate tree descents and insertions per row, and each one is also recorded in the write-ahead log.

This is why bulk loads are often faster when you create the indexes after the data is in, instead of maintaining them row by row.

Page splits

A leaf page has a fixed size. When an insert lands on a page that's full, Postgres splits it: allocate a new page, move about half the entries over, and add a new separator key to the parent. If the parent is full too, it splits as well, and in the worst case that cascades all the way to the root. When the root splits, the tree gets one level taller. That's the only way a B-tree grows in height, and it's why the tree stays balanced without anyone rebalancing it.

Splits are where your key choice starts to matter:

• Sequential keys (a bigserial id, a timestamp) always insert at the right edge of the tree. The same few pages stay hot in cache, and when the rightmost page fills, Postgres leaves the left page nearly full instead of half empty, so the index stays compact.
• Random keys (a random UUID) insert all over the tree. Every insert might need a page that isn't cached, splits happen everywhere, pages end up half-full, and the index grows larger than the same data would need.

If you want UUIDs but also want that right-edge insert pattern, time-ordered UUIDs exist for exactly this reason. PostgreSQL 18 ships uuidv7() built in.

Updates and deletes

An UPDATE in Postgres doesn't normally change a row in place. MVCC writes a new version of the row. Without an optimization, that new version needs its own entries in the indexes, so even an update to a column that isn't indexed at all can mean index maintenance on every index of the table.

The optimization is the HOT update (heap-only tuple). If the update doesn't modify any column referenced by an index (summarizing indexes like BRIN are exempt) and there's enough free space on the same heap page for the new version, Postgres skips the new index entries entirely. That makes the set of columns you index a direct input to your write performance: indexing a frequently updated column, like last_seen_at or a status that flips all the time, turns cheap updates into expensive ones.

A DELETE doesn't synchronously remove its index entries either. Dead index tuples are cleaned up later, primarily by VACUUM, though the B-tree code can also delete some of them opportunistically when a leaf page is about to split, to avoid the split. VACUUM is still the guaranteed cleanup. And a leaf page is only recycled once it's completely empty, so a table where you delete scattered rows can leave an index full of half-empty pages. That's index bloat, and it's why an index can be much bigger than the data in it justifies. You can see the effect with pg_relation_size and avg_leaf_density from earlier.

The practical rule

Every index is a trade: faster reads for the queries it serves, slower writes for every statement that touches the table, plus disk space and cache pressure. An index nobody queries is pure cost. Postgres tracks usage for you:

SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

Run that on a table that's been live for a while and the zero-scan indexes are candidates for investigation, not automatic drops. Check that stats weren't recently reset before you trust it. Keep indexes that back a unique or primary key constraint regardless of scans, since they do a job beyond serving queries, and be careful with indexes used rarely but critically, like a monthly report or an incident-time query.

Composite indexes are one sorted list

The mental model that makes composite indexes click: an index on (a, b) is not two indexes. It's a single sorted list, ordered by a, and where a ties, ordered by b. Like a phone book sorted by last name, then first name.

CREATE INDEX ON orders (customer_id, created_at);

(customer_id, created_at)

(41, 2026-09-02)
(41, 2026-09-18)
(42, 2026-09-01)   ◀── all of customer 42 is contiguous
(42, 2026-09-07)
(42, 2026-09-30)
(43, 2026-09-03)

Once you see it as that list, the rules stop being rules and become obvious:

Equality on the leading column is a jump. WHERE customer_id = 42 lands on a contiguous block. Add created_at >= '2026-09-07' and it's a range inside that block. Both conditions are used to narrow the scan.

Skipping the leading column breaks the model. WHERE created_at >= '2026-09-07' alone has no starting point, because those dates are scattered through the whole list, in chunks, one per customer. This is the case post 2 described. A caveat that's new: PostgreSQL 18 added skip scan, which can let a multicolumn index serve a query that omits a leading column. It works by repeating the search once per distinct value of that column, so it's mostly useful when that column has relatively few distinct values, and the planner picks it by cost. It's an optimization for specific shapes, not a reason to stop thinking about column order.

A range usually ends the contiguous narrowing. Equality conditions on the leading columns, plus an inequality on the first column that has no equality, decide which contiguous stretch of the index gets scanned. Conditions on columns after that are still checked inside the index, so they save visits to the table, but they don't necessarily shrink the stretch being read, because within it the later columns aren't sorted on their own. Skip scan can sometimes change this by repeating searches, but whether it's worth it is a cost decision. That's why equality columns first, then the range or sort column last is a good starting heuristic, though not a universal law.

The sort bonus

The list is already sorted, which means an index can replace a sort step. This query:

SELECT id, total
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 10;

with an index on (customer_id, created_at) doesn't need to find and sort all of customer 42's orders. It jumps to the end of that block and reads ten entries backward, then stops. That is the single biggest win composite indexes give you, and it's invisible if you only think of indexes as filters. With a plain index on customer_id alone, Postgres has to fetch every matching row and sort them just to give you ten.

Choosing the order

A short procedure that works well:

1. Put columns compared with = first.
2. Put the column you range over or sort by last.
3. Among the equality columns, lean toward the one every query uses first, so more queries can share the index.
4. Don't add a column "just in case". Each extra column makes entries wider, which lowers the fanout from earlier, which makes the tree taller and the index bigger.

One more consequence of the sorted-list model: an index on (a, b) can generally support the same searches on a that an index on (a) alone can. It's larger, though, so a workload can occasionally justify keeping both. Most of the time it's redundant weight on every write.

A short checklist

• A B-tree is shallow because each node is a whole page with hundreds of entries, so a lookup visits one index page per level, usually three or four, and many of those are already cached.
• Ranges and ORDER BY are cheap because the leaves are sorted and linked.
• Every index costs a tree insert per row plus WAL, and can cause page splits.
• Random keys split pages everywhere; sequential or time-ordered keys keep inserts on the right edge.
• Indexing a frequently updated column defeats HOT updates.
• Deletes leave dead index entries behind, cleaned up mainly by VACUUM, and half-empty pages don't merge, so indexes can bloat.
• Think of (a, b) as one sorted list: equality columns first, range or sort column last as a starting heuristic, and don't keep both (a) and (a, b) without a reason.
• Use pg_stat_user_indexes to find indexes that may be costing you writes without serving reads, then investigate before dropping anything.

An index isn't a free speedup you sprinkle on. It's a data structure with a price on every write, and it pays off exactly when its sort order matches the questions you actually ask. Knowing the structure is how you tell which ones those are.