You run a query. It takes 4 seconds. You add an index. Now it takes 3 milliseconds. What just happened?

Most developers know that indexes make queries faster. Fewer know how. This post breaks open the internals — B-trees, hash indexes, composite indexes, covering indexes, and the trade-offs that come with all of them.

If you’re working with PostgreSQL or any relational database, understanding indexes is the single highest-leverage thing you can learn for performance.

What Is an Index?

An index is a separate data structure that the database maintains alongside your table. Think of it like the index at the back of a textbook — instead of reading every page to find “B-tree,” you look up the term in the index, get a page number, and jump straight there.

In database terms: without an index, the engine performs a sequential scan — it reads every single row in the table to find matches. With an index, it performs an index scan — it navigates a sorted lookup structure to find the rows it needs, then fetches only those rows from the table.

For a table with 10 million rows, that’s the difference between checking 10 million rows and checking maybe 3 or 4 tree nodes.

B-Tree: The Default Index

When you run CREATE INDEX in PostgreSQL, MySQL, or virtually any relational database, you get a B-tree index by default. B-tree stands for “balanced tree,” and it’s the workhorse of database indexing.

Here’s how a B-tree looks conceptually for an indexed age column:

                    ┌─────────────┐
                    │   [30, 60]  │              ← Root node
                    └──┬────┬────┬┘
                       │    │    │
            ┌──────────┘    │    └──────────┐
            ▼               ▼               ▼
     ┌────────────┐  ┌────────────┐  ┌────────────┐
     │ [10, 20]   │  │ [40, 50]   │  │ [70, 80]   │   ← Internal nodes
     └─┬───┬───┬──┘  └─┬───┬───┬──┘  └─┬───┬───┬──┘
       │   │   │        │   │   │        │   │   │
       ▼   ▼   ▼        ▼   ▼   ▼        ▼   ▼   ▼
      ┌─┐ ┌─┐ ┌─┐     ┌─┐ ┌─┐ ┌─┐     ┌─┐ ┌─┐ ┌─┐
      │5│ │15│ │25│    │35│ │45│ │55│    │65│ │75│ │85│  ← Leaf nodes
      └─┘ └─┘ └─┘     └─┘ └─┘ └─┘     └─┘ └─┘ └─┘      (point to
                                                           table rows)

How a lookup works: Say you’re searching for age = 45.

1. Start at the root [30, 60]. 45 is between 30 and 60, so go to the middle child.
2. Reach [40, 50]. 45 is between 40 and 50, so go to the middle child.
3. Arrive at the leaf node containing 45. This leaf stores a pointer to the actual row on disk.

That’s 3 steps to find a value in a tree that could hold millions of entries. The time complexity is O(log n) — for 10 million rows, that’s roughly 23 comparisons instead of 10 million.

B-trees are sorted, which makes them excellent for:

• Equality lookups (WHERE age = 30)
• Range queries (WHERE age BETWEEN 20 AND 40)
• Sorting (ORDER BY age)
• Min/max (SELECT MIN(age))

The leaf nodes are also linked together in order, so range scans can walk the leaves sequentially without jumping back up the tree.

Hash Indexes

Hash indexes use a hash function to map values directly to bucket locations. They’re conceptually simpler: compute a hash, jump to the bucket, find the row.

CREATE INDEX idx_email_hash ON users USING hash (email);

Hash indexes are fast for exact equality lookups only (WHERE email = 'user@example.com'). They cannot help with range queries, sorting, or partial matches.

In PostgreSQL, hash indexes were historically discouraged because they weren’t WAL-logged (crash-safe) before version 10. Since PostgreSQL 10, they’re fully supported and can be useful for large equality-only lookups where the key is long (like UUIDs or URLs) — the hash is smaller than the original value, so the index is more compact.

In practice, B-trees handle equality lookups well enough that hash indexes are rarely worth the trade-off of losing range query support.

Composite Indexes: Column Order Matters

A composite index covers multiple columns:

CREATE INDEX idx_user_lookup ON orders (user_id, status, created_at);

This creates a single B-tree sorted by user_id first, then status within each user_id, then created_at within each (user_id, status) pair.

The leftmost prefix rule determines which queries can use this index:

Query	Uses index?
WHERE user_id = 5	✅ Yes
WHERE user_id = 5 AND status = 'active'	✅ Yes
WHERE user_id = 5 AND status = 'active' AND created_at > '2026-01-01'	✅ Yes (full index)
WHERE status = 'active'	❌ No (skips first column)
WHERE user_id = 5 AND created_at > '2026-01-01'	⚠️ Partial (uses user_id only)

Think of it like a phone book sorted by last name, then first name. You can look up everyone named “Smith,” or “Smith, John,” but you can’t efficiently look up everyone named “John” across all last names.

Put your most selective and most frequently filtered column first.

Covering Indexes and Index-Only Scans

Normally, the database finds a row pointer in the index, then goes to the table to fetch the full row. That second trip is called a “heap fetch.” A covering index includes all the columns the query needs, eliminating the heap fetch entirely.

CREATE INDEX idx_covering ON orders (user_id) INCLUDE (total, status);

Now a query like SELECT total, status FROM orders WHERE user_id = 5 can be answered entirely from the index. PostgreSQL calls this an index-only scan — it never touches the table.

You’ll see this in EXPLAIN ANALYZE output:

Index Only Scan using idx_covering on orders
  Index Cond: (user_id = 5)
  Heap Fetches: 0

Heap Fetches: 0 is the goal. If you see a high number there, the table’s visibility map may need a VACUUM.

When Indexes Hurt

Indexes aren’t free. Every index you add comes with costs:

Write overhead. Every INSERT, UPDATE, or DELETE must also update every index on that table. A table with 8 indexes means 8 additional write operations per row change. For write-heavy workloads, this adds up fast.

Storage. Indexes take disk space. A B-tree index on a large text column across 50 million rows can easily be several gigabytes. Run \di+ in psql to check index sizes.

Planner confusion. Too many indexes can cause the query planner to make suboptimal choices. It might pick a slow index scan over a faster sequential scan on a small table.

Dead index weight. Unused indexes still get updated on every write. Audit your indexes periodically — pg_stat_user_indexes shows usage counts.

Rule of thumb: index columns that appear in WHERE, JOIN, and ORDER BY clauses of your most frequent queries. Don’t index everything.

Partial Indexes

A partial index only covers rows matching a condition:

CREATE INDEX idx_active_orders ON orders (created_at)
  WHERE status = 'active';

If 95% of your orders are completed and you only ever query active ones, this index is a fraction of the size of a full index — faster to scan, cheaper to maintain, and less storage.

GIN and GiST: Beyond Simple Values

PostgreSQL offers specialized index types for complex data:

GIN (Generalized Inverted Index) is designed for values that contain multiple elements — arrays, JSONB fields, and full-text search vectors:

CREATE INDEX idx_search ON articles USING gin (to_tsvector('english', body));

GiST (Generalized Search Tree) handles geometric data, range types, and also supports full-text search. It’s more versatile but generally slower than GIN for containment queries.

If you’re doing full-text search or querying JSONB columns, GIN is usually your first choice.

Using EXPLAIN ANALYZE

The only way to know if your index is actually being used is to check:

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 5;

Look for:

• Index Scan or Index Only Scan — your index is working
• Seq Scan — full table scan, no index used (or planner chose not to)
• Bitmap Index Scan — index used to build a bitmap, then table scanned in order (common for queries returning many rows)
• Execution time — the number that actually matters

If you see a Seq Scan where you expect an index, check that the column types match, the table exists, statistics are up to date (ANALYZE), and the table is large enough for the planner to prefer an index.

Quick Reference

Index Type	Best For	Supports Range?	Supports Equality?
B-tree	General purpose	✅	✅
Hash	Exact match on large keys	❌	✅
GIN	Arrays, JSONB, full-text	❌	✅ (containment)
GiST	Geometry, ranges, full-text	✅	✅

The Mental Model

An index is a trade-off: you spend storage and write performance to buy read performance. The right indexes on the right columns, in the right order, can make a query thousands of times faster. The wrong indexes waste space and slow down writes for no benefit.

Start with EXPLAIN ANALYZE. Look at what the planner is doing. Add indexes where sequential scans are burning time on large tables. Remove indexes that nothing uses. That’s 90% of database performance tuning.