Module 5 — Indexes: B-Tree Internals, GIN, GiST, and When Each One Hurts You

What this module covers: An index is not a free performance boost. Every index has a write cost that compounds with every INSERT, UPDATE, and DELETE. Every index bloats over time. Every index has a specific structure that makes it fast for some query patterns and useless — or actively harmful — for others. This module covers the internal mechanics of every major Postgres index type, how the planner decides whether to use them, and the discipline of indexing for write-heavy production systems.

The Fundamental Trade-off

Before any index mechanics: the decision to add an index is always a trade-off between read speed and write cost.

Every index on a table is an additional data structure that must be kept consistent with the heap. When you insert a row, Postgres inserts into the heap and into every index. When you update a row, Postgres updates every index whose columns changed. When you delete a row, Postgres marks the row dead in the heap and in every index.

On a table with 8 indexes:

• An INSERT writes to 9 locations (1 heap + 8 indexes)
• An UPDATE that changes 3 indexed columns writes to 7 locations (1 heap old + 1 heap new + 5 unchanged index entries + 2 old index deletes + 2 new index inserts — and WAL for all of it)
• A DELETE marks dead in 9 locations

This is before considering the WAL generated for each operation. With full page writes after each checkpoint (Module 3), each of those 9 page modifications can generate 8KB of WAL on first write post-checkpoint.

The discipline of indexing: add indexes for queries that are hot enough to justify the write cost on every insert/update/delete. Remove indexes that are not being used. Be precise about which columns need indexing and in which order.

B-Tree Index Internals

The B-tree is Postgres's default index type. CREATE INDEX without specifying a type creates a B-tree. Understanding it at the page level makes every other B-tree behavior — splits, bloat, planner decisions, ordering — obvious.

The B-Tree Structure

A B-tree index is a balanced tree of fixed-size 8KB pages. There are three kinds of pages:

Meta page (page 0): Contains the root page pointer and fast-root pointer. The root is where all searches start.

Internal pages (branch nodes): Contain key-pointer pairs. Each entry holds an index key value and a pointer to the child page where values ≤ that key live. Internal pages do not contain heap TIDs — they are navigation only.

Leaf pages: Contain index entries, each being a key value + heap TID (page number + offset). Leaf pages are linked in a doubly-linked list in sorted order — this is what makes range scans efficient. You find the first matching leaf entry, then follow the right-sibling pointer without traversing the tree again.

B-Tree Searches

A point lookup (e.g., WHERE block_height = 18500050) traverses from root to leaf:

1. Read root page → find the internal entry where 18500050 falls → get child pointer
2. Read internal page → find the next child pointer
3. Read leaf page → find entries with block_height = 18500050, extract TIDs
4. For each TID: heap fetch (check visibility, return row)

For a 3-level tree with 100M rows, this is 3 page reads + 1 heap read = 4 random I/Os per row. With shared_buffers warmed up, those pages are in cache and the lookup is pure CPU.

Range Scans and the Leaf Chain

For WHERE block_height BETWEEN 18500000 AND 18500100:

1. Tree traversal to find the first leaf entry ≥ 18500000
2. Scan right along the leaf chain, collecting TIDs
3. Sort TIDs (or not, depending on the access pattern)
4. Fetch each heap page

The leaf chain scan is sequential — efficient. The heap fetches are random — potentially expensive if the matching rows are spread across many heap pages. This is where correlation matters (covered below).

Page Splits: The Source of B-Tree Bloat

When a leaf page fills up, Postgres splits it: the existing entries are divided between the current page and a new page, and a pointer to the new page is inserted into the parent. If the parent is also full, it splits too — cascading upward.

The right-growth optimization: When inserts are strictly sequential (e.g., a BIGSERIAL primary key), Postgres detects this and always splits to the right — new pages are appended rather than split. This produces densely-packed pages with no wasted space. Sequential primary keys are cheaper to maintain in indexes than random ones.

Random inserts cause 50% fill factor after splits. By default, Postgres splits a full page roughly in half. After the split, both pages are ~50% full. On a random-insert workload, pages frequently hover between 50% and 100% full — wasting up to 50% of index storage.

Setting a lower fillfactor leaves room for updates without splits:

For indexes on frequently-updated columns, a lower fillfactor reduces page splits at the cost of larger index size. For append-only tables, use the default (90) or even higher.

HOT Updates and Index Overhead

Heap Only Tuple (HOT) updates are a critical optimization. When you update a row and the updated columns are NOT indexed, Postgres can avoid updating any indexes:

1. Old tuple is marked dead in the heap
2. New tuple is written to the same heap page (if space allows)
3. The old tuple's ctid pointer chains to the new tuple
4. No index entries are modified

HOT updates generate significantly less WAL and avoid index bloat. They only work when:

• The updated columns are not part of any index
• The new tuple fits on the same heap page as the old tuple

If hot_pct is low on a high-update table, audit which columns are being updated versus which are indexed. Sometimes removing an index on a column that is updated frequently (but not queried with it) dramatically improves write throughput.

Index Correlation

Correlation measures how well the physical order of rows in the heap matches the logical order of values in an index. It ranges from -1 (perfectly reversed) to +1 (perfectly aligned).

When correlation is low, an index scan fetches rows from scattered heap pages — potentially one random I/O per row. For large result sets, the planner may choose a sequential scan instead, because reading heap pages sequentially is more efficient than random fetches.

This is why CLUSTER (which rewrites the table in index order) can dramatically speed up range queries on low-correlation columns — but it's a full table rewrite and acquires an exclusive lock.

Multi-Column Indexes

A multi-column (composite) index on (a, b) stores entries sorted by a first, then b within each a value.

This index efficiently supports:

• WHERE block_height = X — uses the index (leftmost column)
• WHERE block_height = X AND status = Y — uses both columns
• WHERE block_height BETWEEN X AND Y — range on leading column
• ORDER BY block_height, status — sorted output

It does not efficiently support:

• WHERE status = Y — cannot use the index without the leading column
• ORDER BY status — not sorted by trailing column alone

The leading column rule: The index is only usable when the query predicates include the leftmost column(s). A query on status alone cannot use idx_transactions_height_status.

Column order matters for range queries: Put equality predicates first, range predicates last.

Partial Indexes

A partial index indexes only the rows that match a WHERE condition. This is one of the most underused features in Postgres.

Partial indexes:

• Are smaller (fewer entries → fewer pages → more cache hits)
• Have lower write cost (only insert/delete when the condition is met)
• Can be more selective (same selectivity over a smaller row set)

The pattern for status-filtered tables: If 95% of rows are in a terminal state (confirmed, failed) and 5% are active (pending), a partial index on active rows is 20x smaller than a full index and much more cache-friendly.

Expression Indexes

An expression index indexes the result of a function or expression, not a raw column value.

Expression indexes increase write cost because Postgres must evaluate the expression for every inserted/updated row and store the result in the index.

GIN Indexes: For Containment Queries

Generalized Inverted Index (GIN) is designed for data types where a single column value contains multiple "elements" — arrays, JSONB documents, tsvectors for full-text search.

How GIN Works

A GIN index maintains a posting list structure:

• Key: each distinct element (array element, JSONB key, lexeme)
• Value: the list of heap TIDs that contain this key

For a JSONB column, GIN indexes every key and value in every document. For an array column, it indexes every array element.

GIN Operators

GIN Write Cost: The Pending List

GIN indexes have a significantly higher write cost than B-tree because inserting one row requires updating the posting list for every element in the document. A JSONB document with 20 keys generates 20+ index updates per INSERT.

To mitigate this, GIN uses a pending list: new entries are first written to a small pending list on disk, and then merged into the main GIN structure in bulk during VACUUM or when the pending list fills gin_pending_list_limit (default 4MB).

This pending list is great for write throughput but means GIN indexes may not reflect very recent changes until the pending list is merged. For most use cases this is fine.

jsonb_path_ops vs jsonb_ops

jsonb_path_ops produces a smaller index (indexes only paths, not individual keys) and is faster for @> queries. The trade-off: it does not support ?, ?|, ?& operators.

GiST Indexes: For Geometric and Range Queries

Generalized Search Tree (GiST) is an extensible index framework that supports spatial queries, range type overlap, and nearest-neighbor searches. Unlike B-tree (exact ordering) and GIN (containment), GiST supports geometric predicates.

GiST for Full-Text Search

GiST can also index tsvector (full-text search vectors), but GIN is almost always preferred for full-text — GIN is faster for lookup, GiST is faster for writes.

GiST for Nearest-Neighbor (KNN)

GiST supports KNN searches using the <-> distance operator:

BRIN Indexes: For Naturally Ordered Large Tables

Block Range INdex (BRIN) is fundamentally different from B-tree and GIN. Instead of indexing individual values, it stores the min and max value for each range of heap pages (a "block range", default 128 pages = 1MB).

BRIN is useful when the column value is correlated with physical insertion order — i.e., newer rows have later timestamps, and they are inserted at the end of the heap. This is true for:

• Auto-incrementing IDs (BIGSERIAL)
• Timestamps with append-only insert patterns
• Block heights in a blockchain indexer

BRIN vs B-tree: When to Choose

The rule: use BRIN on timestamp or sequential ID columns in append-only tables when cardinality is high and correlation is high. Use B-tree everywhere else that needs fast point lookup.

A BRIN index on a 100M-row table with 128 pages per range is roughly 100M / 128 / (8KB/entry) ≈ 100KB. A B-tree on the same column is hundreds of megabytes. The BRIN query is slower (must scan all pages in matching ranges), but for large time-range filters it eliminates the vast majority of pages.

Hash Indexes

Hash indexes store a hash of the indexed value and are only useful for equality comparisons (=). They are smaller than B-tree for equality workloads but do not support range queries, ordering, or NULL.

In practice, B-tree handles equality lookups nearly as fast as hash indexes, and B-tree is more versatile. Hash indexes are a niche optimization for very high cardinality equality columns (like UUIDs or hashes) where the planner otherwise might not use the index effectively.

Index-Only Scans

When all columns needed by a query are in the index, Postgres can satisfy the query without touching the heap at all — an index-only scan.

Index-only scans are fast because they avoid random heap I/O. But they require the Visibility Map to confirm tuple visibility — if the VM bit for a page is not set (page has not been vacuumed recently), Postgres must fetch the heap page anyway to check visibility.

If heap fetches are high on an index-only scan, run VACUUM on the table to set VM bits. After vacuum, heap fetches should drop to zero.

Covering Indexes: INCLUDE

Postgres 11+ supports INCLUDE columns — columns stored in the index leaf pages but not part of the sort key. This enables index-only scans without affecting the index sort order.

INCLUDE columns increase index size but don't affect the B-tree structure or split behavior. Use them when you have a frequently-used query that needs just a few extra columns beyond the index key.

When Indexes Hurt: The Cases Most Engineers Miss

1. Low-Selectivity Columns

An index on a column with few distinct values (low cardinality) is often useless or counterproductive.

The planner estimates that fetching 95% of rows via index is more expensive than a sequential scan. It will choose the sequential scan. The index is wasted disk space and write overhead.

The fix: partial index on the selective values only:

2. Too Many Indexes on a Write-Heavy Table

At 2,000 inserts/second, each insert touches all 12 index structures. That's 24,000 index page modifications per second, each potentially generating WAL. This is the hidden write amplification that only becomes visible when write throughput starts saturating I/O.

Audit unused indexes:

Drop indexes with idx_scan = 0 that have been around long enough to capture representative traffic (reset stats after major traffic pattern changes with SELECT pg_stat_reset()).

3. Indexes That Are Never Used by the Planner

An index exists but the planner refuses to use it — not because it's wrong, but because the cost estimate says sequential scan is cheaper.

If block_height > 18000000 matches 95% of rows, the planner is correct — sequential scan is faster. The index exists but is never used. It costs write overhead on every insert with no read benefit.

Force the planner to show you what it thinks:

4. Indexes That Break HOT Updates

Any index on a column that is frequently updated prevents HOT updates on those updates, forcing full index maintenance.

5. Unused Unique Indexes Beyond the Constraint

Unique indexes are often added for constraint enforcement, which is valid. But sometimes engineers add unique indexes "just in case" without realizing the constraint enforcement itself already creates an index:

Check for duplicate indexes (same columns, same order) and drop the redundant ones.

The Planner and Indexes: When Good Indexes Are Ignored

Statistics Freshness

The planner decides whether to use an index based on statistics. If statistics are stale (bulk load without ANALYZE, or autovacuum hasn't run), the planner may misestimate selectivity and choose the wrong plan.

enable_indexscan and Plan Forcing

Bitmap Index Scans

When a query matches many rows via an index, Postgres may use a bitmap index scan instead of a regular index scan:

1. Scan the index, building a bitmap of matching heap page numbers (not individual TIDs)
2. Sort the page numbers
3. Read heap pages in sorted order (sequential-ish access pattern)

This is more efficient than random-order index scan when many rows match. It trades the precise TID ordering for coarser page-level ordering, which reduces random I/O.

Multiple bitmap index scans can be ANDed or ORed together:

Production Index Audit Workflow

Production Incident: Index Bloat Causing 3x Query Regression

Context: A transactions table with a B-tree index on (sender, block_height) used for API queries like "show me all transactions from sender X in the last 10,000 blocks."

What happened:

The table processed roughly 500 updates/second to the status column. These updates were NOT HOT updates because an index on status existed from an earlier investigation. The index on (sender, block_height) was fine — but each non-HOT update to status caused a full index page access in the sender index as well, because the new tuple needed a new entry even though sender hadn't changed.

After 6 months, the (sender, block_height) index had grown to 8GB from its original 2GB. Average leaf page density had dropped to 45% from the constant churn of dead tuple entries.

The query WHERE sender = '0xabc...' AND block_height > 18400000 now scanned 2x as many leaf pages as necessary, because each page was only 45% full. Query time went from 2ms to 6ms — imperceptible in isolation, but 3x slower and visible in p99 latency.

The fix:

After the reindex, query time returned to 2ms. The REINDEX INDEX CONCURRENTLY took 40 minutes on the 8GB index but did not lock reads or writes during the rebuild.

Summary

Core rules:

1. Every index has a write cost — measure it, don't ignore it
2. Remove indexes the planner isn't using (idx_scan = 0)
3. Low-cardinality columns need partial indexes, not full indexes
4. HOT updates are killed by indexes on updated columns — audit before adding
5. Check correlation before relying on B-tree range scans
6. BRIN is underused — add it to sequential timestamp/ID columns
7. After bulk loads, always ANALYZE — stale stats cause good indexes to be ignored

Indexes determine how the planner accesses data. Module 6 covers how the planner actually makes those decisions — the cost model, statistics, join strategies, and how to diagnose every class of plan regression.

Next: Module 6 — Query Planning and Execution: How Postgres Decides What to Do With Your Query →