Database Indexing Explained: How B-Tree Indexes Really Speed Up Your Queries

Most slow PostgreSQL queries I'm asked to look at share one root cause: the database reads far more data than the query needs. A request that returns 20 rows scans 10 million, or an index exists but the planner can't use it. Meanwhile, the same tables carry a dozen indexes that tax every write while half of them sit unused.

In this post I'll open up the B-tree behind almost every CREATE INDEX, then use a realistic orders table and EXPLAIN (ANALYZE, BUFFERS) to show composite, covering, partial, and expression indexes at work. I'll also cover why the planner ignores some indexes, what they cost on writes, and how I manage them in production.

What an index is and why full table scans hurt#

A PostgreSQL table, the heap, is a file of 8 KB pages, and new rows go wherever there's free space. Nothing in that layout tells Postgres where customer 42's orders live, so answering WHERE customer_id = 42 without an index means reading every page and testing every row. That's a sequential scan, and its cost grows with the table, not the result: fetching 97 rows from the 10-million-row table below reads about 650 MB.

An index keeps column values in sorted order, each paired with a TID (tuple identifier) pointing to the row's heap page and slot. Postgres searches the index, collects TIDs, and reads only the heap pages holding matches, like using the index at the back of a book. The catch: it's a second copy of part of your data, updated on every write, so it should exist only where queries earn it back.

How a B-tree index works#

CREATE INDEX builds a B-tree by default: it handles equality, ranges, and sorting, which covers most application queries.

Pages, fan-out, and O(log n) lookups#

A B-tree is also built from 8 KB pages. Leaf pages hold the entries (a key plus a TID); internal pages hold separator keys pointing to child pages, up to a single root. A lookup walks down from the root, following the child whose key range covers the search value. Since a page holds a few hundred bigint keys, each level multiplies capacity by a few hundred:

That's O(log n) with a huge base. My 10-million-row table's indexes are 3 levels deep, so a lookup reads 3 index pages plus a heap page, and the upper levels stay cached because every lookup passes through them. Full pages split and push a separator into their parent, keeping every leaf at the same depth.

Why the sorted leaf level matters#

Leaf pages link to their neighbors, and the whole leaf level is in key order. For a range, Postgres descends once to the first match and walks sideways until it passes the upper bound, which is why one B-tree handles =, <, <=, >=, >, BETWEEN, IN, and IS NULL.

The same ordering makes sorting nearly free: ORDER BY created_at LIMIT 10 on an indexed column reads 10 entries and stops. Leaves can be walked in either direction, so an ascending index serves DESC too.

Reading EXPLAIN output on a real table#

EXPLAIN shows the chosen plan, ANALYZE runs the query and reports what actually happened, and BUFFERS adds how many 8 KB pages each step touched. I trust page counts over timings, which swing with cache state.

The orders table#

Here's the table for the rest of the post: 10 million orders from about 100,000 customers, inserted in time order over roughly two years.

CREATE TABLE orders (
    id          bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer_id bigint      NOT NULL,
    status      text        NOT NULL,
    total_cents integer     NOT NULL,
    created_at  timestamptz NOT NULL
);
 
INSERT INTO orders (customer_id, status, total_cents, created_at)
SELECT
    1 + floor(random() * 100000)::bigint,
    CASE
        WHEN g % 100 = 0 THEN 'pending'    -- 1%
        WHEN g % 20 = 0  THEN 'cancelled'  -- 4%
        ELSE 'delivered'                   -- 95%
    END,
    100 + floor(random() * 50000)::int,
    timestamptz '2024-01-01' + g * interval '6 seconds'
FROM generate_series(1, 10000000) AS g;
 
VACUUM ANALYZE orders;
 
-- Keep plans readable: parallel workers split a Seq Scan
-- across processes, but every page still gets read.
SET max_parallel_workers_per_gather = 0;

Plans below use the PostgreSQL 16/17 output format, lightly trimmed (18 adds a few details), and timings are illustrative.

The four scan types#

Each node shows estimates (cost, rows, width), then measurements (actual time in milliseconds, rows, loops). shared hit counts pages found in PostgreSQL's buffer cache; read counts pages fetched from the OS. If estimated and actual rows differ by 10x or more, suspect statistics.

Before and after the first index#

Here's every order for one customer:

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 42;

Seq Scan on orders  (cost=0.00..208334.00 rows=101 width=38) (actual time=7.912..857.304 rows=97 loops=1)
  Filter: (customer_id = 42)
  Rows Removed by Filter: 9999903
  Buffers: shared hit=2208 read=81126
Planning Time: 0.094 ms
Execution Time: 857.352 ms

Postgres read all 83,334 heap pages and discarded 9,999,903 rows to return 97. Now add an index:

CREATE INDEX orders_customer_id_idx ON orders (customer_id);

Bitmap Heap Scan on orders  (cost=5.22..399.93 rows=101 width=38) (actual time=0.049..0.276 rows=97 loops=1)
  Recheck Cond: (customer_id = 42)
  Heap Blocks: exact=97
  Buffers: shared hit=100
  ->  Bitmap Index Scan on orders_customer_id_idx  (cost=0.00..5.19 rows=101 width=0) (actual time=0.031..0.031 rows=97 loops=1)
        Index Cond: (customer_id = 42)
        Buffers: shared hit=3
Planning Time: 0.187 ms
Execution Time: 0.305 ms

That's 100 pages instead of 83,334: three index pages (root, internal, leaf) plus 97 heap pages. Because customer 42's orders are scattered across the table, the planner chose a bitmap scan: it collects every TID first, then reads each heap page once in physical order instead of hopping around. Recheck Cond only matters if the bitmap outgrows work_mem and turns lossy, which Heap Blocks: exact=97 rules out.

Designing indexes that match your queries#

Composite indexes and column order#

An index on (customer_id, created_at) is sorted by customer_id, then by created_at within each customer, like a phone book sorted by last name, then first name. Three rules follow.

Leftmost prefix. The index serves conditions on customer_id or on both columns, but not on created_at alone, whose matches are spread across the whole index. PostgreSQL 18's skip scan softens this for low-cardinality leading columns, but I don't design around it.

Equality before range. For WHERE customer_id = 42 AND created_at >= '2025-01-01', putting the equality column first keeps every match in one contiguous run. Reverse the columns and Postgres walks every order since January, for all customers:

(customer_id, created_at)              (created_at, customer_id)
(41, 2025-08-30 10:12)                 (2025-01-01 00:00:06, 58213)
(42, 2024-03-11 09:45)                 (2025-01-01 00:00:12, 42)     match
(42, 2025-01-04 18:20)  first match    (2025-01-01 00:00:18, 7730)
(42, 2025-06-19 07:02)  match          (2025-01-01 00:00:24, 91004)
(42, 2025-11-02 21:37)  last match     ...every order since January...
(43, 2024-01-15 13:05)                 (2025-11-24 23:59:48, 42)     match

Sort order. Entries come out in key order, so WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20 shouldn't need a sort. With only the single-column index, it does:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status, total_cents, created_at
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Limit  (cost=402.62..402.67 rows=20 width=30) (actual time=0.301..0.305 rows=20 loops=1)
  Buffers: shared hit=100
  ->  Sort  (cost=402.62..402.87 rows=101 width=30) (actual time=0.300..0.302 rows=20 loops=1)
        Sort Key: created_at DESC
        Sort Method: top-N heapsort  Memory: 27kB
        Buffers: shared hit=100
        ->  Bitmap Heap Scan on orders  (cost=5.22..399.93 rows=101 width=30) (actual time=0.048..0.271 rows=97 loops=1)
              Recheck Cond: (customer_id = 42)
              Heap Blocks: exact=97
              Buffers: shared hit=100
              ->  Bitmap Index Scan on orders_customer_id_idx  (cost=0.00..5.19 rows=101 width=0) (actual time=0.030..0.030 rows=97 loops=1)
                    Index Cond: (customer_id = 42)
                    Buffers: shared hit=3
Planning Time: 0.162 ms
Execution Time: 0.329 ms

With a composite index, Postgres jumps to the end of customer 42's range, walks backward, and stops after 20 rows:

CREATE INDEX orders_customer_created_idx ON orders (customer_id, created_at);

Limit  (cost=0.43..81.58 rows=20 width=30) (actual time=0.024..0.063 rows=20 loops=1)
  Buffers: shared hit=24
  ->  Index Scan Backward using orders_customer_created_idx on orders  (cost=0.43..410.20 rows=101 width=30) (actual time=0.023..0.060 rows=20 loops=1)
        Index Cond: (customer_id = 42)
        Buffers: shared hit=24
Planning Time: 0.171 ms
Execution Time: 0.079 ms

That's 24 pages instead of 100, and no sort. For a customer with 50,000 orders, the first plan would fetch and sort all 50,000 rows; the second still reads about 24 pages. Mixed directions across customers, like ORDER BY customer_id, created_at DESC, need a matching declaration: (customer_id, created_at DESC).

Covering indexes with INCLUDE#

That plan still visited 20 heap pages. When an index holds every column a query touches, Postgres can run an Index Only Scan and skip the heap. INCLUDE adds payload columns stored only in the leaf pages. Say an order-history widget needs only dates and totals:

CREATE INDEX orders_customer_created_total_idx
    ON orders (customer_id, created_at) INCLUDE (total_cents);
 
EXPLAIN (ANALYZE, BUFFERS)
SELECT created_at, total_cents
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

Limit  (cost=0.43..1.58 rows=20 width=12) (actual time=0.019..0.024 rows=20 loops=1)
  Buffers: shared hit=3
  ->  Index Only Scan Backward using orders_customer_created_total_idx on orders  (cost=0.43..6.20 rows=101 width=12) (actual time=0.018..0.021 rows=20 loops=1)
        Index Cond: (customer_id = 42)
        Heap Fetches: 0
        Buffers: shared hit=3
Planning Time: 0.158 ms
Execution Time: 0.037 ms

Three pages, no heap visits. The catch is that row visibility lives in the heap, so Postgres can skip only pages the visibility map marks as all-visible, and VACUUM sets those bits. I vacuumed after loading, hence Heap Fetches: 0; on a write-heavy table that number climbs and the advantage shrinks.

Included columns don't affect ordering or uniqueness and stay out of the tree's upper levels, but you can't search or sort by them. In a real schema I'd replace orders_customer_created_idx with this index rather than keep both.

Partial indexes#

A partial index only contains rows matching its WHERE clause. A job that retries stuck pending orders only ever reads 1% of the table, so there's no reason to index the rest:

CREATE INDEX orders_pending_created_idx
    ON orders (created_at)
    WHERE status = 'pending';
 
SELECT id, customer_id, created_at
FROM orders
WHERE status = 'pending'
  AND created_at < now() - interval '1 day'
ORDER BY created_at
LIMIT 100;

It's about 1% of the size of a full index on created_at, and inserting a delivered order never touches it. The planner uses it only when it can prove the query implies the index predicate, so status = 'pending' must appear in the query; status = $1 under a generic prepared-statement plan won't match. Partial unique indexes are the other classic use: CREATE UNIQUE INDEX ON users (email) WHERE deleted_at IS NULL.

Expression indexes#

An index on email can't serve WHERE lower(email) = $1, because it stores email, not lower(email). Index the expression instead, which here also enforces case-insensitive uniqueness:

CREATE UNIQUE INDEX users_email_lower_key ON users (lower(email));
 
SELECT id, email FROM users WHERE lower(email) = lower('Ada@Example.com');

The query must use exactly the same expression, and the expression must be immutable: created_at::date on a timestamptz column isn't, because it depends on the session time zone. Run ANALYZE afterward too, since Postgres keeps separate statistics for indexed expressions.

Why the planner ignores your index#

The planner is cost-based: it estimates the rows each step returns, converts them into page reads and CPU work, and picks the cheapest plan. By default it prices a random heap read at four times a sequential one (random_page_cost = 4, seq_page_cost = 1), so once a query matches a large enough share of the table, a sequential scan wins, usually correctly.

Those estimates rest on selectivity (the fraction of rows a condition matches) and cardinality (the number of distinct values). Here's what the planner knows about status:

SELECT attname, n_distinct, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';

 attname | n_distinct |       most_common_vals        |       most_common_freqs
---------+------------+-------------------------------+--------------------------------
 status  |          3 | {delivered,cancelled,pending} | {0.9504667,0.039633334,0.0099}

With an index on status, status = 'delivered' is estimated at 9.5 million rows and correctly gets a sequential scan, while status = 'pending' (about 99,000 rows) gets an index-based plan. When the planner skips an index you expected it to use, look for:

• Stale statistics. ANALYZE samples 30,000 rows by default, and autovacuum only re-analyzes after about 10% of a table changes, so run it yourself after bulk loads and backfills.
• Skewed or correlated data. Raise a column's sample with ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000, and use CREATE STATISTICS for columns that move together, like city and postal code.
• A query the index can't serve as written. See the mistakes below.
• A tiny table. Scanning 20 pages beats any index.

Indexes in production#

What every index costs on writes#

Every INSERT adds an entry to every index (partial indexes skip non-matching rows), so a table with eight indexes turns one insert into nine modifications, each writing WAL and sometimes splitting a page.

Updates are worse. PostgreSQL writes a new row version on every update, and normally every index gets a new entry, even indexes on untouched columns. The exception is a HOT (heap-only tuple) update: if no indexed column changed and the new version fits on the same page, Postgres chains it to the old version and skips the indexes entirely. Index a frequently updated column like updated_at, and those updates stop being HOT. On update-heavy tables, leave room on each page with ALTER TABLE orders SET (fillfactor = 90), and watch the ratio:

SELECT relname,
       n_tup_upd,
       n_tup_hot_upd,
       round(100.0 * n_tup_hot_upd / nullif(n_tup_upd, 0), 1) AS hot_pct
FROM pg_stat_user_tables
ORDER BY n_tup_upd DESC
LIMIT 10;

Building indexes without blocking writes#

A plain CREATE INDEX blocks INSERT, UPDATE, and DELETE for the entire build, which on a large table means minutes of stalled writes. CREATE INDEX CONCURRENTLY lets writes continue. The price is two table scans and waiting for in-flight transactions, so it's slower, and a long-running or idle-in-transaction session can stall it.

-- CONCURRENTLY cannot run inside a transaction block,
-- so this migration must opt out of the tool's wrapping transaction.
CREATE INDEX CONCURRENTLY orders_customer_created_idx
    ON orders (customer_id, created_at);

Most migration tools wrap each migration in a transaction, so opt out for this one (disable_ddl_transaction! in Rails, atomic = False in Django), and follow progress in pg_stat_progress_create_index.

Finding unused and duplicate indexes#

pg_stat_user_indexes counts scans per index, so zero-scan indexes, largest first, are the first candidates to drop:

SELECT s.relname                                      AS table_name,
       s.indexrelname                                 AS index_name,
       s.idx_scan,
       s.last_idx_scan,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS index_size
FROM pg_stat_user_indexes AS s
JOIN pg_index AS i ON i.indexrelid = s.indexrelid
WHERE s.idx_scan = 0
  AND NOT i.indisunique
ORDER BY pg_relation_size(s.indexrelid) DESC;

Unique indexes are excluded because they enforce constraints even when nothing reads them, and last_idx_scan needs PostgreSQL 16 or later. Grouping pg_index by definition finds exact duplicates:

SELECT indrelid::regclass              AS table_name,
       array_agg(indexrelid::regclass) AS duplicate_indexes
FROM pg_index
GROUP BY indrelid, indkey::text, indclass::text, indcollation::text, indoption::text,
         coalesce(indexprs::text, ''), coalesce(indpred::text, '')
HAVING count(*) > 1;

Redundant prefixes are subtler. Once (customer_id, created_at) exists, an index on (customer_id) alone is usually dead weight, but because it's smaller, the planner may keep using it, so it never looks unused. Drop it deliberately and recheck your plans.

Common indexing mistakes#

Functions or casts on the column. An index on created_at doesn't store created_at::date, so a condition on the converted value can't use it. Rewrite it as a range:

-- Can't use an index on created_at
SELECT count(*) FROM orders WHERE created_at::date = '2025-06-01';
 
-- Same rows, and a plain index range scan
SELECT count(*) FROM orders
WHERE created_at >= '2025-06-01' AND created_at < '2025-06-02';

Leading wildcards. LIKE 'ada%' maps to a range of the sorted index, so a B-tree can serve it if the index uses text_pattern_ops or the column uses the C collation. LIKE '%@example.com' could match anywhere, so use a trigram index from pg_trgm instead:

CREATE INDEX users_email_prefix_idx ON users (email text_pattern_ops);
 
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX users_email_trgm_idx ON users USING gin (email gin_trgm_ops);

Type mismatches. Compare a bigint column with a numeric value and Postgres casts the column, which rules out the index:

EXPLAIN SELECT * FROM orders WHERE customer_id = 42.0;

Seq Scan on orders  (cost=0.00..233334.00 rows=50000 width=38)
  Filter: ((customer_id)::numeric = 42.0)

The column-side cast in Filter is the giveaway, and rows=50000 is a default guess because there are no statistics for the cast expression. The usual culprit is a driver binding a parameter as numeric, such as a Java BigDecimal. customer_id = 42 is fine: cross-type integer comparisons are built into the B-tree operator family.

OR across columns. WHERE customer_id = 42 OR total_cents = 12345 needs an index on both sides. Without one on total_cents, any row could match, so Postgres scans the table. With both indexed, it can combine two bitmap scans with a BitmapOr, or you can rewrite the query as a UNION.

Low-selectivity columns. A B-tree on a 50/50 boolean like is_archived will almost never be used, because reading half a table through an index is slower than scanning it. If you only query the rare value, use a partial index instead.

Over-indexing. Every index slows writes, competes for cache, and adds vacuum work. I add one only when a real query from pg_stat_statements or the slow query log justifies it, verify it with EXPLAIN, and check later that it's actually scanned.

Key takeaways#

• A B-tree turns "read every page" into "read a handful of pages", and its sorted leaves make ranges and ORDER BY ... LIMIT cheap.
• Judge plans with EXPLAIN (ANALYZE, BUFFERS): compare estimated to actual rows, and count pages, not milliseconds.
• In composite indexes, put equality columns before range and sort columns; the leftmost prefix decides which queries can use them.
• INCLUDE, partial, and expression indexes are smaller and more targeted, but only help when queries match their definition.
• Every index taxes writes and can block HOT updates, so build with CREATE INDEX CONCURRENTLY and prune what pg_stat_user_indexes shows is unused.

Never add an index on faith. Run EXPLAIN (ANALYZE, BUFFERS), add the index, run it again, and compare the pages touched; if the numbers don't move, the index is only costing you writes. For more depth, the PostgreSQL docs on indexes and using EXPLAIN are the best next read.