B-tree indexes

How the default index finds one row among millions in three or four page reads, and what it costs.

Draft. This page is new and has not yet been reviewed by a second person. Every query output on it was produced by a real run on PostgreSQL 18.6 (PGlite 0.5.9). If something looks wrong, report it.

On this page
  1. Without an index
  2. With an index
  3. At production scale
  4. How it stays fast
  5. What a B-tree can answer
  6. What it costs
  7. Try it yourself
  8. In MySQL
  9. Sources

An index is a second, smaller structure kept next to the table that lets the database find rows without reading every page. PostgreSQL's default, and by far the most common, is the B-tree. It keeps keys sorted, it stays shallow however much data it holds, and it answers equality, ranges and sorted output with the same structure.

Without an index#

To find one customer's orders, the database has no choice but to read the whole table and test every row:

sql
select * from orders where user_id = 42;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Seq Scan on orders  (cost=0.00..2060.00 rows=44 width=31) (actual time=0.287..7.435 rows=44.00 loops=1)
  Filter: (user_id = 42)
  Rows Removed by Filter: 99956
  Buffers: shared hit=810
Planning:
  Buffers: shared hit=16
Planning Time: 0.226 ms
Execution Time: 7.561 ms

Seq Scan on orders read every page of the table (Buffers counts pages), and Rows Removed by Filter shows almost 100,000 rows were read only to be thrown away. In PostgreSQL 18, EXPLAIN ANALYZE reports buffers by default.

With an index#

sql
create index orders_user_id_idx on orders (user_id);
sql
select * from orders where user_id = 42;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Bitmap Heap Scan on orders  (cost=4.63..147.46 rows=44 width=31) (actual time=0.045..0.156 rows=44.00 loops=1)
  Recheck Cond: (user_id = 42)
  Heap Blocks: exact=44
  Buffers: shared hit=44 read=2
  ->  Bitmap Index Scan on orders_user_id_idx  (cost=0.00..4.62 rows=44 width=0) (actual time=0.025..0.026 rows=44.00 loops=1)
        Index Cond: (user_id = 42)
        Index Searches: 1
        Buffers: shared read=2
Planning:
  Buffers: shared hit=5 read=1
Planning Time: 0.259 ms
Execution Time: 0.214 ms

The plan now starts from the index. The number of pages read drops by more than an order of magnitude, and nothing is read just to be discarded. (Why a bitmap scan here rather than a plain index scan is the subject of scan types.)

At production scale#

With 100,000 orders even the slow plan above takes milliseconds, so the difference is easy to shrug off. Here is the same query on the same shop generated 100 times larger, recorded on a real PostgreSQL server:

At production scale: One user's orders, among ten million 2,000,000 users and 10,000,000 orders, recorded on PostgreSQL 18.3 on 2026-10-21. Each plan is the second of two runs, so the data was already in memory.

Without an index

select * from orders where user_id = 42;
Gather  (cost=1000.00..133990.66 rows=18 width=31) (actual time=4.187..213.522 rows=525.00 loops=1)
  Workers Planned: 2
  Workers Launched: 2
  Buffers: shared hit=80906
  ->  Parallel Seq Scan on orders  (cost=0.00..132988.86 rows=8 width=31) (actual time=3.667..182.374 rows=175.00 loops=3)
        Filter: (user_id = 42)
        Rows Removed by Filter: 3333158
        Buffers: shared hit=80906
Planning Time: 0.064 ms
JIT:
  Functions: 6
  Options: Inlining false, Optimization false, Expressions true, Deforming true
  Timing: Generation 0.673 ms (Deform 0.120 ms), Inlining 0.000 ms, Optimization 0.508 ms, Emission 6.840 ms, Total 8.021 ms
Execution Time: 213.885 ms
create index orders_user_id_idx on orders (user_id);

With the index on user_id

select * from orders where user_id = 42;
Index Scan using orders_user_id_idx on orders  (cost=0.43..76.75 rows=18 width=31) (actual time=0.027..0.767 rows=525.00 loops=1)
  Index Cond: (user_id = 42)
  Index Searches: 1
  Buffers: shared hit=526
Planning Time: 0.089 ms
Execution Time: 0.809 ms

Without the index the server read every one of the table's 80,906 pages to return 525 rows. That took 214 ms even though it split the scan across three processes (Gather and Parallel Seq Scan: a server runs big scans in parallel, which the in-browser engine cannot). With the index it read 526 pages and finished in under a millisecond. The gap grows with the table, because a full scan reads every page and the index reads only the pages that hold matching rows.

Two more things differ from the small database. The estimate (rows=18) is well below the 525 rows found, because on a table this size ANALYZE reads a sample (30,000 rows by default) instead of every row. And the JIT lines show the server compiling parts of an expensive query to machine code; the in-browser engine has no JIT.

How it stays fast#

  • Sorted pages. Each page holds keys in order. Inner pages hold boundaries and point down to the page that covers a range of keys; leaf pages hold every key, each with the address of its row.
  • Shallow. A real page holds hundreds of keys, so each level multiplies the reach by hundreds. Three or four levels cover hundreds of millions of rows, which means a lookup reads three or four index pages. In the animation the pages hold three keys so that you can see the splits.
  • Always balanced. When a page fills up it splits in two and passes a boundary key up to its parent. The tree only grows taller when the root itself splits, so every leaf is always the same distance from the root.
  • Linked leaves. Each leaf points to the next one, so a range is one descent followed by a walk sideways. That also makes ORDER BY on the indexed column free: the rows come out sorted.
sql
select id, user_id, created_at from orders
where user_id between 100 and 110
order by user_id
limit 10;
Plan, executed real output from PostgreSQL 18.6 (PGlite 0.5.9). Timings depend on the machine; the shape and the row counts do not
Limit  (cost=0.29..33.10 rows=10 width=16) (actual time=0.020..0.055 rows=10.00 loops=1)
  Buffers: shared hit=11 read=1
  ->  Index Scan using orders_user_id_idx on orders  (cost=0.29..1243.86 rows=379 width=16) (actual time=0.017..0.037 rows=10.00 loops=1)
        Index Cond: ((user_id >= 100) AND (user_id <= 110))
        Index Searches: 1
        Buffers: shared hit=11 read=1
Planning:
  Buffers: shared hit=18 read=1
Planning Time: 0.477 ms
Execution Time: 0.084 ms

No Sort node: the index already returns rows in user_id order, so the database reads entries from the start of the range and stops after ten. Index Searches: 1 (new in PostgreSQL 18) confirms a single descent served it.

Take the LIMIT away and the plan changes: the same range matches a few hundred orders scattered across the table, and the planner prefers to collect them with a bitmap scan and sort them afterwards. Sorted order from an index is free, but it is only one of the costs the planner weighs.

What a B-tree can answer#

A B-tree helps when a query compares an indexed column using =, <, <=, >, >=, BETWEEN, IN, or IS NULL, and when it sorts by the indexed column (in either direction). A pattern match like LIKE 'abc%' can also use one, but only when the index uses the C collation or a pattern operator class such as text_pattern_ops; a pattern that starts with a wildcard, LIKE '%abc', cannot.

It does not help when the column is wrapped in a function or expression the index was not built on: an index on email does nothing for where lower(email) = …. That needs an expression index.

What it costs#

sql
select pg_size_pretty(pg_relation_size('orders_user_id_idx')) as index_size,
       pg_size_pretty(pg_relation_size('orders')) as table_size;
Result 1 row; real output from PostgreSQL 18.6 (PGlite 0.5.9)
index_sizetable_size
1144 kB6480 kB
  • Space. Every index is another structure on disk and in memory.
  • Writes. Every INSERT adds an entry to every index on the table, and an UPDATE that changes an indexed column (or cannot be done as a HOT update) must touch the indexes too. A table with ten indexes pays for ten extra writes per insert.
  • Choice. The planner may still decide a full scan is cheaper, for example when a large share of the rows match. See designing indexes.

Try it yourself#

Each exercise runs on the same sample database. Your changes are made inside a transaction and undone after every check, so you cannot break anything.

Exercise

One customer's orders

The "Your orders" page lists one customer's orders, newest first. Every visit reads the whole orders table, and the page gets slower as the shop grows.

Your task. Make the query read only the rows it needs, without changing what it returns.

select id, status, created_at, total
from orders
where user_id = 42
order by created_at desc

This exercise runs a real database in your browser and needs JavaScript.

In MySQL#

Not run here; from the MySQL reference manual. InnoDB indexes are also B+trees. Because an InnoDB table is itself the primary-key B-tree, a secondary index entry holds the primary key rather than a row address, so a lookup through a secondary index is followed by a search of the primary key. Keeping the primary key short keeps every secondary index small.

Sources#

Esc
↑ ↓ to move↵ to open