Database Indexing Strategies: B-Trees, Hash Indexes, and Composite Keys for Production Performance

Every slow query you have ever stared at had one of two causes: missing index, or wrong index. The fix looks obvious in hindsight. In practice, picking the right index requires understanding what the storage engine is actually doing, not just cargo-culting CREATE INDEX and hoping the planner is grateful.

This article covers how B-trees, hash indexes, and GIN/GiST structures work under the hood, then moves into practical strategies that matter in production: composite key ordering, partial indexes, covering indexes, and the write amplification cost you are always trading against.

How Indexes Work Under the Hood

B-Tree Indexes

The B-tree (balanced tree) is the default index type in every major relational database. Understanding its structure explains almost every indexing rule you will encounter.

A B-tree index is a self-balancing ordered tree where:

• Leaf nodes contain the indexed key value alongside a pointer (page ID + slot number) to the actual heap row.
• Internal nodes contain separator keys that route searches to the correct leaf.
• The tree stays balanced by splitting and merging nodes on write.

                [50]
               /    \
          [25]        [75]
         /    \      /    \
      [10,20] [30,40] [60,70] [80,90]

A lookup for value 30 traverses three nodes: root, internal node, leaf. The height of a B-tree grows logarithmically. For a table with 100 million rows, you are looking at roughly five or six node reads per lookup regardless of column count. Each node is typically one disk page (8 KB in PostgreSQL).

This structure has direct implications:

• Range scans are efficient because leaf nodes are linked, so after finding the start key the engine can walk the linked list without going back up the tree.
• Equality lookups are O(log n).
• The tree must be rebalanced on every insert, update, or delete touching the indexed column.

Hash Indexes

Hash indexes store a hash of the key and a pointer to the heap row in a flat hash table. There is no ordering. The lookup is O(1) for equality. Range queries are impossible because the hash function destroys order.

PostgreSQL hash indexes were historically unreliable (not WAL-logged before version 10). They are now safe, but the narrow use case means B-tree with an equality predicate is usually the default choice. The exception is very high cardinality columns where equality lookups dominate and you want to avoid B-tree’s log overhead.

-- Hash index: only useful for equality, never for ORDER BY or range
CREATE INDEX CONCURRENTLY idx_sessions_token_hash
  ON sessions USING hash (token);

-- This query benefits:
SELECT user_id FROM sessions WHERE token = $1;

-- This query cannot use it:
SELECT user_id FROM sessions WHERE token > $1;

GIN and GiST Indexes

GIN (Generalized Inverted Index) and GiST (Generalized Search Tree) handle data types that B-trees cannot index efficiently.

GIN is designed for containment queries on composite values: arrays, JSONB, full-text tsvector. It builds an inverted index mapping each element to the set of rows that contain it. This is expensive to update (writes require touching many index entries) but makes @> (contains) and @@ (text search) fast.

-- GIN on JSONB for fast containment queries
CREATE INDEX idx_events_metadata ON events USING gin (metadata);

-- Fast:
SELECT id FROM events WHERE metadata @> '{"type": "purchase"}';

-- GIN on array column
CREATE INDEX idx_articles_tags ON articles USING gin (tags);

SELECT id FROM articles WHERE tags @> ARRAY['postgresql', 'indexing'];

GiST indexes support custom operator classes. Range types, geometric types, and full-text search all use GiST variants. The distinction from GIN: GiST is lossy (may produce false positives, requiring heap recheck) while GIN is exact.

Composite Indexes and Column Ordering

Composite indexes are the most commonly misused feature in relational databases. The rule is straightforward but easy to get wrong: the leading column determines which queries can use the index at all.

A composite index (a, b, c) can satisfy:

• Queries filtering on a
• Queries filtering on a, b
• Queries filtering on a, b, c
• Queries ordering by a or a, b or a, b, c

It cannot satisfy a query filtering only on b or only on c.

-- Table: orders(id, user_id, status, created_at, total)
CREATE INDEX idx_orders_user_status ON orders (user_id, status);

-- This uses the full index:
SELECT * FROM orders WHERE user_id = 42 AND status = 'pending';

-- This uses the index (leading column match):
SELECT * FROM orders WHERE user_id = 42;

-- This cannot use the index (skips leading column):
SELECT * FROM orders WHERE status = 'pending';

The practical rule for ordering columns in a composite index:

1. Put equality-filtered columns first.
2. Put range-filtered or sort columns last.
3. Among equality columns, put the highest-cardinality column first to prune the search space fastest.

-- Suppose queries look like:
-- WHERE tenant_id = $1 AND status = $2 AND created_at > $3

-- Good ordering: equality columns first, range column last
CREATE INDEX idx_orders_composite
  ON orders (tenant_id, status, created_at);

-- Bad ordering: range column in the middle breaks the sort
-- The index can only use (tenant_id) for the range predicate
CREATE INDEX idx_orders_bad
  ON orders (tenant_id, created_at, status);

You can verify this with EXPLAIN (ANALYZE, BUFFERS). Look for Index Cond versus Filter: conditions under Filter were not pushed into the index scan, meaning those rows were fetched from the heap and discarded after the fact.

Partial Indexes

A partial index indexes only the rows matching a WHERE clause. The index is smaller, faster to scan, and cheaper to maintain.

-- Index only active users, not the full users table
CREATE INDEX idx_users_active_email
  ON users (email)
  WHERE status = 'active';

-- This query uses the partial index:
SELECT id FROM users WHERE email = $1 AND status = 'active';

-- This query cannot use it (predicate does not match):
SELECT id FROM users WHERE email = $1 AND status = 'suspended';

Partial indexes shine in two scenarios:

Sparse conditions. If 95% of your orders rows have status = 'completed' and only 5% are pending, a full index on status is nearly useless for the common query pattern. A partial index on status = 'pending' covers only the 5% and is tiny.

Soft-delete patterns. Tables with a deleted_at column typically run all queries with WHERE deleted_at IS NULL. Index only the null rows.

CREATE INDEX idx_documents_undeleted
  ON documents (user_id, created_at)
  WHERE deleted_at IS NULL;

This index shrinks as you delete rows and grows only with new undeleted rows. In an active system where hard deletes are rare, this can be an order of magnitude smaller than an equivalent full index.

Covering Indexes and Index-Only Scans

A covering index includes all columns needed to satisfy a query, so the engine never touches the heap. This is the index-only scan.

-- Query:
SELECT email, name FROM users WHERE tenant_id = $1 AND role = 'admin';

-- A regular index on (tenant_id, role) would find matching row pointers,
-- then fetch each heap page to read email and name.

-- A covering index eliminates the heap fetch entirely:
CREATE INDEX idx_users_tenant_role_covering
  ON users (tenant_id, role)
  INCLUDE (email, name);

The INCLUDE clause (PostgreSQL 11+, SQL Server has had it longer) adds columns to the leaf nodes of the B-tree without including them in the sort key. This is important: if you added email and name to the sort key instead, you would be affecting index ordering and potentially breaking other queries that rely on this index.

Index-only scans are only possible when the visibility map confirms that all rows on a heap page are visible to all transactions. PostgreSQL’s autovacuum updates the visibility map. On tables with high write rates, autovacuum may lag and force heap fetches even on a covering index. Monitor pg_stat_user_tables.n_live_tup versus n_dead_tup and tune autovacuum thresholds accordingly.

Inspecting Query Plans

Before and after adding an index, you should read the query plan. Here is a TypeScript helper for running EXPLAIN ANALYZE in a Node.js context:

import { Pool } from "pg";

const pool = new Pool({ connectionString: process.env.DATABASE_URL });

interface PlanRow {
  "QUERY PLAN": string;
}

async function explainQuery(sql: string, params: unknown[] = []): Promise<void> {
  const result = await pool.query<PlanRow>(
    `EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) ${sql}`,
    params
  );
  for (const row of result.rows) {
    console.log(row["QUERY PLAN"]);
  }
}

// Before index: Seq Scan, ~50,000 rows examined
await explainQuery(
  "SELECT id, email FROM users WHERE tenant_id = $1 AND role = $2",
  ["tenant-abc", "admin"]
);

// After index: Index Only Scan, 3 rows examined
await explainQuery(
  "SELECT id, email FROM users WHERE tenant_id = $1 AND role = $2",
  ["tenant-abc", "admin"]
);

Key terms to look for in the plan output:

Term	Meaning
Seq Scan	Full table scan, no index used
Index Scan	Index used, but heap fetches still happen for each row
Index Only Scan	No heap fetch, all data from index leaf nodes
Bitmap Index Scan	Multiple index scans combined, then heap fetched in page order
Filter	Predicate applied after fetch (row was fetched then discarded)
Index Cond	Predicate applied inside the index scan (efficient)
Buffers: hit=N read=M	N pages from cache, M from disk

Moving a condition from Filter to Index Cond by adjusting composite key order is often the highest-leverage single change you can make to a slow query.

The Write Amplification Tradeoff

Every index you add imposes a cost on every write. An INSERT into a table with five indexes must update five index structures. An UPDATE on an indexed column must delete the old key and insert a new one. A DELETE must remove the key from all indexes.

This is write amplification: one logical write becomes multiple physical writes.

// Inserting one order row with 6 indexes:
// 1. Heap page write
// 2. idx_orders_user_status: B-tree insert
// 3. idx_orders_created_at: B-tree insert
// 4. idx_orders_status_partial: B-tree insert (if row matches predicate)
// 5. idx_orders_total: B-tree insert
// 6. idx_orders_composite: B-tree insert
// Each B-tree insert may cause page splits, which cascade upward

The tradeoff table:

Index type	Read benefit	Write cost	Maintenance cost
B-tree, single column	High for range and equality	Low per write	Moderate (bloat over time)
B-tree, composite	High for specific query patterns	Low per write	Moderate
Covering (INCLUDE)	Eliminates heap fetch	Low per write	Moderate, larger leaf pages
Partial	High for sparse conditions	Low per write	Low (fewer rows indexed)
GIN (JSONB/array)	High for containment	High per write	High (pending list, vacuum)
Hash	Moderate for equality	Low per write	Low

GIN indexes have a pending list that batches inserts and flushes periodically. This softens write amplification but introduces a latency spike during flush. For write-heavy tables with JSONB columns, consider whether the schema should be normalized instead of relying on GIN.

When to Remove Indexes

Indexes that are never used are pure overhead. PostgreSQL tracks index usage in pg_stat_user_indexes.

-- Find indexes with zero scans since last statistics reset
SELECT
  schemaname,
  tablename,
  indexname,
  idx_scan,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
  AND schemaname = 'public'
ORDER BY pg_relation_size(indexrelid) DESC;

Before dropping, verify:

• The statistics were not recently reset (pg_stat_reset()).
• The index is not used by a foreign key constraint (those rarely show up in scan stats).
• The table is not only accessed by batch jobs that run infrequently.

Drop unused indexes with DROP INDEX CONCURRENTLY to avoid locking the table.

Common Anti-Patterns

Over-indexing. A table with twelve indexes on twelve columns will have terrible write throughput. Index the columns that appear in WHERE, JOIN ON, and ORDER BY clauses of your actual query workload. Start with pg_stat_statements to find the top queries by total time.

Indexing low-cardinality columns. A B-tree index on a boolean column with 50% true / 50% false is useless for reads and costs writes. The planner will prefer a seq scan when selectivity is low. Use partial indexes instead: WHERE is_active = true if active rows are the minority.

Wrong composite key order. The most common mistake. Putting a low-selectivity column first (e.g., status) before a high-selectivity column (e.g., user_id) means the index scan examines far more entries than necessary. Order by selectivity: most selective first for equality predicates.

Forgetting CONCURRENTLY. CREATE INDEX without CONCURRENTLY takes a full table lock. On a production table with millions of rows and active traffic, this locks out all writes for minutes. Always use CONCURRENTLY in production migrations.

-- Production-safe index creation
CREATE INDEX CONCURRENTLY idx_orders_user_created
  ON orders (user_id, created_at DESC);

-- Production-safe index removal
DROP INDEX CONCURRENTLY idx_orders_old;

Implicit casts breaking index use. If a column is VARCHAR and you query it with an integer parameter, the planner may cast the column rather than the parameter, preventing index use. Keep query parameter types consistent with column types.

// Risky: if user_id column is VARCHAR, this may not use the index
const result = await pool.query(
  "SELECT * FROM users WHERE user_id = $1",
  [42] // number, not string
);

// Safe: match the column type
const result = await pool.query(
  "SELECT * FROM users WHERE user_id = $1",
  ["42"] // string
);

Production Considerations

On a live system, indexing strategy is a continuous process, not a one-time task.

Use pg_stat_statements weekly to identify queries whose total execution time is growing. Correlate with pg_stat_user_indexes to find indexes that are either missing or unused.

For tables receiving heavy writes, watch for index bloat. Deleted rows leave dead entries in B-tree leaf nodes. These are reclaimed by vacuum, but a table with high churn and lagging autovacuum will have an index twice the size it should be. Monitor pg_stat_user_tables.n_dead_tup and the output of pgstattuple for precise bloat measurement.

When adding indexes to a large production table, run CREATE INDEX CONCURRENTLY during low-traffic periods. The concurrent build takes longer and uses more I/O, but it does not block writes. Wrap it in a migration that checks if the index already exists:

DO $$
BEGIN
  IF NOT EXISTS (
    SELECT 1 FROM pg_indexes
    WHERE tablename = 'orders'
      AND indexname = 'idx_orders_user_created'
  ) THEN
    CREATE INDEX CONCURRENTLY idx_orders_user_created
      ON orders (user_id, created_at DESC);
  END IF;
END;
$$;

For multi-tenant SaaS, composite indexes with tenant_id as the leading column are almost always the right default. Every query scoped to a tenant benefits. Every index can be made partial with WHERE tenant_id IS NOT NULL if you have a global admin path that bypasses tenancy.

Closing

The mental model that helps most: an index is a sorted copy of part of your data, maintained automatically on every write. The question is never “should I add an index” but “is this sorted copy worth the write overhead for the queries I actually run.”

B-trees for range and equality, hash for equality-only high cardinality, GIN for array and JSONB containment, partial indexes for sparse conditions, covering indexes to eliminate heap fetches. Each tool fits specific access patterns. Reading query plans before and after is the only way to confirm you are getting what you expect.

The most expensive index is the one you added three years ago and forgot about.