B-Tree Indexes: Structure and When They Win

The one thing to understand first

A B-tree is the default and most versatile PostgreSQL index, implemented in src/backend/access/nbtree/. It supports equality and range operators (=, <, <=, >, >=, BETWEEN, IN), ORDER BY acceleration, and uniqueness enforcement — all from one balanced, ordered structure.

A B-tree wins because it keeps your keys sorted — and almost everything useful (selective equality, ranges, ORDER BY, uniqueness) is just a consequence of sorted order. Understand that, plus the leftmost-prefix rule for composite indexes, and most "why isn't my index used" questions answer themselves.

Structure: a balanced ordered tree

PostgreSQL implements a Lehman-Yao B-tree variant designed for high concurrency. The tree has:

• Internal pages — hold separator keys and downlinks routing a search toward the right leaf.
• Leaf pages — hold the indexed keys in sorted order, each with a TID pointing to the heap tuple. Leaves are linked left-to-right (and right-to-left) so a range scan can walk siblings without returning to the root.

Because the tree is balanced, any lookup costs O(log n) page reads — typically 3–4 page accesses even for huge tables.

High concurrency by design

The Lehman-Yao technique adds a high key and a right-link to every page. A descending search never needs to hold a lock on a parent while locking a child; if a concurrent split moved the target, the searcher follows the right-link to find it. This lets many sessions read and modify the same index with minimal blocking — central to PostgreSQL's write concurrency.

When a B-tree wins

• High selectivity equality — WHERE email = ? returning few rows.
• Range scans — WHERE created_at >= ? reads a contiguous leaf range.
• ORDER BY / LIMIT — the index already provides sorted output, enabling cheap top-N without a sort.
• Uniqueness — primary keys and unique constraints are enforced by a unique B-tree.

Column order in composite indexes

For an index on (a, b, c), the leftmost-prefix rule applies: it can satisfy predicates on a, a,b, or a,b,c, and an equality on a combined with a range on b. It cannot efficiently serve a query filtering only on b. Order columns by: equality predicates first, then the range/sort column last.

Index-only scans

If a query's needed columns are all in the index, PostgreSQL can answer from the index alone — but it must still confirm visibility. It checks the visibility map: if the heap page is marked all-visible, it skips the heap fetch. This is why a freshly bulk-loaded table benefits from VACUUM before index-only scans pay off, and why covering indexes use INCLUDE:

-- Covering index: key on (customer_id), payload total_amount
CREATE INDEX idx_orders_cust ON orders (customer_id) INCLUDE (total_amount);
-- Now SELECT total_amount WHERE customer_id = ? can be index-only.

Layer 3 — Watch it happen on your own database

-- Depth and page counts of a real B-tree
CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT btpo_level, type, live_items, dead_items
FROM   bt_page_stats('idx_orders_cust', 1);
SELECT * FROM bt_metap('idx_orders_cust');   -- root, level (tree height)

-- Prove an index-only scan needs the visibility map
EXPLAIN (ANALYZE, BUFFERS)
SELECT total_amount FROM orders WHERE customer_id = 42;  -- Index Only Scan
VACUUM orders;   -- sets all-visible bits; Heap Fetches drops toward 0

bt_metap shows the tree height (usually 3–4 even for huge tables — that is the O(log n) promise made concrete). The second block demonstrates why index-only scans need a recent VACUUM: before the visibility map is set you will see non-zero Heap Fetches in the plan; after vacuum they fall away.

Layer 4 — The levers this hands you

• Order composite columns deliberately: equality predicates first, then the single range/sort column last, so the leftmost-prefix rule works for you.
• Use covering indexes with INCLUDE to make hot queries index-only without bloating the key.
• Build without blocking using CREATE INDEX CONCURRENTLY on busy tables.
• Drop dead weight. Every write maintains every applicable index; find unused ones via pg_stat_user_indexes.idx_scan = 0 and remove them.
• Let deduplication help on low-cardinality indexes — modern PostgreSQL compresses duplicate keys in leaves automatically.

Layer 5 — What an Oracle DBA should expect vs what they get

B-trees are universal, but the surrounding rules differ:

• Index-only scans depend on the visibility map. Oracle index-only access just needs the columns in the index. In Postgres, because the index entry does not record visibility, an index-only scan also consults the all-visible bit — so vacuum freshness directly affects whether it stays "index only."
• No bitmap indexes, no IOTs. Oracle bitmap indexes and Index-Organized Tables have no direct Postgres equivalent; for low-cardinality you rely on B-tree deduplication or BRIN, and there is no clustered-by-PK storage (use CLUSTER as a one-off reorg).
• **INCLUDE columns ≈ Oracle covering via composite key,** but Postgres keeps the payload out of the ordered key, so uniqueness and tree size stay based on the key columns only.
• Concurrency by right-links (Lehman-Yao), not by the specific latch/ITL mechanics you know; the net effect (readers rarely block on splits) is similar but the failure modes and tuning knobs are different.

Key takeaway

A PostgreSQL B-tree is a balanced, ordered, Lehman-Yao tree: O(log n) lookups, linked leaves for range scans, and high concurrency via high keys and right-links. It wins on selective equality, ranges, ordered output, and uniqueness. Design composite indexes around the leftmost-prefix rule, use INCLUDE for index-only coverage, keep vacuum current so index-only scans stay cheap, and prune indexes that never serve a scan.