How a B-tree index works

Article.

“An index makes lookups O(log n) instead of O(n)” is true and explains almost nothing you actually need. It does not tell you why a composite index has a left-prefix rule, why the planner sometimes refuses to use your index, why an “Index Only Scan” can still read the table, or why one extra index made writes 20% slower.

All of those come from two structural facts. The tree is shaped by the disk page, and the leaf holds a pointer rather than the row.

The mechanism: fanout, not asymptotics

The unit of I/O is a page — 8 KB in Postgres — and a page read costs the same whether you use one byte of it or all of it. So the structure is designed to put as many keys in one page as possible.

binary tree, 10M rows      B-tree, 10M rows

  23 levels deep             3-4 levels deep
  23 page reads              3-4 page reads
  2 children per node        HUNDREDS of children per node

Both are O(log n). The base of the logarithm is the whole point: a binary tree is log₂, a B-tree with a fanout of 500 is log₅₀₀. That is a 6× difference in disk reads on the same asymptotic complexity, and it is why every disk-backed index is a B-tree and not the tree you learned in an algorithms course.

root       [ ... F ... M ... S ... ]        1 page
             │
internal   [ ... Ha .. Ho .. Hy ... ]       1 page
                 │
leaf       [ (Hobbs,→) (Hodge,→) ... ]      1 page
                        │
heap                    the actual row      1 page

Four reads to find one row in ten million, and the top two levels are almost always in memory because every query touches them.

Postgres uses a B+tree variant: all values live in the leaves, and the leaves are linked to their siblings. That is what makes a range scan cheap — find the start, then walk sideways without ever going back up the tree.

The leaf holds a pointer

This is the second fact, and more consequences hang off it than off the first.

index leaf: (value, ctid) ────► heap page ────► the row

An index scan is therefore two lookups: descend the tree, then fetch the heap page. And the second one is random I/O, one page per matching row, in whatever physical order the rows happen to sit.

Everything below follows from that:

• A covering index avoids the second lookup, which is why an index-only scan can be several times faster than an index scan returning the same rows.
• A non-selective index scan is slower than a sequential scan. Returning 30% of a table through an index means a random page fetch per row; reading the whole table sequentially is one streaming pass. The planner switching to Seq Scan there is correct, not a bug.
• The tipping point is a cost setting, not a law. Postgres compares random_page_cost (default 4.0) against seq_page_cost (1.0). That ratio was calibrated for spinning disks; on SSD or cloud storage 1.1 is the common setting, and leaving it at 4.0 is a frequent cause of the planner avoiding a perfectly good index.

Composite indexes: sorted by tuple

The left-prefix rule is usually presented as a rule to memorise. It is a consequence you can derive in one glance at the leaf order.

CREATE INDEX ON events (tenant_id, type, created_at) sorts by all three, as a tuple:

(1, 'click',  09:00)
(1, 'click',  11:00)
(1, 'view',   08:00)     <- type changed, time restarts
(2, 'click',  07:00)     <- tenant changed, both restart
(2, 'purchase', 10:00)

Read the second column on its own: click, click, view, click, purchase. It is not sorted, so there is no way to binary-search it. Same for the third.

That is the left-prefix rule, and it is just “a tuple sort only sorts the later columns within a fixed prefix”. PostgreSQL 18’s skip scan softens the no rows when the leading column has few distinct values: it descends once per value (Index types).

Equality first, then the range

The corollary that decides real column ordering, and the part people miss.

WHERE tenant_id = 7 AND created_at > now() - interval '1 day' AND type = 'click'

With (tenant_id, created_at, type) the index descends on tenant_id, starts a range scan on created_at, and then type is no longer usefully sorted — every row in the range must be checked individually.

With (tenant_id, type, created_at) both equality columns pin an exact prefix and the range scan happens on the last column, reading only matching leaves.

Equality columns first, the range column last. And a range column consumes the rest of the index: anything after it can filter but cannot seek, and cannot supply an ORDER BY either.

Partial indexes

CREATE INDEX idx_active_email ON users (email) WHERE is_active = true;

If 95% of rows are inactive, the index is 5% of the size, stays in cache, and inactive-row updates never touch it.

The catch is that the planner must prove the query is a subset of the predicate, so the filter has to be there:

-- uses it
SELECT * FROM users WHERE email = 'a@b.com' AND is_active = true;

-- does not
SELECT * FROM users WHERE email = 'a@b.com';

Natural targets: status flags, deleted_at IS NULL, feature-gated rows.

Covering indexes

CREATE INDEX idx_users_email ON users (email) INCLUDE (name, created_at);

INCLUDE columns live in the leaf but are not part of the sort key, so they do not affect ordering and cannot be searched — they exist purely to avoid the heap fetch.

EXPLAIN (ANALYZE) SELECT email, name FROM users WHERE email = 'a@b.com';
--  Index Only Scan using idx_users_email  (Heap Fetches: 0)

Check Heap Fetches. See below for why it is frequently not zero.

Where it breaks in production

An “Index Only Scan” that still reads the table

The detail almost nobody knows, and it explains a covering index that did not help.

The index leaf does not record whether a row is visible to your transaction — MVCC visibility lives in the heap. Postgres avoids the heap fetch only when the visibility map marks the page all-visible, and the visibility map is maintained by vacuum.

Index Only Scan ...  (actual rows=50000)
  Heap Fetches: 49873   <- no vacuum: an index scan

On a table that is written constantly and vacuumed rarely, index-only scans quietly degrade into index scans. If a covering index did not deliver, look at Heap Fetches before redesigning anything.

The write cost nobody measured, and HOT

“Each index costs 5-10% on writes” is a rule of thumb that hides the mechanism.

In Postgres an UPDATE writes a new row version. If no indexed column changed and the page has free space, it is a HOT update: the new version chains within the page and no index is touched at all. Otherwise every index on the table gets a new entry. Since PostgreSQL 16, changing only columns covered by BRIN indexes still allows a HOT update.

-- Leave room on each page so updates can stay HOT.
ALTER TABLE hot_table SET (fillfactor = 85);

So the real question is not how many indexes you have but whether your updates touch indexed columns. A table updating a last_seen_at that you indexed pays on every write; the same table with that column unindexed pays nothing.

Index bloat

Deleted and superseded entries are not reclaimed immediately, so an index can grow well past the data it describes — occasionally larger than the table.

REINDEX INDEX CONCURRENTLY idx_users_email;   -- online rebuild

Watch pg_stat_user_indexes and the pgstattuple extension. Bloat also degrades cache efficiency, so a bloated index is slower per read as well as larger.

Indexes that never get used

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

Zero scans after weeks of representative traffic means the index is pure cost. Check that the stats span a full cycle — a monthly report’s index looks unused for 29 days.

Redundant overlapping indexes

(tenant_id) is redundant when (tenant_id, type) exists, because the composite serves every query the single-column one does. Teams accumulate these one migration at a time, and each one is paying write and storage cost for nothing.

Foreign keys are not indexed

Postgres creates an index for a primary key and a unique constraint. It creates nothing for a foreign key.

DELETE FROM users WHERE id = 42;
-- FK check: SELECT ... FROM orders WHERE user_id = 42  -> Seq Scan

A delete on the parent scans the entire child table. On a large orders table this presents as “deleting one user takes 40 seconds”, which nobody connects to a missing index.

CREATE INDEX ix_orders_user ON orders (user_id);

CONCURRENTLY that failed

CREATE INDEX CONCURRENTLY idx_email ON users (email);

Always this form in production — the plain version holds a write lock for the whole build. The cost is that it is slower, cannot run inside a transaction, and on failure leaves an INVALID index behind that still costs writes while serving no reads.

SELECT indexrelid::regclass FROM pg_index WHERE NOT indisvalid;
DROP INDEX CONCURRENTLY idx_email;   -- then retry

Check for invalid indexes after any failed migration.

In Django and SQLAlchemy

class User(models.Model):
    email = models.CharField(max_length=255, unique=True)   # implies an index
    is_active = models.BooleanField(default=True)

    class Meta:
        indexes = [
            models.Index(fields=["last_name", "first_name"]),
            models.Index(
                fields=["email"],
                name="idx_active_email",
                condition=models.Q(is_active=True),        # partial
            ),
        ]

class User(Base):
    __tablename__ = "users"
    id: Mapped[int] = mapped_column(primary_key=True)
    email: Mapped[str] = mapped_column(unique=True)

    __table_args__ = (
        Index("ix_name", "last_name", "first_name"),
        Index("ix_email_lower", func.lower(email)),         # expression index
    )

Both generate CREATE INDEX through migrations. Set the migration to use CONCURRENTLY — Alembic needs autocommit_block(), Django needs AddIndexConcurrently from django.contrib.postgres.operations and atomic = False on the migration.

Why your index is not used

Sargability, implicit casts, composite ordering, selectivity and planner cost settings are one question with one answer, and it has its own note: Why your index is not being used.

The trade not taken

The index you did not create. Every index is a permanent tax on every write to that table, paid forever, to speed up queries that may not run any more. The default should be to add one for a measured slow query and to delete it when the query goes away — and almost nobody does the second half.

The larger trade is the data structure itself. A B-tree keeps data sorted in place, which is what makes reads cheap and writes expensive: a random insert dirties a random page, and maintaining order under a write-heavy load is the whole cost.

The other family inverts it. LSM trees — RocksDB, Cassandra, ScyllaDB — buffer writes in memory and flush sorted runs sequentially, so writes are fast and cheap while reads may have to check several runs. That is why a write-saturated workload sometimes belongs in a different engine rather than in a Postgres table with better indexes.

Knowing that the choice exists is the senior answer: B-trees optimise reads at the cost of writes, and if your workload is 95% writes, indexing harder is optimising the wrong side of the trade.

Related

• Index types - GIN, GiST, BRIN and when a B-tree is wrong
• Why your index is not being used - sargability and the planner
• Reading a query plan - reading the plan that proves it