B-tree Indexes — Structure & How Range/Equality Queries Use Them

An index is a separate, sorted structure that lets a database find rows by value without scanning the whole table — turning an O(n) "look at every row" into an O(log n) "walk down a shallow tree." The B-tree is the structure that makes this work on disk, for equality and range queries alike, and it is the default index type in every relational database.

Intermediate indexes b-tree query-performance range-query disk-io Created 2026-05-31 · Updated 2026-05-31

Key Components

Index: A separate, sorted data structure that maps a column value to the location of its rows, so the engine can find them without reading the whole table.
Sequential scan (Seq Scan): The fallback when no usable index exists: read every row in the heap and test the predicate — O(n) in the table size.
B+ tree: The on-disk index structure used in production: balanced, sorted, high-fanout, with all entries in the leaves and the leaves chained in a sorted doubly-linked list.
Branch (internal) node: Pure navigation — each entry holds the max value of the child below plus a pointer down. No row data, just signposts toward the right leaf.
Leaf node & TID: Holds the actual entries (value → row pointer). The pointer is a TID/RID — the physical location of the row in the heap. Leaves are linked in sorted order, which is what makes range scans fast.

Concrete Example

A table is a heap — an unordered pile of rows. With no index, a filter forces a sequential scan across all of them. Creating a B-tree index on the filtered column converts that scan into a handful of page reads through the tree:

-- Without an index: Seq Scan reads all 10M rows
SELECT * FROM comments WHERE post_id = 42;

CREATE INDEX idx_comments_post_id ON comments(post_id);
-- Now: ~4–5 page reads via the tree, regardless of table size

You can't simply keep the table itself sorted — inserts arrive constantly, and you'd need a different physical order for every column you might filter on. So the database builds a separate sorted structure that points back to the rows. After the index exists, WHERE post_id = 42 descends root → branch → leaf, reads the row pointer (TID), and jumps straight to the heap row — about four to five page reads whether the table holds ten thousand rows or ten million.

Visual Model

Picture a phone book. To find one name (equality) you flip straight to it. To find a span of names (range) you find the first one, then read forward — the pages are already in order. It's fast on disk because each page holds hundreds of names, so any name is reachable in four or five flips. Keeping it sorted is what costs effort on every insert and delete: the write tax.

Walk the trace below to watch an equality lookup of id = 42 descend the tree, then see how a range scan reuses the sorted leaf chain instead of re-descending.

Step 1 of N

Deeper — Edge Cases & Gotchas

Why a B-tree and not a binary search tree? Indexes live on disk and are read in fixed pages (8 KB in Postgres). The bottleneck is disk reads, not comparisons — a disk fetch is roughly 10,000× slower than an in-memory compare. A binary tree (2 children per node) is tall and thin, so it costs many fetches; a B-tree packs many keys into each page-sized node, making it wide and shallow. Node count is proportional to disk fetches, so minimizing nodes visited is the entire game.

Binary tree (10M rows): depth ~23  → up to 23 disk reads
B-tree   (10M rows):    depth 4–5  → 4–5 disk reads   (each level ~100× capacity)

Three defining properties: balanced (all leaves at equal depth, so every lookup costs the same — no slow path), sorted, and multi-way (high fanout, not just two children). Range scans and ORDER BY ... LIMIT come for free because the leaves are sorted and linked — Postgres's docs even call sorting the B-tree's primary use case.

When a B-tree index won't be used

<> / NOT IN — "everything except 42" isn't a contiguous range, so there's nothing to descend to.
Leading wildcard — LIKE 'abc%' works (a known prefix is a range); LIKE '%abc' can't (no known starting point).
NULLs — = NULL is always a logic error; IS NULL can use the index because Postgres stores NULLs separately.
Low selectivity — if a query returns a large fraction of rows (>~5–10%), the planner may prefer a Seq Scan: scattered heap jumps cost more than one linear sweep. Indexes help selective queries.
Write tax — every INSERT/UPDATE/DELETE must maintain every index (add/remove a leaf entry, occasionally split a page). Faster reads paid for at write time — the same trade as denormalization. Don't index columns you never filter or sort by.

Anti-pattern: wrapping the indexed column in a function and expecting the plain index to still be used.

CREATE INDEX idx_users_email ON users(email);

-- Will NOT use idx_users_email — falls back to Seq Scan:
SELECT * FROM users WHERE lower(email) = 'a@b.com';

The subtle part: lower() is applied to the stored column value, not to your search literal. Per row it means "lowercase this row's email, then compare." A row stored as A@b.com evaluates lower('A@b.com') = 'a@b.com' → TRUE, so every casing variant matches. But the plain index is sorted by the raw stored strings (ASCII puts uppercase before lowercase), so those matching variants are scattered across the whole index — there is no single contiguous span to descend to. The planner matches indexes syntactically against the exact predicate expression; it finds an index on email, not on lower(email), and refuses to evaluate the function across every stored entry on the fly (that would be a full scan, defeating sortedness).

The fix is an expression index that computes and stores the transformed value at write time:

CREATE INDEX idx_users_lower_email ON users(lower(email));
-- Now lower(email) = 'a@b.com' descends a tree sorted on lower(email).

Rule of thumb: a B-tree is usable only when the query filters by the exact expression the tree is sorted on. WHERE age + 1 = 30 won't use an index on age, but WHERE age = 29 will — and WHERE email = 'a@b.com' (no lower()) can use a plain index because the predicate dimension matches the sort dimension.

Test Yourself

Why is a high-fanout B-tree preferred over a binary search tree for an on-disk index?

Which leaf-node property lets a B-tree serve BETWEEN and ORDER BY efficiently, while an equality-only structure (like a hash index) cannot?

Which of these queries can use a plain B-tree index on email?

You add 5 indexes to a write-heavy table to speed up reads. What got worse, and which prior topic is this the same trade as?