B-tree fundamentals revisited with an advanced lens

Capsule description

Guide #8 taught you the "tutorial" version of B-tree: CREATE INDEX ON books(author_id); and queries with WHERE author_id = 42 become fast. Functional, enough to get started. But it leaves questions unanswered:

• Why is WHERE author_id = 42 fast but WHERE name LIKE '%tolkien' isn't, even though both use the same type of index?
• Why do you sometimes create an index and the plan still shows Seq Scan?
• What exactly does "selectivity" mean when people say "the index isn't used because the column isn't selective"?
• Why does a B-tree work for =, <, BETWEEN, ORDER BY but not for <> or LIKE '%foo'?

This capsule opens up the B-tree from the inside enough for the next capsules (composite, covering, partial, expression) to make sense as logical consequences, not memorized recipes. By the end, you'll be able to look at a query and predict whether a B-tree index will help — before creating it.

Concrete objective: you'll be able to explain to a colleague why the planner decided to ignore the index you just created, and propose at least two hypotheses of what to change (the query, the index, or the statistics).

A B-tree from the inside: a balanced ordered tree

PostgreSQL implements B-trees as balanced multi-level trees. The essential idea is the same as any dictionary or phone book:

                          [ G | M | T ]              ← root
                         /     |    |     \
                  [A..F]  [G..L] [M..S] [T..Z]       ← intermediate level
                 /  |  \   ...                         ...
            [rows] [rows] [rows]                       ← leaves (point to tuples)

Each intermediate node stores separators (the keys that divide ranges). When you search for author_id = 42:

1. You start at the root. You see separators [100, 500, 1000]. Since 42 < 100, you go down the left branch.
2. At the intermediate level, you see finer separators [10, 50, 80]. Since 42 is between 10 and 50, you go down that branch.
3. You reach a leaf. The leaf contains the keys in order and, next to each key, a TID (Tuple Identifier: a pointer to the row in the heap).
4. You read the row from the heap using the TID.

Search cost: O(log n). For 1,000,000 rows with a typical fanout of 100 entries per node, the tree has about 4 levels. It means 4 page reads to find a key, vs reading the whole table (potentially thousands of pages).

Why it matters that the leaves are ordered

The leaves of a B-tree are linked in order. This gives you three efficient operations for free:

• Equality (= 42): you go down the tree and read one leaf.
• Range (BETWEEN 10 AND 50, >= 100, < 2026-01-01): you go down to the first leaf of the range and walk the following ones in order.
• Ordering (ORDER BY author_id): the index is already ordered. You read the leaves in order and return rows without doing a separate Sort.

Why B-tree doesn't work for everything

The following patterns don't leverage a standard B-tree, even if the column is indexed:

The following capsules resolve several of these cases:

• LIKE 'tolkien%' (with a prefix): it does work with a standard B-tree (a shared prefix = going down the tree).
• LIKE '%tolkien%': needs pg_trgm with GIN — guide #14.
• lower(email): expression index — capsule 06.
• created_at::date: expression index — capsule 06.
• jsonb @> ...: GIN — guide #14.

Selectivity and cardinality: the planner's language

The terms you'll read most when someone explains why the planner ignores an index:

• Cardinality of a column: how many distinct values it has. gender with values ('M', 'F', 'O') has cardinality 3. email in a users table has cardinality almost equal to the number of rows.
• Selectivity of a predicate: what fraction of the table it returns. WHERE id = 42 returns 1 row of 1M = selectivity 0.000001 (very selective). WHERE active = true in a table where 95% are active returns 950k of 1M = selectivity 0.95 (not selective).

Intuitive rule:

• Very low selectivity (you return <5% of the table): the index probably wins.
• Medium selectivity (5-30%): it depends — a Bitmap Heap Scan may appear.
• High selectivity (>30%): the Seq Scan usually wins. Reading the whole table sequentially with cache prefetching is faster than making random jumps to the heap through the index.

That's why a column with low cardinality (active true/false, status pending/done/cancelled) often doesn't benefit from a standard B-tree index: any value covers too much of the table. The solutions for those cases are partial indexes (capsule 05) and composite indexes putting another column first (capsule 03).

How the planner knows the selectivity

PostgreSQL maintains statistics in pg_stats (populated by ANALYZE and autovacuum). For each column it stores:

• null_frac: the fraction of null values.
• n_distinct: an estimate of distinct values.
• most_common_vals and most_common_freqs: the most frequent values and their frequency.
• histogram_bounds: a histogram for the general distribution.

When the planner sees WHERE status = 'pending', it looks up 'pending' in most_common_vals. If it finds it, it uses the exact frequency. If not, it assumes a uniform distribution over the non-common values.

Practical example (see it yourself):

-- Replace 'orders' with a table of yours that has data
SELECT
  attname,
  n_distinct,
  most_common_vals,
  most_common_freqs
FROM pg_stats
WHERE tablename = 'orders'
  AND attname = 'status';

If most_common_freqs tells you that 'pending' covers 0.05 of the table, the planner estimates 50,000 rows in a 1M table — low, the index is probably used.

If it tells you 'pending' covers 0.6, the planner estimates 600,000 rows — high, a Seq Scan probably wins.

(Statistics and ANALYZE are covered in depth in module 7. Here you only need to know that they exist and that the planner relies on them.)

Worked example: same column, two indexes, opposite behaviors

You'll set up a test table, load data, create an index, and see two cases where the planner makes different decisions.

Setup

Connect to your local PostgreSQL (in psql or the client you use):

-- Create a test table
DROP TABLE IF EXISTS demo_orders;
CREATE TABLE demo_orders (
    id          BIGSERIAL PRIMARY KEY,
    customer_id INTEGER NOT NULL,
    status      TEXT NOT NULL,
    total       NUMERIC(10, 2) NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Load 500,000 rows with a skewed status:
-- 95% 'completed', 4% 'pending', 1% 'cancelled'
INSERT INTO demo_orders (customer_id, status, total, created_at)
SELECT
    (random() * 50000)::INTEGER + 1,
    CASE
        WHEN random() < 0.95 THEN 'completed'
        WHEN random() < 0.99 THEN 'pending'
        ELSE 'cancelled'
    END,
    (random() * 1000)::NUMERIC(10, 2),
    NOW() - (random() * INTERVAL '365 days')
FROM generate_series(1, 500000);

-- Refresh statistics
ANALYZE demo_orders;

Case 1: index on customer_id (high cardinality)

customer_id has 50,000 distinct values over 500,000 rows. Each value covers ~10 rows on average: very selective.

CREATE INDEX idx_demo_customer ON demo_orders(customer_id);

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

Expected output:

Index Scan using idx_demo_customer on demo_orders
  Index Cond: (customer_id = 42)
  Buffers: shared hit=12
Planning Time: 0.234 ms
Execution Time: 0.187 ms

The planner chose Index Scan. Very high selectivity favors the index.

Case 2: same index, different query — status = 'completed'

Now you try:

CREATE INDEX idx_demo_status ON demo_orders(status);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE status = 'completed';

Expected output:

Seq Scan on demo_orders
  Filter: (status = 'completed'::text)
  Rows Removed by Filter: 25000
  Buffers: shared hit=4500
Planning Time: 0.245 ms
Execution Time: 92.345 ms

The planner ignored the index. Reason: status='completed' covers 95% of the table. Reading 475,000 rows through an index (with random jumps to the heap) is more expensive than reading the 500,000 sequentially. It's the right decision.

Case 3: same column, different value — status = 'cancelled'

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM demo_orders WHERE status = 'cancelled';

Expected output:

Bitmap Heap Scan on demo_orders
  Recheck Cond: (status = 'cancelled'::text)
  Heap Blocks: exact=...
  Buffers: shared hit=...
  ->  Bitmap Index Scan on idx_demo_status
        Index Cond: (status = 'cancelled'::text)
Planning Time: 0.234 ms
Execution Time: 8.412 ms

Now it does use the index (via Bitmap Index Scan). Reason: cancelled is 1% of the table — selective. The planner consulted most_common_freqs, saw that cancelled is rare, and chose to use the index.

Key point: the same index on the same column is used or not used depending on the exact value of the predicate. The planner is value-aware.

When the planner ignores a "perfectly valid" index

A list of common causes — worth memorizing:

1. High predicate selectivity

Already covered above. If WHERE x = $val returns >30% of the table, Seq Scan usually wins.

How to verify:

EXPLAIN (ANALYZE)
SELECT * FROM table WHERE column = 'value';

Look at the node's actual rows. If it's a large fraction of the table, the planner is being reasonable.

2. Stale statistics

If you inserted a lot of data recently and didn't run ANALYZE, the planner thinks the table has the old distribution. A decision based on outdated information.

How to verify:

SELECT
  schemaname, relname,
  last_analyze, last_autoanalyze,
  n_live_tup, n_dead_tup
FROM pg_stat_user_tables
WHERE relname = 'your_table';

If last_analyze and last_autoanalyze are old, run ANALYZE your_table;.

3. Small table

For tables with fewer than ~1000 rows, the planner almost always prefers Seq Scan. Loading the index and making jumps to the heap costs more than reading the whole table.

Symptom: you work locally with 100 rows, everything is Seq Scan. You insert 100k rows with a seed script and suddenly the planner starts using the index. Normal.

4. Function or cast on the WHERE column

WHERE lower(email) = 'foo@bar.com'   -- index on email does NOT work
WHERE created_at::date = '2026-05-01'  -- index on created_at does NOT work
WHERE id::TEXT = '42'                  -- index on id does NOT work

The function wraps the column and breaks the match. Solution: an expression index (capsule 06) or rewriting the query (WHERE created_at >= '2026-05-01' AND created_at < '2026-05-02' instead of a cast).

5. Type mismatch

-- The user_id column is BIGINT
WHERE user_id = '42'  -- string, not integer

Some drivers/ORMs do implicit casts. If the cast is explicit or the parameter's type doesn't match, the index usage can break. Verify that your driver passes the right type.

6. Operator not compatible with B-tree

WHERE column <> 'value'            -- "not equal to"
WHERE column LIKE '%something'     -- suffix
WHERE column IS NOT NULL           -- (sometimes yes, sometimes no)
WHERE arr_col @> ARRAY['x']        -- array containment

B-tree doesn't support these operators efficiently. For some, there are other index types (GIN, GiST, BRIN). For <>, there's almost never an efficient index.

7. OR over different columns without a combined index

WHERE author_id = 42 OR isbn = 'XYZ'

With separate indexes on author_id and isbn, the planner can use BitmapOr (combines bitmaps). Sometimes it decides it's more expensive and goes to Seq Scan. Solutions: a composite index, or UNION instead of OR.

8. PostgreSQL version or configuration

random_page_cost (default 4 on magnetic disks, 1.1 recommended on SSD) affects when the planner prefers index vs sequential. If your database runs on SSD but has random_page_cost = 4, the planner underestimates the index.

SHOW random_page_cost;

If it's at 4 and you run on SSD, consider lowering it to 1.1 globally.

Why does this matter in real work?

1. You avoid the "create index, doesn't work, create another" cycle.

Without understanding the fundamentals, you go guessing. With the fundamentals, you look at the query, look at pg_stats, look at the plan, and propose an index with reasonable confidence that it'll be used.

2. You defend your technical decisions.

In a serious PR review, someone will ask "why this index?". "Because the query needed it" is a junior answer. "Because the cardinality of status is 4 and the real selectivity of 'pending' is 5%, so a partial index on that value wins over a full one, and I validated with EXPLAIN that it's used" is a senior answer.

3. You negotiate with the planner without fighting it.

Sometimes the planner ignores your index and the solution isn't to force it (with enable_seqscan = off, an anti-pattern), it's to understand why it ignores it and fix the real cause (statistics, a rewritten query, a partial index).

Traps and common mistakes

Mistake 1 (conceptual): assuming that the index exists = the index is used

Symptom: "I added an index and it's still slow."

Why it happens: the planner decides. Creating the index enables its use, it doesn't guarantee it.

How to detect: capture the plan with EXPLAIN (ANALYZE). If you see Seq Scan, the index isn't being used.

How to fix it: review the list of causes above. If it's none of the obvious ones, look at the statistics with pg_stats and check the predicate's real selectivity.

Mistake 2 (conceptual): forcing the planner with SET enable_seqscan = off

Symptom: someone on Stack Overflow recommends SET enable_seqscan = off to "force" using the index.

Why it's wrong: it's a patch. If the planner prefers Seq Scan, it's usually right. Forcing an Index Scan can be worse in real performance. And if it works, it's a sign of a deeper problem (statistics, configuration, a poorly designed index) that you're papering over.

How to fix it: use it only for diagnosis ("how much does the alternative plan cost?"), never as a permanent solution. To adjust the costing, use random_page_cost or effective_cache_size.

Mistake 3 (practical): indexing columns with very low cardinality without thinking

Symptom: you create CREATE INDEX ON users(active); and it's never used.

Why it happens: active has cardinality 2 (true/false). Any value covers a large percentage of the table. The planner almost always prefers Seq Scan.

How to fix it: either don't index boolean columns (they don't help), or use a partial index on the minority value (capsule 05): CREATE INDEX ON users(id) WHERE active = false; if the inactive ones are 5%.

Mistake 4 (conceptual): confusing a usable B-tree with an efficient one

Symptom: the plan shows Index Scan, you assume it's optimized.

Why it's sometimes wrong: an Index Scan can bring back 100,000 candidates and then discard 95% via Filter. That's inefficient — the index only partially covers the query.

How to detect: look at Rows Removed by Filter. If it's high vs actual rows, the index is covering only part of the predicate. You need a composite (capsule 03) or partial (capsule 05).

Mistake 5 (conceptual): assuming an "old" index doesn't need review

Symptom: "That index has been there since 2024, it must be fine."

Why it happens: the app's queries change. Refactors, new features, added columns. An index that was optimal six months ago may be getting ignored today.

How to fix it: periodically review pg_stat_user_indexes (capsule 07). If idx_scan = 0 after months, the index is only slowing down writes and consuming disk.

Exercises

Exercise 1: predict index usage based on selectivity

You have a users table with 1,000,000 rows. For each of these predicates, predict whether the planner will probably use a B-tree index on the corresponding column. Justify.

1. WHERE id = 12345 (on the PK)
2. WHERE active = true (95% are active)
3. WHERE country = 'AR' (15% are Argentine out of 200 countries)
4. WHERE email = 'user@example.com'
5. WHERE registered_at >= '2026-01-01' (5% registered in that range)
6. WHERE registered_at >= '2020-01-01' (95% registered since that year)

Exercise 2: diagnose an ignored index

You created an index and the plan still shows Seq Scan. List at least 5 possible causes to investigate, in order of probability.

Exercise 3: investigate real selectivity with pg_stats

Take a table of yours (or use the demo_orders from the worked example). Run:

SELECT
  attname,
  null_frac,
  n_distinct,
  most_common_vals,
  most_common_freqs
FROM pg_stats
WHERE tablename = 'demo_orders';

For three different columns, write one sentence about each: "this column has cardinality X and its most frequent value covers Y% of the table, so a standard B-tree index [would be used / would not be used / depends on the value]."

SELECT attname, n_distinct, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'demo_orders';

Exercise 4: distinguish B-tree-friendly queries from ones that aren't

Mark each query as B-tree uses or B-tree does NOT use (assuming an index on the predicate's column and reasonable selectivity).

1. SELECT * FROM books WHERE title = 'The Lord of the Rings'
2. SELECT * FROM books WHERE title LIKE 'The Lord%'
3. SELECT * FROM books WHERE title LIKE '%Rings'
4. SELECT * FROM books WHERE published_year BETWEEN 1950 AND 1960
5. SELECT * FROM books WHERE published_year <> 2000
6. SELECT * FROM books WHERE lower(title) = 'the hobbit'
7. SELECT * FROM books WHERE id IN (1, 2, 3, 4, 5)
8. SELECT * FROM books WHERE author_id IS NULL
9. SELECT * FROM books ORDER BY published_year DESC LIMIT 10 (assuming an index on published_year)
10. SELECT * FROM books WHERE jsonb_metadata @> '{"genre": "fantasy"}'

Exercise 5: experiment with small vs large tables

In your local PostgreSQL:

1. Create a tiny table with 100 rows.
2. Create an index on any column.
3. Capture the plan of a SELECT that filters by that column.
4. Insert 100,000 more rows into the same table.
5. Run ANALYZE.
6. Capture the plan of the same query.
7. Compare and comment.

-- Step 1-2
CREATE TABLE tiny (id SERIAL PRIMARY KEY, code TEXT);
INSERT INTO tiny (code) SELECT md5(random()::text) FROM generate_series(1, 100);
CREATE INDEX idx_tiny_code ON tiny(code);
ANALYZE tiny;

-- Step 3
EXPLAIN (ANALYZE) SELECT * FROM tiny WHERE code = 'some_code';

Seq Scan on tiny  (cost=0.00..2.25 rows=1 width=37) (actual time=0.020..0.023 rows=0 loops=1)
  Filter: (code = 'some_code'::text)
  Rows Removed by Filter: 100

-- Step 4-5
INSERT INTO tiny (code) SELECT md5(random()::text) FROM generate_series(1, 100000);
ANALYZE tiny;

-- Step 6
EXPLAIN (ANALYZE) SELECT * FROM tiny WHERE code = 'some_real_code';

Index Scan using idx_tiny_code on tiny  (cost=0.42..8.44 rows=1 width=37) (actual time=0.045..0.048 rows=0 loops=1)
  Index Cond: (code = 'some_real_code'::text)

Summary and next step

In this capsule you learned:

• A B-tree is a balanced ordered tree with linked leaves. It allows efficient equality, range, and ordering in O(log n).
• B-tree does NOT work for suffix (LIKE '%foo'), <>, functions on the column (lower(x) = ...), or non-B-tree operators (@>, FTS).
• Selectivity is the fraction of the table a predicate returns. Cardinality is how many distinct values a column has.
• The planner knows the distribution thanks to pg_stats, populated by ANALYZE and autovacuum. It decides whether to use the index or not based on the predicate's estimated selectivity with the specific value.
• The planner can ignore a "perfectly valid" index due to: high selectivity, stale statistics, a small table, a function wrapping the column, a type mismatch, an incompatible operator, configuration (random_page_cost).
• Creating the index doesn't guarantee it's used. You always validate with EXPLAIN (ANALYZE).

Before moving on, you should be able to:

• Explain why WHERE name LIKE '%tolkien' doesn't leverage a standard B-tree index.
• Predict, given a column and a value, whether the planner will probably use an index (based on selectivity).
• List at least 4 causes for the planner ignoring a valid index.
• Query pg_stats to see the cardinality and most common values of a column.

Next capsule — Composite indexes: order and selectivity. You now know when a simple index wins or loses. The next capsule raises the stakes: queries with multiple filters (WHERE a = X AND b = Y). Two separate indexes, or one composite? In what order should the columns go? You'll learn the leftmost prefix rule (the most misunderstood rule of indexing) and design composites the planner actually uses.

Resources

1. Markus Winand — Use The Index, Luke! — "Anatomy of an Index" — the best visual explanation of how a B-tree is structured, with diagrams. Required reading.
2. PostgreSQL Documentation — Index Types — the official chapter on index types in PostgreSQL 16.
3. PostgreSQL Documentation — Statistics Used by the Planner — how the planner uses pg_stats to make decisions.
4. Hubert "depesz" Lubaczewski — "Index Scan vs Seq Scan" — real cases with before/after plans.
5. Bruce Momjian — "Inside the PostgreSQL Query Optimizer" (slides) — from the core team. Covers how the planner decides between alternative plans.
6. PostgreSQL Wiki — Slow Query Questions — the official checklist of what information to include when you report a slow query. Useful as a reminder of what to look at.
7. Tom Lane on planner cost constants — the canonical explanation of random_page_cost vs seq_page_cost and when to adjust them.

Module 3 — Database Performance & Query Tuning Guide