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
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:
select * from orders where user_id = 42;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#
create index orders_user_id_idx on orders (user_id);select * from orders where user_id = 42;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 msThe 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:
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 mscreate 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 BYon the indexed column free: the rows come out sorted.
select id, user_id, created_at from orders
where user_id between 100 and 110
order by user_id
limit 10;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 msNo 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#
select pg_size_pretty(pg_relation_size('orders_user_id_idx')) as index_size,
pg_size_pretty(pg_relation_size('orders')) as table_size;| index_size | table_size |
|---|---|
| 1144 kB | 6480 kB |
- Space. Every index is another structure on disk and in memory.
- Writes. Every
INSERTadds an entry to every index on the table, and anUPDATEthat 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.
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#
- PostgreSQL documentation: Indexes (Introduction, Index Types, Indexes and ORDER BY), B-Tree Indexes (implementation), Operator Classes and Operator Families, Using EXPLAIN.
- Use The Index, Luke by Markus Winand, chapter "Anatomy of an Index".
- MySQL reference manual: Clustered and Secondary Indexes.