SQL Indexing Strategies: B-Tree, Hash, Partial, and Composite Indexes

Why Indexes Matter

Without an index, the database must read every row in a table to answer a query (a sequential scan). An index is a separate data structure that maps column values to row locations, allowing the database to jump directly to matching rows.

But indexes are not free. Each index consumes disk space and slows down INSERT, UPDATE, and DELETE operations. The art of indexing is choosing the right indexes for your workload.

B-Tree Indexes

B-tree is the default and most versatile index type. It stores values in a sorted tree structure and supports:

• Equality: WHERE status = 'active'
• Range: WHERE created_at > '2026-01-01'
• Sorting: ORDER BY created_at
• Prefix matching: WHERE name LIKE 'Al%'

-- Default index type (B-tree)
CREATE INDEX idx_orders_status ON orders (status);

-- Equivalent explicit syntax
CREATE INDEX idx_orders_status ON orders USING btree (status);

How B-Trees Work

A B-tree organizes values into a balanced tree of pages. The root page points to internal pages, which point to leaf pages containing the actual values and pointers to heap tuples. Looking up a value traverses at most log(N) pages, where N is the number of indexed rows.

For a table with 10 million rows, a B-tree index lookup typically reads 3-4 pages versus scanning all pages sequentially.

Hash Indexes

Hash indexes use a hash function to map values to buckets. They only support equality comparisons:

CREATE INDEX idx_orders_uuid ON orders USING hash (order_uuid);

When to Use Hash Indexes

• The column is only ever queried with = (never <, >, BETWEEN, ORDER BY).
• The column contains long values (UUIDs, URLs) where hashing reduces the index size.

Before PostgreSQL 10, hash indexes were not crash-safe. In modern PostgreSQL they are fully WAL-logged and safe to use.

-- Good use case: UUID lookups
SELECT * FROM orders WHERE order_uuid = 'a1b2c3d4-e5f6-7890-abcd-ef1234567890';

-- Bad use case: range queries (hash index will NOT be used)
SELECT * FROM orders WHERE order_uuid > 'a1b2c3d4';

Composite (Multi-Column) Indexes

A composite index covers multiple columns. Column order matters significantly:

CREATE INDEX idx_orders_status_date ON orders (status, created_at);

This index efficiently serves:

-- Uses the index (leading column match)
SELECT * FROM orders WHERE status = 'shipped';

-- Uses the index (both columns)
SELECT * FROM orders WHERE status = 'shipped' AND created_at > '2026-01-01';

-- Does NOT use the index efficiently (skips leading column)
SELECT * FROM orders WHERE created_at > '2026-01-01';

The Left-Prefix Rule

A composite index (A, B, C) can serve queries on:

• A alone
• A, B together
• A, B, C together

But not:

• B alone
• C alone
• B, C together

Think of it like a phone book sorted by last name, then first name. You can look up everyone named “Smith” but you cannot efficiently find everyone named “Alice” regardless of last name.

Choosing Column Order

Put the most selective column first (the one with the most distinct values) when all columns use equality. For mixed equality + range queries, put equality columns first:

-- status has few distinct values, created_at is a range
-- This order is optimal:
CREATE INDEX idx_orders_status_date ON orders (status, created_at);

-- Serves: WHERE status = 'active' AND created_at BETWEEN '2026-01-01' AND '2026-06-30'
-- The index narrows by status first, then range-scans the date within that subset.

Partial Indexes

A partial index only includes rows matching a WHERE clause. This reduces index size and maintenance cost:

-- Only index active orders (90% of queries target active orders)
CREATE INDEX idx_orders_active ON orders (customer_id)
  WHERE status = 'active';

The query must include the same condition to use the index:

-- Uses the partial index
SELECT * FROM orders WHERE status = 'active' AND customer_id = 42;

-- Does NOT use the partial index
SELECT * FROM orders WHERE status = 'shipped' AND customer_id = 42;

Practical Use Cases

-- Index only unprocessed jobs
CREATE INDEX idx_jobs_pending ON jobs (created_at)
  WHERE processed_at IS NULL;

-- Index only non-deleted records (soft deletes)
CREATE INDEX idx_users_active ON users (email)
  WHERE deleted_at IS NULL;

Expression Indexes

You can index the result of an expression or function:

-- Index on lowercase email for case-insensitive lookups
CREATE INDEX idx_users_email_lower ON users (LOWER(email));

-- Query must use the same expression
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';

-- Index on extracted year for date-based partitioning
CREATE INDEX idx_orders_year ON orders (EXTRACT(YEAR FROM created_at));

SELECT * FROM orders WHERE EXTRACT(YEAR FROM created_at) = 2026;

Covering Indexes (INCLUDE)

A covering index includes extra columns so the query can be answered entirely from the index without hitting the table (an Index Only Scan):

CREATE INDEX idx_orders_covering ON orders (customer_id)
  INCLUDE (total, status);

-- This query can be answered from the index alone
SELECT total, status FROM orders WHERE customer_id = 42;

The INCLUDE columns are stored in the leaf pages but are not part of the search tree, so they do not affect lookup performance.

GIN and GiST Indexes

For specialized data types, PostgreSQL offers additional index types:

-- GIN: Generalized Inverted Index, for arrays and full-text search
CREATE INDEX idx_posts_tags ON posts USING gin (tags);
SELECT * FROM posts WHERE tags @> ARRAY['sql', 'postgres'];

-- GiST: Generalized Search Tree, for geometric and range data
CREATE INDEX idx_events_during ON events USING gist (tsrange(start_at, end_at));

Index Maintenance

Checking Index Usage

SELECT indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
WHERE schemaname = 'public'
ORDER BY idx_scan ASC;

Indexes with zero or very few scans are candidates for removal.

Rebuilding Bloated Indexes

-- Rebuild an index without locking writes (PostgreSQL)
REINDEX INDEX CONCURRENTLY idx_orders_status;

Summary

Start with B-tree indexes on columns appearing in WHERE, JOIN, and ORDER BY clauses. Use composite indexes for multi-column queries, placing equality columns before range columns. Add partial indexes to reduce overhead when queries consistently target a subset of rows. Use hash indexes for equality-only lookups on long values. Monitor index usage with pg_stat_user_indexes and remove unused indexes to reduce write overhead.