How a B-tree index works in PostgreSQL Basic

The problem

A table btree_demo has 100,000 rows: sequence_no integer PRIMARY KEY, passenger_name text. Three queries look similar:

SELECT sequence_no, passenger_name FROM btree_demo WHERE sequence_no = 42000;
SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE 'passenger-4200%';
SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE '%9999';

Query	Result
sequence_no = 42000	Uses the index, fast
LIKE 'passenger-4200%'	Even though passenger_name is indexed, it still scans the whole table, about 350x slower
LIKE '%9999'	A regular B-tree cannot help, even after the fix; you need GIN with pg_trgm, or an index on reverse()

The 350x figure compares two different queries, so it only shows the plan difference; it is not a fair benchmark.

This article runs all three on a real PostgreSQL 17 and reads the real plans, to answer precisely “what an index can and cannot do”.

Core concepts

CREATE INDEX without USING creates a B-tree, the default and most common index type. It is a balanced multi-way tree: each node (one 8 kB page) holds hundreds of keys and points to hundreds of children, so the tree is very shallow.

The index on 100,000 rows in the demo below takes only:

     relname     | index_pages | index_size
-----------------+-------------+------------
 btree_demo_pkey |         276 | 2208 kB

276 pages (8kB each) for 100,000 keys, an average of about 362 keys per page. This demo index has only 2 levels: bt_metap() (from the pageinspect extension) reports the root at level 1, meaning the root points straight to the leaves.

When the number of leaves exceeds the pointers one root can hold (a few hundred), PostgreSQL adds an internal level. With this fan-out, the tree stays at 3 levels even with millions of rows. That is why B-tree lookups barely slow down when the table grows 10x.

The structure has three page types:

Page type	Contains	Role
Root	Separator keys + pointers to the level below	Starting point of every lookup
Internal	Separator keys + pointers	Narrows the search range
Leaf	Real keys + TIDs (block, item) pointing into the heap	Where rows are found; leaves are linked in order

Finding sequence_no = 42000: root → leaf → heap is 3 buffers, then walk sideways across leaves

Enlarge diagram

Root page → Leaf pagewhich leaf has 42000?

◀ Prev▶ PlayNext ▶↺ RestartStep 1/4

Buffer 1: compare 42000 with the separator keys in the root and follow the pointer down to the right leaf. The demo tree has only 2 levels, so the root points straight to the leaf.

Because leaves form a chain, once the start point is found PostgreSQL walks sideways through a range of values without going back to the root. That is why range scans and ORDER BY are cheap.

The most important and most misunderstood point: a B-tree compares values with the operators <, <=, =, >=, >. It does not “search for substrings”; that is the job of the LIKE operator, and not every use of LIKE translates into a comparison the B-tree understands.

How it works

1. Equality: find exactly one row

Index Scan using btree_demo_pkey on btree_demo  (cost=0.29..8.31 rows=1 width=19) (actual time=0.004..0.004 rows=1 loops=1)
  Index Cond: (sequence_no = 42000)
  Buffers: local hit=3
Execution Time: 0.008 ms

sequence_no = 42000 translates directly into an = comparison. PostgreSQL walks from root to leaf following separator keys, touching only 3 pages, in 0.008 ms.

2. Range + ORDER BY: no separate Sort

SELECT sequence_no FROM btree_demo
WHERE sequence_no BETWEEN 42000 AND 42009
ORDER BY sequence_no;

Index Only Scan using btree_demo_pkey on btree_demo  (cost=0.29..4.47 rows=9 width=4) (actual time=0.007..0.007 rows=10 loops=1)
  Index Cond: ((sequence_no >= 42000) AND (sequence_no <= 42009))
  Heap Fetches: 0
  Buffers: local hit=3

BETWEEN translates into >= and <=, still operators the B-tree understands. Because leaf pages are already ordered, PostgreSQL reads 10 consecutive entries without a separate Sort step for ORDER BY sequence_no.

Heap Fetches: 0 confirms the query never went back to the table, because SELECT sequence_no only needs the column already in the index. The condition: the visibility map must mark the pages all-visible, meaning the table has been VACUUMed (vacuum and bloat).

On a table with heavy recent writes, Heap Fetches will be large.

Change SELECT sequence_no to SELECT * with the same condition:

Index Scan using btree_demo_pkey on btree_demo  (cost=0.29..8.47 rows=9 width=19) (actual time=0.003..0.003 rows=10 loops=1)
  Index Cond: ((sequence_no >= 42000) AND (sequence_no <= 42009))
  Buffers: local hit=3

The node name changes from Index Only Scan to Index Scan: passenger_name is not in the index, so PostgreSQL has to go back to the heap for it.

Buffers stay at 3 because the data is cached; on a much larger table, this trip back to the heap is where the real I/O cost lies.

3. Prefix LIKE: Seq Scan despite the index, why?

Add an index on passenger_name, then run:

SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE 'passenger-4200%';

Seq Scan on btree_demo  (cost=0.00..1887.00 rows=10 width=4) (actual time=0.127..2.797 rows=11 loops=1)
  Filter: (passenger_name ~~ 'passenger-4200%'::text)
  Rows Removed by Filter: 99989
  Buffers: local hit=637
Execution Time: 2.799 ms

The index exists, yet it is still a Seq Scan, reading 637 pages and discarding 99,989 rows to return 11. PostgreSQL did not “forget” the index; the cause is the database collation:

 datcollate
------------
 en_US.utf8

With a locale other than C, PostgreSQL cannot be sure that the locale’s sort order matches the byte order needed to use a B-tree for prefix comparison. This is not rare: most production databases do not use the C locale.

The fix: create an index with the text_pattern_ops operator class, which compares bytes instead of locale order:

CREATE INDEX btree_demo_name_pattern_idx ON btree_demo (passenger_name text_pattern_ops);

Rerun the same query:

Index Scan using btree_demo_name_pattern_idx on btree_demo  (cost=0.42..8.44 rows=10 width=4) (actual time=0.030..0.034 rows=11 loops=1)
  Index Cond: ((passenger_name ~>=~ 'passenger-4200'::text) AND (passenger_name ~<~ 'passenger-4201'::text))
  Filter: (passenger_name ~~ 'passenger-4200%'::text)
  Buffers: local hit=2 read=3
Execution Time: 0.048 ms

2.799 ms → 0.048 ms: about 58x faster, 637 buffers → 5 buffers. PostgreSQL translates LIKE 'passenger-4200%' into the byte range >= 'passenger-4200' AND < 'passenger-4201', a range that a text_pattern_ops B-tree understands and can locate directly.

Same LIKE 'passenger-4200%'	Plan	Time	Buffers
Default index (en_US.utf8)	Seq Scan	2.799 ms	637
text_pattern_ops	Index Scan	0.048 ms	5

A text_pattern_ops index has a cost: it compares bytes, so it does not serve <, > or ORDER BY in locale order. If you need both kinds of query, keep two indexes, or create one index with COLLATE "C". For varchar columns, use varchar_pattern_ops.

4. LIKE starting with %: a regular B-tree cannot help

SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE '%9999';

Seq Scan on btree_demo  (cost=0.00..1887.00 rows=10 width=4) (actual time=0.322..3.313 rows=10 loops=1)
  Filter: (passenger_name ~~ '%9999'::text)
  Rows Removed by Filter: 99990
  Buffers: local hit=637

Even with the text_pattern_ops index from the previous step, this is still a Seq Scan. The reason is entirely different: %9999 has no fixed prefix to translate into a comparison range; a match can start with any character.

A B-tree locates entries by ordered comparison; an “ends with X” condition cannot narrow the start position in the tree. A B-tree directly on the column cannot solve this. There are two options:

• GIN with pg_trgm: also supports LIKE '%x%'.
• Expression index on reverse() (for “ends with” only): create an index on (reverse(passenger_name) text_pattern_ops) and rewrite the query as WHERE reverse(passenger_name) LIKE reverse('%9999') (i.e. '9999%' on the reversed string). The B-tree becomes usable again.

Lookup table: which operators can use a B-tree?

Condition	Regular B-tree usable?	Notes
col = x, col IN (...)	Yes
col < x, >, BETWEEN, ORDER BY col	Yes	Keeps order, no Sort needed
col IS NULL	Yes	B-tree stores NULLs
col LIKE 'abc%', C locale	Yes	Translated into a comparison range automatically
col LIKE 'abc%', en_US locale	No	Needs text_pattern_ops or COLLATE "C"
col LIKE '%abc'	No	Use a reverse(col) expression index or GIN pg_trgm
col LIKE '%abc%', ILIKE	No	GIN/GiST with pg_trgm
lower(col) = x	Only with an index on lower(col)	Expression index
col <> x	Almost never	Most rows match

Multicolumn indexes: PostgreSQL 18 adds skip scan for multicolumn B-trees, so missing the leading column is no longer always a disaster; details in composite index column order.

Real-world example

Real-world example

An orders table has a tracking_code text column (like "TRK-2026-004821"), and the application allows searching by the full code or by prefix ("TRK-2026-").

If the database does not run the C locale, the default CREATE INDEX ON orders (tracking_code) will not speed up prefix search, exactly as above.

Add CREATE INDEX ON orders (tracking_code text_pattern_ops) if prefix search is a frequent query. Check the database’s datcollate before assuming a regular index will automatically serve LIKE 'x%'.

Trade-offs

Pros

• Shallow tree (2-3 levels for millions of rows thanks to high fan-out), so lookup speed barely changes as the table grows
• Supports equality, ranges, and preserves order for ORDER BY/LIMIT without a separate Sort
• text_pattern_ops extends the B-tree to efficient prefix search without switching index type

Cons

• Only supports ordered comparison operators; does not help with LIKE '%x', full-text search, or set membership
• A non-C locale (common in production) silently disables regular indexes for prefix search; easy to miss because EXPLAIN does not warn, it simply picks Seq Scan
• Each extra index (including text_pattern_ops alongside a regular index) costs storage and slows writes

Common mistakes

Common pitfall

Seeing Seq Scan in EXPLAIN and concluding “the index is broken” or “PostgreSQL doesn’t use indexes”. In the example above, the index exists and is valid; the LIKE operator under the default locale just cannot be translated into a comparison the B-tree understands.

Before suspecting the index, check:

1. Whether the operator in WHERE is one a B-tree supports.
2. If it is LIKE, whether the database runs the C locale or the index uses text_pattern_ops.
3. Whether the planner estimates few enough rows for the index to be cheaper than a full table scan.

🎮 Try it

• Choose an index type: when to use a B-tree, when another type, when no index is needed.

Checklist for designing a B-tree index

1. Match the WHERE conditions against the lookup table above: a B-tree only translates <, <=, =, >=, > (including BETWEEN, IN, IS NULL).
2. For LIKE 'prefix%' search: check datcollate; if it is not C, create an index with text_pattern_ops (varchar_pattern_ops for varchar) or COLLATE "C".
3. Need both prefix search and locale-ordered ORDER BY/comparisons: keep two indexes, because text_pattern_ops does not serve locale order.
4. For LIKE '%suffix' or '%x%': do not add a regular B-tree; use GIN pg_trgm or an expression index on reverse().
5. For an Index Only Scan: only SELECT columns in the index and let VACUUM keep the visibility map current, or Heap Fetches will be large.
6. Each extra index costs storage and slows writes; only add one for frequent queries.

Summary

Key takeaways

• A B-tree is a balanced multi-way tree: 100,000 rows need only 276 pages, 2-3 levels deep
• It only translates conditions using <, <=, =, >=, >, including BETWEEN and LIKE 'prefix%' when the locale allows
• SELECT only indexed columns → Index Only Scan (Heap Fetches: 0); add other columns → back to the heap
• With a non-C locale (the default in most production setups), LIKE 'prefix%' needs an index built with text_pattern_ops; otherwise it silently falls back to Seq Scan
• No B-tree helps LIKE '%suffix', because there is no fixed starting point for an ordered comparison

References

• PostgreSQL 17 — Index Types
• PostgreSQL 17 — B-Tree Indexes
• PostgreSQL 17 — Operator Classes
• PostgreSQL 17 — Index-Only Scans and Covering Indexes