B-tree — The Default, and What It Costs

A B-tree index is a balanced tree of 8 KB pages. Its leaves hold the indexed values in sorted order, each paired with the address of a physical row version; the levels above hold separator keys that say which child to descend into. That one structure answers equality, ranges, IN lists, IS NULL, sorted output without a sort, and MIN/MAX — and it has to be maintained by every write that touches the indexed column, which is the half of the deal that never makes it onto the ticket saying "add an index".

Cartwheel's orders table carries nine of them. Three have not been scanned once since statistics were last reset. Every insert on Saturday morning, at 3,000 orders a minute, writes ten things: the row itself and one entry in each of the nine indexes, all of it logged and all of it shipped to pg-replica-a. This topic is what the tree buys and what those ten writes cost, because an indexing decision made from only the first half is a guess.

The Shape of the Tree

Every lookup starts at the root page and descends: read the root, pick the child whose key range contains the value, read that page, repeat until the leaf level. Depth grows logarithmically because an internal page on a bigint key holds several hundred separators, so each additional level multiplies the number of addressable rows by that fan-out. A 40-million-row index on orders.id is three or four levels deep. The root and the level below it are read on every single lookup, so they live permanently in shared_buffers; the marginal cost of a point lookup is one leaf page read plus one heap page read.

So "will the index still be fast when the table is ten times bigger" has an unexciting answer: ten times the rows buys at most one more level, and that level is probably cached. Leaf pages also carry sibling links, so a range scan descends once and then walks sideways along the leaf level instead of returning to the root for every value. BETWEEN over a narrow range therefore costs barely more than a single lookup.

What It Can Answer

The access method is defined by five operators, <, <=, =, >= and >, and everything else it serves is built out of them. BETWEEN and IN are combinations. IS NULL and IS NOT NULL work because nulls are stored in the tree at a defined end. Sorted output falls out of the leaf order, so ORDER BY placed_at DESC LIMIT 20 can be answered by walking the leaf level backwards with no sort node at all, and max(placed_at) is a one-row scan of one end.

CREATE INDEX orders_placed_at_idx ON orders (placed_at);

-- served: range, ordering, and the extreme value
SELECT * FROM orders WHERE placed_at >= '2026-08-01'
                       AND placed_at <  '2026-09-01';
SELECT * FROM orders ORDER BY placed_at DESC LIMIT 20;
SELECT max(placed_at) FROM orders;

-- not served: the column is wrapped in a function call
SELECT * FROM orders
 WHERE date_trunc('month', placed_at) = '2026-08-01';

The three that work all compare the indexed column itself against a constant. The fourth compares a computed value, and the index stores no such value, so the only way to evaluate it is to compute date_trunc for all 40 million rows. Rewriting it as a range on the bare column fixes it for free; indexing the expression instead is the subject of a later topic, and it is a real answer rather than a workaround.

Pattern matching is the one place where the default operator class is not enough. A B-tree serves LIKE or ~ when the pattern is a constant anchored at the start, so sku LIKE 'CW-88%' qualifies and sku LIKE '%88' never can, but outside the C locale that needs an index built with text_pattern_ops, which compares character by character rather than by collation rules. The trade is fixed: such an index serves pattern matching and equality and cannot serve ordinary < or > comparisons. A column needing both gets two indexes, and a leading wildcard needs a different access method entirely.

The Write Cost

For a table four years in production, nine indexes is not an unusual number, and no single one of them was a bad idea on the day it was added.

Indexes:
    "orders_pkey" PRIMARY KEY, btree (id)
    "orders_public_id_key" UNIQUE, btree (public_id)
    "orders_customer_id_idx" btree (customer_id)
    "orders_customer_id_placed_at_idx" btree (customer_id, placed_at DESC)
    "orders_placed_at_idx" btree (placed_at)
    "orders_status_idx" btree (status)
    "orders_status_placed_at_idx" btree (status, placed_at)
    "orders_customer_id_status_idx" btree (customer_id, status)
    "orders_total_idx" btree (total)

Read that list as a write path, not as a menu. Inserting one order means locating the correct leaf page in nine separate trees and adding an entry to each, occasionally splitting a page in the process, and writing every one of those changes to the WAL that pg-replica-a has to replay. An update that changes an indexed column has to insert a new entry in every index, because the index points at a physical row version and the update produced a new one — the mechanism Chapter 7 examines from the vacuum side, where those superseded entries become the cleanup work. Deletes and superseded versions leave entries behind that only vacuum removes, so the nine indexes also set how long a vacuum of orders takes.

Selectivity, and When the Index Loses

An index scan pays a random page read per matching row plus a visit to the heap page holding that row; a sequential scan reads the table in physical order, which storage and the kernel both reward. Postgres prices random reads well above sequential ones, so the crossover arrives early: past roughly 5 to 10 percent of the table matching, reading everything in order is genuinely cheaper than doing hundreds of thousands of scattered lookups. "The planner is ignoring my index" is usually a report of the planner being right about a query that returns 30 percent of orders. It is occasionally a bad row estimate instead, and Chapter 9 is where you learn to tell those two apart from the plan rather than by argument.

Size, and the Bloat With a Schema Cause

Budget roughly 16 bytes per row for the entry itself on a bigint or timestamptz key, and about twice that once per-page overhead, the internal levels and the free space a B-tree carries at its default 90% fill are counted in. On orders that is under a gigabyte per index and nobody notices. On delivery_events, at 1.2 billion rows, the same arithmetic produces the 40 GB B-tree on occurred_at that this chapter later replaces with something three orders of magnitude smaller. There is also a hard ceiling on a single entry: an index tuple cannot exceed approximately one third of a page, about 2.7 KB, and exceeding it fails the INSERT at run time on whichever row happens to be long — not at CREATE INDEX time, and not in testing.

Insertion order decides how much of that space is wasted. Keys that arrive in ascending order pack the rightmost leaf and move on, and B-tree builds fill leaf pages to a fillfactor of 90 by default. Keys that arrive in random order land in the middle of existing pages, split them into two roughly half-full pages, and leave them that way, producing an index twice the size it needs to be with a schema decision as its cause. Fixing one that has already bloated is a rebuild, and doing it without blocking writes is the last topic of this chapter. That is exactly why Cartwheel's orders.public_id is a v7 UUID and not a v4: v7 values sort by time, so the index appends instead of scattering.

Deduplication and Skip Scan

Since 13, B-trees deduplicate. Groups of entries with identical keys are merged into a single posting list tuple: the key value is stored once, followed by a sorted array of row addresses. On orders_status_idx, where 40 million rows carry perhaps six distinct statuses, that is the difference between an unusable index and a compact one. It is on by default and controlled per index by the deduplicate_items storage parameter. It does not apply everywhere: numeric and jsonb are excluded because display scale must be preserved, float4 and float8 because -0 and 0 must stay distinguishable, along with nondeterministic collations, container types such as arrays, and any index carrying an INCLUDE column.

Since 18 there is a skip scan. A multicolumn B-tree can now be used when an early column has no equality constraint from the query, by generating a matching-every-value constraint internally for that column and combining it with a real constraint on a later one. The planner takes it only when there are so few distinct values in the unconstrained column that most leaf pages can be skipped outright. With many distinct values the whole index would have to be read, and a sequential scan wins.

Both features mean that indexing advice written before 13 is now too pessimistic: a low-cardinality column is no longer automatically a bad index, and a composite is no longer automatically dead weight for queries that skip its leading column. The write path in this topic did not get any cheaper, so neither feature is a reason to add indexes more freely.