How a B-tree index speeds up a query

SQL, indexing and PostgreSQL Junior Python 3.13+ PostgreSQL 17+ Reviewed By Best Latest Apps

Pick the fix

SELECT * FROM orders WHERE customer_id = 42 scans the whole 1M-row table every time. What do you add?

Options
Hint 1 of 1

Which column does the WHERE clause filter on?

Choose an answer, then open Show answer below to check it.

A toy table of 8 pages with a 3-level index. Finding id 450 follows one cell per level and reads 1 table page; without a usable index every table page is read.

Plan shape checked with EXPLAIN on PostgreSQL 17; page counts are a toy table

Text version

No usable index (Seq Scan):

  1. Root: not used
  2. Inner: not used
  3. Leaf: not used
  4. Table: H1, H2, H3, H4, H5, H6, H7, H8

Primary key index (Index Scan):

  1. Root: 301–600
  2. Inner: 401–500
  3. Leaf: 434–466
  4. Table: H4
Pages read
ScenarioPlanIndex pagesTable pages
No usable indexSeq Scan08
Primary key indexIndex Scan31
Show answer

Answer: A CREATE INDEX CONCURRENTLY ON orders (customer_id);

Correct. An index on the filtered column; CONCURRENTLY avoids blocking writes while it builds.

Without an index on customer_id, PostgreSQL has to read every row to find matches. A B-tree on that column lets it seek straight to them, and CONCURRENTLY builds it without blocking writes.

Why not the others?
  • B CREATE INDEX ON orders (id, customer_id);. The leading column is id, so a filter on customer_id alone can't seek into it.
  • C VACUUM FULL orders;. Compacts the table but doesn't change how rows are found.
  • D SET enable_seqscan = off;. A planner debugging switch, not a fix; with no usable index it still scans.

30-second answer

A B-tree index keeps the indexed values sorted in a shallow, balanced tree of pages, each pointing to the table row's location. A lookup walks from the root through a few levels to the leaf that holds the value, then fetches the row, so cost grows with the tree's height, not the table's size. On a 1,000,000-row table in our PostgreSQL 17 run, a primary key lookup read 4 pages, while a filter on an unindexed column read all 7,353 table pages.

Practise saying it · 35 s. No recording, just a timer

Explain how a B-tree index works.

Say your answer out loud, then check which of these points you covered:

  • Sorted keys in a balanced tree
  • Cost grows with height, not rows
  • Points to heap rows
  • Writes pay for every index

Deep dive

Every PostgreSQL table is a heap (unordered); indexes are separate structures pointing at row locations (TIDs).

B-trees support equality, ranges, ORDER BY and prefix LIKE on text_pattern_ops.

Each index slows writes and takes space: every INSERT and most UPDATEs must change it.

The planner may still choose a sequential scan when a query returns a large share of the table; that's usually right.

Two plan shapes for two filters Ran on PostgreSQL 17.11
SQL · PostgreSQL 17
SET max_parallel_workers_per_gather = 0;
CREATE TABLE orders (id int PRIMARY KEY, customer_id int);
INSERT INTO orders
SELECT g, g % 1000 FROM generate_series(1, 100000) g;
VACUUM ANALYZE orders;
EXPLAIN (COSTS OFF) SELECT * FROM orders WHERE customer_id = 42;
EXPLAIN (COSTS OFF) SELECT * FROM orders WHERE id = 450;

Pages read on a 1,000,000-row table Ran on PostgreSQL 17.11
SQL · PostgreSQL 17
CREATE TABLE users (id int PRIMARY KEY, email text, plan text);
INSERT INTO users
SELECT g, 'user' || g || '@example.com', 'free'
FROM generate_series(1, 1000000) AS g;
VACUUM ANALYZE users;
SET max_parallel_workers_per_gather = 0;
CREATE FUNCTION pages_read(q text) RETURNS bigint
LANGUAGE plpgsql AS $$
DECLARE plan json;
BEGIN
  EXECUTE 'EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON) ' || q INTO plan;
  RETURN (plan->0->'Plan'->>'Shared Hit Blocks')::bigint
       + (plan->0->'Plan'->>'Shared Read Blocks')::bigint;
END $$;
SELECT pages_read('SELECT * FROM users WHERE id = 500000');
SELECT pages_read(
  'SELECT * FROM users WHERE email = ''user500000@example.com''');

Common mistakes

  • Indexing every column 'just in case'.
  • Expecting an index on a low-selectivity column like a boolean to help most queries.
  • Forgetting that a function on the column (lower(email)) can't use a plain index on email.

Senior take & follow-ups

Explain the sorted tree and the height argument, and balance it with write cost and selectivity.

Follow-up questions

Think of your answer first, then open the hint.

  1. When is a sequential scan faster than an index?

    Show hint

    When the query reads a big share of the table; random page reads cost more than sequential ones.

  2. How tall is a B-tree on 1 billion rows?

    Show hint

    Usually 4 to 5 levels, because each page holds hundreds of keys.

Related questions

Suggest a fix if something here is wrong or out of date.