Database Indexing Strategies — From B-Trees to BRIN

Overview

A dashboard query takes 30 seconds. You add an index on the filter column, and it drops to 5 milliseconds. That’s the power of indexes — and also the trap. Six months later, writes are 40% slower, the index is bloated from millions of updates, and the query planner is ignoring it anyway because statistics are stale.

Indexes are the single most impactful performance tool in a database, but they’re not free. Every index consumes storage, slows down writes, and can actively hurt performance if the query planner decides a sequential scan is cheaper. The difference between a well-indexed table and a poorly-indexed one is often 100x in query speed — and 2x in write speed, in the wrong direction.

This guide covers the six index types you’ll actually use in production: B-Tree, Hash, GIN, GiST, BRIN, and partial indexes. For each, you’ll see when to use it, when to avoid it, and concrete SQL you can run to verify it’s working. For query-level optimization beyond indexing, see the Complete Guide to SQL Query Optimization.

When to Use

Indexing is the right tool when your workload is read-heavy and queries filter, join, or sort on specific columns. The four scenarios below cover the vast majority of cases where an index will dramatically improve performance:

• Queries filtering on specific columns (WHERE, JOIN conditions)
• Sorting large result sets (ORDER BY, GROUP BY)
• Enforcing uniqueness constraints (UNIQUE, PRIMARY KEY)
• Accelerating full-text search, geospatial queries, and JSONB lookups

If your table has fewer than ~10,000 rows, a sequential scan is often faster than an index scan — the planner knows this and will ignore your index. If your workload is almost entirely writes (INSERT/UPDATE/DELETE) with few reads, indexes hurt more than they help. For a deeper dive into query-level optimization beyond indexing, see the Complete Guide to SQL Query Optimization.

B-Tree Indexes

The default index type in most relational databases. B-Trees maintain sorted data that allows O(log n) lookups, range scans, and ordered traversal. PostgreSQL, MySQL (InnoDB), SQL Server, and SQLite all use B-Tree as the default index structure.

CREATE INDEX idx_users_email ON users(email);

-- Uses index: exact match
SELECT * FROM users WHERE email = 'alice@example.com';

-- Uses index: range scan
SELECT * FROM users WHERE email BETWEEN 'a' AND 'c';

-- Uses index: ORDER BY
SELECT * FROM users ORDER BY email LIMIT 10;

When to use B-Tree: Equality lookups, range queries (BETWEEN, >, <), ORDER BY, and GROUP BY on the indexed column. This is your default choice — start here unless you’ve got a specific reason not to.

When to avoid B-Tree: Full-text search on large text columns (use GIN instead), exact-match-only lookups on large hashable values (Hash is smaller), or very large append-only time-series tables (BRIN is 99% smaller).

Composite B-Tree Indexes

Column order matters. A composite index on (a, b, c) supports queries on a, (a, b), and (a, b, c) — but NOT queries on b alone or (b, c). The leading column is the entry point; without it, the index is useless.

CREATE INDEX idx_orders_customer_date ON orders(customer_id, created_at);

-- Uses index: matches leading column
SELECT * FROM orders WHERE customer_id = 42;

-- Uses index: matches leading columns
SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2024-01-01';

-- Does NOT use index: skips leading column
SELECT * FROM orders WHERE created_at > '2024-01-01';

The rule for column order: put the column with the highest selectivity (most distinct values) first, unless all queries filter on a specific column. If 90% of your queries filter on customer_id and then sort by created_at, the composite (customer_id, created_at) is correct even if created_at has more distinct values. For a deeper understanding of query patterns and normalization trade-offs, see the Database Normalization Guide.

Hash Indexes

Optimized for equality comparisons only. Smaller and faster than B-Trees for exact matches, but can’t support range queries or sorting. PostgreSQL supports hash indexes natively; MySQL’s InnoDB doesn’t offer a separate hash index type (it uses adaptive hash indexing internally on top of B-Tree).

CREATE INDEX idx_sessions_token ON sessions USING HASH(token);

-- Fast: equality
SELECT * FROM sessions WHERE token = 'abc123';

-- Cannot use hash index: range
SELECT * FROM sessions WHERE token > 'abc';

When to use Hash: Exact-match lookups on long strings or UUIDs where you never need range queries or sorting. Session tokens, API keys, and hash digests are good candidates. The index is smaller than a B-Tree because it stores only the hash, not the sorted value.

When to avoid Hash: If there’s any chance you’ll need range queries, ORDER BY, or prefix matching in the future. Hash indexes can’t be used for LIKE 'prefix%' queries either. For most workloads, B-Tree is the safer default — the size difference is rarely worth the lost flexibility.

GIN Indexes (Generalized Inverted Index)

Designed for multi-value columns and full-text search. A GIN index maps each element (array item, JSONB key, or token) to the rows that contain it — the same inverted-list structure that powers search engines. PostgreSQL is the primary database with mature GIN support.

-- Array containment
CREATE INDEX idx_products_tags ON products USING GIN(tags);
SELECT * FROM products WHERE tags @> ARRAY['electronics', 'wireless'];

-- JSONB search
CREATE INDEX idx_events_data ON events USING GIN(data jsonb_path_ops);
SELECT * FROM events WHERE data @> '{"status": "error"}';

-- Full-text search (PostgreSQL)
CREATE INDEX idx_articles_search ON articles USING GIN(to_tsvector('english', content));
SELECT * FROM articles WHERE to_tsvector('english', content) @@ to_tsquery('database & indexing');

When to use GIN: Arrays with @> (contains), JSONB with @> or ? (key exists), and full-text search with @@ (tsquery match). GIN is the only index type that makes these queries fast — a B-Tree can’t index an array or a JSONB document.

When to avoid GIN: GIN indexes are expensive to maintain. Each INSERT or UPDATE to a GIN-indexed column can be much slower than a B-Tree update because the inverted list must be updated for every element. If your table is write-heavy, consider the fastupdate=off option (faster queries, slower writes) or gin_pending_list_limit tuning. For read-heavy tables, GIN is excellent.

GiST Indexes (Generalized Search Tree)

A framework for building indexes on complex data types: geometric, range, and nearest-neighbor queries. GiST isn’t a single index type — it’s a template that PostgreSQL extensions (PostGIS, pg_trgm, btree_gist) implement for specific operators.

-- Geospatial (PostGIS)
CREATE INDEX idx_locations_geom ON locations USING GIST(geom);
SELECT * FROM locations WHERE ST_DWithin(geom, ST_Point(0,0)::geography, 1000);

-- Range queries
CREATE INDEX idx_reservations_period ON reservations USING GIST(period);
SELECT * FROM reservations WHERE period && daterange('2024-01-01', '2024-01-10');

When to use GiST: Geospatial queries (PostGIS), range types (daterange, tsrange), trigram fuzzy search (pg_trgm for LIKE '%term%'), and nearest-neighbor searches (<-> operator). If you’re using PostGIS, GiST is mandatory — no other index type supports spatial operators.

When to avoid GiST: Standard scalar lookups (equality, range on numbers/dates). B-Tree is faster and smaller for these. GiST also has higher maintenance cost than B-Tree for writes.

BRIN Indexes (Block Range Indexes)

Compact indexes for very large, naturally ordered tables. Instead of storing an entry per row (like B-Tree), BRIN stores only the min and max value for each block of pages. A 1-billion-row time-series table might have a BRIN index of 5 MB, compared to 20 GB for a B-Tree.

-- Time-series data: logs, events, metrics
CREATE INDEX idx_logs_created ON logs USING BRIN(created_at);

-- Size: ~1% of B-Tree, but only useful for ordered data
-- Best for: billions of rows, time-series, append-only workloads

When to use BRIN: Append-only tables with natural ordering (time-series logs, event streams, metrics). If your data is inserted in roughly sorted order by the indexed column, BRIN can prune entire blocks from a scan at ~1% of the storage cost of a B-Tree. This is the index type that makes billion-row tables queryable.

When to avoid BRIN: Tables with random access patterns or frequent updates. If the min/max range of a block changes frequently (updates scattered across the table), BRIN loses its pruning ability and degrades to a full scan. BRIN is also useless for equality lookups on high-cardinality columns — it tells you “this block might contain your value,” not “this row contains your value.”

Partial Indexes

Index only a subset of rows, reducing size and improving write performance. A partial index on WHERE active = true when 90% of queries filter on active = true is smaller and faster than a full index — and it skips the 10% of inactive rows entirely.

-- Only index active users (80% of queries filter on active)
CREATE INDEX idx_users_active_email ON users(email) WHERE active = true;

-- Only index unpaid orders for aging reports
CREATE INDEX idx_orders_unpaid ON orders(created_at) WHERE status = 'unpaid';

When to use Partial: Queries that always include a specific WHERE condition. If every query on orders filters on status = 'pending', a partial index on WHERE status = 'pending' is dramatically smaller than a full index and the planner will use it. Partial indexes also reduce write amplification — INSERTs of rows that don’t match the condition don’t touch the index.

When to avoid Partial: If queries sometimes run without the filter condition, the partial index won’t be used for those queries. You’d need a second full index, which defeats the purpose.

Covering Indexes (Index-Only Scans)

Include additional columns so the database can answer queries without touching the heap (the table’s main data storage). An index-only scan is 2-10x faster than an index scan that’s got to fetch the heap page, because it avoids random I/O.

-- PostgreSQL: INCLUDE adds columns to the index leaf
CREATE INDEX idx_orders_customer_total ON orders(customer_id) INCLUDE(total, status);

-- Query uses index only — no heap access
SELECT total, status FROM orders WHERE customer_id = 42;

-- MySQL: composite index naturally covers
CREATE INDEX idx_orders_customer_total ON orders(customer_id, total, status);

PostgreSQL vs MySQL: PostgreSQL uses the INCLUDE clause to add non-key columns to the index without making them part of the sort order. MySQL (InnoDB) gets the same effect with a composite index — the secondary index entries already contain the primary key, so a composite (customer_id, total, status) covers SELECT total, status FROM orders WHERE customer_id = 42.

When to use Covering: When a query selects a small number of columns and filters on one. The classic case is SELECT count(*) FROM orders WHERE status = 'pending' — a covering index on (status) that includes nothing extra still needs a heap fetch per row, but a partial index on WHERE status = 'pending' with a covering column can answer it as an index-only scan.

Index Selection Matrix

Index Type	Best For	Avoid When
B-Tree	Equality, range, sorting	High-cardinality text search
Hash	Exact match on large text	Range queries needed
GIN	Arrays, JSONB, full-text	Simple scalar columns
GiST	Geospatial, ranges	Standard scalar lookups
BRIN	Large ordered datasets	Random access patterns
Partial	Frequently filtered subsets	Queries scan all rows

The decision flow below shows how to pick the right index type based on your query pattern:

When NOT to Index

Not every column needs an index. Adding indexes indiscriminately is one of the most common causes of slow writes and bloated storage. Here are the cases where you should skip the index:

• Small tables (< 10,000 rows): A sequential scan of 10,000 rows takes under 1 ms on modern hardware. The query planner knows this and will ignore your index anyway, so the index wastes storage and slows writes for no benefit.
• Low-cardinality columns: A gender column with 3 values (M/F/other) or a is_active boolean can’t benefit from a B-Tree — the index returns ~50% of rows, and the planner correctly chooses a seq scan instead. Bitmap indexes (Oracle) or partial indexes (PostgreSQL) handle these better.
• Write-heavy tables with few reads: Every index adds write amplification. A table with 10 indexes and 10,000 INSERTs/sec pays 100,000 index updates/sec. If reads are rare, drop the indexes and accept seq scans. For write-heavy workloads, see the Database Replication Guide for strategies to offload reads to replicas.
• Columns never used in WHERE/JOIN/ORDER BY: If the query planner has never used an index, it’s dead weight. Audit unused indexes quarterly with pg_stat_user_indexes (PostgreSQL) or performance_schema (MySQL).
• Frequently updated columns: An index on a column that changes with every UPDATE forces the index to be rewritten on every write. Consider whether the update frequency justifies the index maintenance cost.

Common Mistakes

• Indexing every column — slows writes dramatically; indexes have maintenance cost
• Wrong column order in composites — the leading column must be the most selective
• Indexing low-cardinality columns — gender, boolean flags; bitmap indexes handle these better
• Ignoring partial indexes — indexing 100% of rows when queries always filter
• Not updating statistics — stale stats lead to bad index choices by the query planner

Monitoring Index Usage

-- PostgreSQL: find unused indexes
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelname NOT LIKE 'pg_toast%'
ORDER BY schemaname, tablename, indexname;

-- MySQL: index usage via performance_schema
SELECT object_schema, object_name, index_name, count_read
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE index_name IS NOT NULL
ORDER BY count_read DESC;

For connection setup and query execution against PostgreSQL or MySQL, see the PostgreSQL Connection Recipe and MySQL Connection Recipe.

Troubleshooting

• Index not used by the query planner: Run EXPLAIN ANALYZE and check if the planner chose a seq scan. Common causes: stale statistics (run ANALYZE table_name), low cardinality (the index returns too many rows), or the query doesn’t match the index’s leading column. For PostgreSQL, check pg_stats to see what the planner knows about your data distribution.
• Index bloat after many UPDATEs/DELETEs: B-Tree indexes don’t reclaim space from deleted entries automatically. Check bloat with pgstattuple (PostgreSQL) or mysql.innodb_metrics (MySQL). Fix with REINDEX INDEX index_name (PostgreSQL) or OPTIMIZE TABLE (MySQL). For large tables, use REINDEX CONCURRENTLY to avoid locking.
• CREATE INDEX blocks writes in production: A regular CREATE INDEX takes an ACCESS EXCLUSIVE lock — no reads or writes during the build. Use CREATE INDEX CONCURRENTLY (PostgreSQL) or ALTER TABLE ... ADD INDEX ... ALGORITHM=INPLACE (MySQL 8+) to build the index without blocking writes. It takes longer but doesn’t lock the table.
• Index scan slower than seq scan: This happens when the index has low selectivity — it returns a large percentage of rows, and the random I/O of fetching each row from the heap is slower than a sequential scan. The planner correctly chooses seq scan. Fix by making the index more selective (add columns to a composite, use a partial index, or change the leading column).
• Statistics are stale after a bulk load: After COPY or INSERT of millions of rows, the planner’s statistics are outdated and it may choose bad plans. Run ANALYZE table_name (PostgreSQL) or ANALYZE TABLE (MySQL) after bulk loads. For automation, configure autovacuum (PostgreSQL) or innodb_stats_auto_recalc (MySQL).

Index Maintenance

Indexes aren’t fire-and-forget. They need periodic maintenance to stay effective:

-- PostgreSQL: rebuild bloated indexes without locking
REINDEX INDEX CONCURRENTLY idx_orders_customer_date;

-- PostgreSQL: update statistics after bulk loads
ANALYZE orders;

-- PostgreSQL: check index bloat
SELECT schemaname, tablename, indexname,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE idx_scan > 0
ORDER BY pg_relation_size(indexrelid) DESC
LIMIT 10;

-- MySQL: rebuild table and update statistics
OPTIMIZE TABLE orders;
ANALYZE TABLE orders;

Maintenance schedule: Run ANALYZE after any bulk load of > 10% of table size. Check index bloat monthly on high-write tables. REINDEX quarterly or when bloat exceeds 30%. For time-series tables, consider partitioning by date so you can drop old partitions instead of maintaining indexes on billions of rows.

Advanced Topics

Scenario: Query Optimization for E-commerce

-- Table: orders (50M rows, 500K/day)
-- Problem: Dashboard queries take 30+ seconds

-- Query 1: Orders by customer in date range
-- Before: seq scan, 12 seconds
EXPLAIN ANALYZE SELECT * FROM orders
WHERE customer_id = 42 AND created_at >= '2026-01-01';

-- Solution: composite index
CREATE INDEX idx_orders_customer_date ON orders(customer_id, created_at DESC);
-- After: index scan, 2ms

-- Query 2: Orders by status and date (dashboard)
-- Before: seq scan + sort, 28 seconds
EXPLAIN ANALYZE SELECT * FROM orders
WHERE status = 'pending' AND created_at >= '2026-01-01'
ORDER BY created_at DESC LIMIT 50;

-- Solution: partial composite index
CREATE INDEX idx_orders_pending_date ON orders(created_at DESC)
WHERE status = 'pending';
-- Only indexes pending orders (~5% of total)
-- After: index scan, 5ms

-- Query 3: Full-text search on products
-- Before: ILIKE, 15 seconds
EXPLAIN ANALYZE SELECT * FROM products
WHERE name ILIKE '%laptop%' OR description ILIKE '%laptop%';

-- Solution: GIN index with tsvector
CREATE INDEX idx_products_fts ON products
USING GIN(to_tsvector('english', name || ' ' || description));

SELECT * FROM products
WHERE to_tsvector('english', name || ' ' || description)
  @@ to_tsquery('english', 'laptop');
-- After: 50ms

-- Query 4: Daily order count (report)
-- Before: seq scan + aggregate, 45 seconds
EXPLAIN ANALYZE SELECT DATE(created_at), count(*)
FROM orders WHERE created_at >= '2026-01-01'
GROUP BY DATE(created_at) ORDER BY 1;

-- Solution: BRIN index (data ordered by date)
CREATE INDEX idx_orders_created_brin ON orders USING BRIN(created_at);
-- Only 1% of B-Tree size
-- After: 8 seconds (acceptable for reports)

-- Query 5: JSONB on order metadata
EXPLAIN ANALYZE SELECT * FROM orders
WHERE metadata @> '{"channel": "mobile"}';

CREATE INDEX idx_orders_metadata ON orders USING GIN(metadata jsonb_path_ops);
-- After: 15ms

-- Unused index audit (quarterly):
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelname NOT LIKE 'pg_toast%'
ORDER BY pg_relation_size(indexrelid) DESC;

-- Result: 3 unused indexes totaling 2GB -> DROP
-- Impact: 15% less write overhead

Lessons from this scenario:

• Column order in composites matters enormously — (customer_id, created_at) serves both queries, but (created_at, customer_id) would only serve the date-range query.
• Partial indexes reduce size and improve writes — the pending-orders index is 5% of a full index and serves 80% of dashboard queries.
• BRIN is ideal for time-series with billions of rows — 1% of B-Tree size, and the data is naturally ordered by date.
• GIN solves full-text search and JSONB — no other index type can make these queries fast.
• Audit unused indexes quarterly — 2GB of dead indexes was 15% write overhead for zero benefit.

How do I choose between B-Tree and BRIN?

Use B-Tree for random access data with equality or range queries. Use BRIN for very large tables (billions of rows) where data is naturally ordered (time-series, append-only logs). BRIN is ~1% of B-Tree size but only useful when queries filter on the ordered column range.

Best Practices

• Start with the query, not the index. Before creating an index, run EXPLAIN ANALYZE on the slow query. Understand which filter or join is causing the seq scan, then index the column that fixes it. Creating indexes without measuring first is how tables end up with 15 indexes, 10 of which are unused.
• Use CREATE INDEX CONCURRENTLY in production. A regular CREATE INDEX locks the table against all reads and writes. On a 50M-row table, that’s minutes of downtime. CONCURRENTLY takes longer but doesn’t block writes.
• Audit unused indexes quarterly. Run pg_stat_user_indexes (PostgreSQL) or performance_schema (MySQL) and look for idx_scan = 0. Every unused index is pure write overhead with zero read benefit. Drop them.
• Prefer composite indexes over two singles. A composite (a, b) serves queries on a, (a, b), and a with ORDER BY b. Two singles on a and b serve queries on a or b independently, but the planner can only use one per query. Match the index to your actual query patterns.
• Update statistics after bulk loads. ANALYZE table_name after COPY or large INSERT batches. Stale statistics lead to bad plans — the planner may choose a seq scan when an index scan would be 100x faster.

Real-World Example: The 2AM Slow Query

A few years ago I got paged at 2AM because the checkout flow was timing out. The orders table had 80 million rows and a dashboard query — SELECT count(*) FROM orders WHERE status = 'pending' AND created_at >= now() - interval '24 hours' — was taking 45 seconds. The dashboard was fine; the problem was that this query held a lock that blocked checkout writes.

I ran EXPLAIN ANALYZE and saw a seq scan. There was a B-Tree on created_at, but the planner ignored it because status = 'pending' matched 40% of rows — too many for an index scan to be worth it. The filter combination was the issue, not either column alone.

The fix took 10 minutes: a partial composite index on (created_at) WHERE status = 'pending'. Only 2% of orders were pending, so the index was tiny (~50 MB vs 8 GB for a full B-Tree) and the query dropped to 8ms. Checkout went back to normal.

Three lessons I learned the hard way:

1. The planner isn’t broken — it’s making a rational choice. A seq scan on 40% of rows IS faster than random I/O for 32 million rows. The fix isn’t to force the index; it’s to make the index worth using (more selective, partial, or composite).
2. Partial indexes are underrated. Most teams reach for a full index by default. If your query always includes a specific filter, a partial index is smaller, faster to build, and cheaper to maintain.
3. Lock contention from slow queries is a real production risk. A 45-second query doesn’t just annoy the dashboard user — it blocks writers and can take down unrelated parts of the app that share the table.