PostgreSQL B-Tree Index Explained: How It Really Works

If you have ever run CREATE INDEX in PostgreSQL without specifying a type, you built a B-tree. The PostgreSQL B-tree index is the default access method and handles most production workloads: equality lookups, range filters, sorting, and the unique constraints behind primary keys. This guide explains how it is structured, how PostgreSQL searches it, what happens on writes, and how to keep it fast in production.

A B-tree ("balanced tree") is a sorted, self-balancing, multi-level data structure. PostgreSQL uses it to map indexed key values to the physical location of table rows, so the planner can find matching rows by descending a handful of tree pages instead of scanning the whole table. It is the only index type that supports the full set of ordering-aware operations, which is why it backs PRIMARY KEY and UNIQUE constraints by default (see the index types overview in the official docs).

Why B-Tree Is the Default Index Type

CREATE INDEX without a USING clause creates a B-tree (CREATE INDEX reference). It is the default because it is the most general access method: equality, ranges, sorting, prefix search, and uniqueness all work in one structure. The other index types are specialists — excellent at one job, useless at the rest.

The O(log n) Idea in Plain Terms

Each B-tree level has a high fanout: one page points to hundreds of children. Doubling the table adds roughly one level, not twice the work. In practice, most B-trees are three to four levels deep even with hundreds of millions of rows. A lookup therefore touches a handful of index pages — a logarithmic, not linear, amount of I/O.

A PostgreSQL B-tree: root page, internal routing pages, leaf pages with key + TID entries, and right-sibling links.

Root, Internal, and Leaf Pages

Every B-tree has three kinds of pages:

• Root page — the fixed entry point; every search starts here.
• Internal pages — routing nodes; each entry holds a key bound and a downlink to a child page.
• Leaf pages — the bottom level; each entry holds an indexed key plus a pointer to a heap row.

What Lives Inside an 8 kB Page

PostgreSQL stores all tables and indexes in fixed-size pages (8 kB by default). A B-tree page contains a small header, line pointers, and index tuples, plus a high key that marks the upper bound of the keys stored on that page. During concurrent inserts, the high key — together with right-sibling links between leaf pages — lets PostgreSQL split pages safely while readers keep scanning.

How Keys and TIDs Point to Heap Rows

Each leaf entry stores the key plus a TID (tuple identifier): a heap page number and item offset. During an index scan, PostgreSQL follows those TIDs to fetch the actual rows. Because the heap is not stored in index order, fetching many rows means random heap access — one reason the planner sometimes prefers a bitmap scan or a sequential scan instead. That trade-off is covered in our index scan vs sequential scan comparison, and the page-level details across all access methods are in how PostgreSQL index internals work.

Equality Lookups

For WHERE email = '[email protected]', PostgreSQL descends from the root, follows the downlink whose key range contains the value, and binary-searches within each page. At the leaf it finds the TIDs and fetches the heap rows. The cost is a few page reads regardless of table size.

Range Scans and ORDER BY for Free

SELECT * FROM orders
WHERE created_at >= '2024-01-01'
  AND created_at <  '2024-02-01'
ORDER BY created_at;

Leaf pages are linked left-to-right in sorted order, so after finding the first match, PostgreSQL simply walks right until the range ends. Because entries emerge already sorted, the planner can drop the explicit sort step entirely — b-tree range queries and ORDER BY are satisfied by the same structure.

Descending Columns and NULLS FIRST/LAST

A B-tree index sorts ascending with NULLS LAST by default; scanning it backwards yields DESC NULLS FIRST. But ORDER BY ts DESC NULLS LAST cannot use that index — you need a matching definition:

CREATE INDEX idx_events_ts ON events (ts DESC NULLS LAST);

Define index column order to match your most expensive sort clauses, especially in combination with the composite index column ordering rules.

Page Splits and Random Insertions

When an insert lands on a full leaf page, PostgreSQL splits it roughly in half and promotes a separator key to the parent — which may itself split, up to the root. Monotonically increasing keys (serial IDs, timestamps) append to the rightmost leaf, which PostgreSQL special-cases to keep pages full. Random keys (UUIDs) scatter inserts across the tree, causing repeated splits and permanently lower page density — the root cause of much B-tree bloat.

Fillfactor Tuning for Hot Pages

B-tree pages default to fillfactor = 90, reserving free space for future inserts and updates. If a hot page splits constantly, create the index with a lower fillfactor:

CREATE INDEX idx_users_last_seen
ON users (last_seen)
WITH (fillfactor = 70);

This helps when updates repeatedly touch the same rows. The trade-off is a slightly larger index, and the setting is fixed at creation — changing it requires a rebuild.

B-Tree Deduplication in PostgreSQL 13+

PostgreSQL 13 added B-tree deduplication: repeated identical keys in a leaf page are merged into one tuple carrying a list of TIDs. Indexes with many duplicate values (status columns, skewed foreign keys) shrink significantly and split less often. It is on by default and controllable per index with the deduplicate_items storage parameter.

B-tree compared with hash, GIN, GiST, and BRIN index types by workload fit.

Operators B-Tree Supports

B-tree handles =, <, <=, >, >=, BETWEEN, IN, IS NULL / IS NOT NULL, and sorting. Prefix searches like LIKE 'abc%' can use it, with a caveat: in non-C locales you need a text_pattern_ops operator class, otherwise the planner cannot apply the index to the pattern:

CREATE INDEX idx_users_email_pattern ON users (email text_pattern_ops);

Patterns with no fixed prefix (LIKE '%abc') cannot use a B-tree at all.

When Hash, GIN, GiST, or BRIN Win Instead

Rule of thumb: default to B-tree and switch only when a workload clearly fits a specialist. A hash index competes only for equality-only lookups; a GIN index is the standard choice for JSONB containment; a BRIN index trades precision for a tiny footprint on time-series tables. For the broader decision framework, see our PostgreSQL indexing guide.

Measuring Size and Bloat with pgstattuple

CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT * FROM pgstatindex('idx_orders_created_at');

pgstatindex reports leaf-level statistics such as avg_leaf_density and fragmentation (pgstattuple docs). Density near the fillfactor indicates a healthy index; low density after heavy churn means bloat that only a rebuild removes — autovacuum cleans dead heap tuples but does not shrink indexes. Fold these checks into your routine using the steps in our PostgreSQL index performance tuning guide. PostgreSQL 14 also added bottom-up index deletion, which prunes dead index tuples during updates and slows bloat growth on frequently updated indexes.

Corruption Checks with amcheck

CREATE EXTENSION IF NOT EXISTS amcheck;
SELECT bt_index_check('idx_orders_created_at');

bt_index_check verifies B-tree invariants cheaply enough to run against production systems; bt_index_parent_check validates parent/child relationships more thoroughly but takes stronger locks, so schedule it in maintenance windows (amcheck docs).

Rebuilding with REINDEX CONCURRENTLY

REINDEX INDEX CONCURRENTLY idx_orders_created_at;

Available since PostgreSQL 12, REINDEX CONCURRENTLY rebuilds without blocking reads or writes. If it fails midway, it leaves an invalid _ccold index behind — drop it and retry. On production systems, prefer it over a plain REINDEX, which takes an exclusive lock.