B-Tree, BRIN, GIN & GiST Indexes

Learning outcomes

• Select optimal index types based on column selectivity
• Optimize timeseries and document queries with BRIN and GIN

Mental model

Indexes accelerate data retrieval by organizing column keys into specialized disk data structures. Choosing the wrong index type degrades write performance without improving query speeds.

Theory

• B-Tree: Default self-balancing search tree. Best for high-selectivity equality (=) and range queries (<, >).
• BRIN (Block Range Index): Stores min/max values for block ranges (e.g. 128 pages). Extremely compact for naturally ordered timeseries data.
• GIN (Generalized Inverted Index): Inverted index mapping elements to tuple IDs. Essential for JSONB keys, array containment (@>), and full-text search.

-- High-selectivity unique lookup (B-Tree)
CREATE INDEX idx_users_email ON users USING btree(email);

-- Compact timeseries range index (BRIN)
CREATE INDEX idx_logs_created_at ON audit_logs USING brin(created_at);

-- Inverted document index for JSONB containment (GIN)
CREATE INDEX idx_events_payload ON events USING gin(payload jsonb_path_ops);

Alternatives and trade-offs

• B-Tree: Fast O(log N) lookups, but large disk footprint (~MBs/GBs per index).
• BRIN: Tiny disk footprint (less than 1% of B-Tree size), but only effective when physical heap data is strictly ordered by insertion time.
• GIN: Fast multi-element containment search, but updates incur high write amplification.

Failure modes and misconceptions

1. Indexing Low-Cardinality Columns: Creating a B-Tree index on a boolean is_active column is ignored by the query planner because sequential scans are faster.
2. Unused Index Overhead: Every index must be updated during INSERT, UPDATE, and DELETE operations, degrading write throughput.

Decision scenario

Use BRIN indexes on large append-only timestamp log tables (>100 million rows) to save 99% of index disk space while enabling fast range scans.

Learning outcomes

• Evaluate column selectivity and query patterns to select the optimal index type.
• Implement BRIN indexes for ordered append-only timeseries data.
• Build GIN expression indexes for fast JSONB document lookups.

Trade-offs

Indexes dramatically accelerate query reads, but introduce storage overhead and slow down database write operations (INSERT/UPDATE/DELETE).

Primary sources

• PostgreSQL 16 Architecture, MVCC & Query Optimization Manual — PostgreSQL Global Development Group, verified 2026-07-22