Understanding Database Indexing

Every experienced developer has been there: a query that took 5ms in staging takes 8 seconds in production, and the fix is a single CREATE INDEX. Indexes are the highest-leverage performance tool in a database, yet most engineers interact with them as magic. This article explains what an index actually is — the data structures underneath, when they help, when they hurt, and how to design them deliberately.

What an index is

An index is a separate data structure that stores a sorted, searchable copy of a subset of a table’s columns, along with pointers to the full rows. Instead of scanning every row, the database searches the index and jumps straight to the matching rows.

Without an index, a query like WHERE email = 'x@example.com' on a table with 10 million rows performs a sequential scan: the database reads all 10 million rows. With a B-tree index on email, it performs roughly 25 pointer hops.

B-trees: the workhorse

Most indexes are B-trees (strictly, B+ trees). A B-tree is a self-balancing tree where each node holds many keys and child pointers. It’s optimized for disk: nodes are sized to page boundaries, so reading a node is one I/O operation.

        [ 10   20   30 ]
       /       |       \
  [1 5 8]  [12 15 18]  [25 27] [35 40]

A B+ tree keeps data only in leaf nodes, which are linked together. That linkage makes range scans trivial: once you find >= 18, you walk the leaf chain forward to get 18, 20, 25, ... without revisiting internal nodes.

Why not a binary search tree? Height. A B-tree with hundreds of keys per node has a height of 3-4 for millions of rows. A binary tree of the same size has a height of ~24, meaning ~6x more disk reads.

-- Creates a B-tree index by default
CREATE INDEX idx_users_email ON users (email);

-- A clustered index (ordering the table itself)
-- on the primary key in most engines

Hash indexes: equality, fast

A hash index computes a hash of the key and stores entries in a hash table. Lookup is O(1) — one hash, one probe, done. That’s faster than a B-tree for exact-match lookups like WHERE id = 123 or WHERE token = '...'.

The catch: hash indexes support only equality. No range queries, no ORDER BY, no prefix matching. PostgreSQL’s USING HASH is rarely worth it because B-tree already handles equality well, but hash indexes shine in key-value stores like Redis and in-memory caches.

CREATE INDEX idx_sessions_token ON sessions USING hash (token);
-- Perfect for: WHERE token = 'abc'
-- Useless for: WHERE token > 'abc'

Composite indexes: order matters

A composite index on (a, b) is sorted by a first, then by b. This means it can serve queries on a, on (a, b), and on (a, b, c) — but not queries on b alone.

CREATE INDEX idx_orders_customer_created
  ON orders (customer_id, created_at DESC);

This single index serves all three of these queries efficiently:

SELECT * FROM orders WHERE customer_id = 42;
SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC;
SELECT * FROM orders WHERE customer_id = 42 AND created_at > '2026-01-01';

But this one cannot use the index:

SELECT * FROM orders WHERE created_at > '2026-01-01';

The rule of thumb: put equality columns first, range columns last.

Covering indexes and the index-only scan

An index-only scan happens when every column a query needs is already in the index. The database never touches the table at all.

CREATE INDEX idx_orders_total ON orders (customer_id, total);

SELECT customer_id, total FROM orders WHERE customer_id = 42;

Both columns come from the index, so the engine skips the heap entirely. This is often the difference between a “fast enough” query and a blazing query.

When indexes hurt

Indexes are not free. Every index adds:

• Write overhead: every INSERT/UPDATE/DELETE must update each index on the table
• Storage cost: an index is a full copy of its columns
• Query planner complexity: more indexes means more choices, and occasionally a bad one

A table with 6 indexes on it can make writes 3-5x slower. High-write tables (event logs, telemetry, message queues) should carry only the indexes that measurably matter.

Use EXPLAIN ANALYZE to check whether the planner is actually using an index, and pg_stat_user_indexes (PostgreSQL) to find unused ones.

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'x@example.com';

 Index Scan using idx_users_email on users
   Index Cond: (email = 'x@example.com'::text)
   Execution Time: 0.084 ms

Indexing for real workloads

A practical recipe:

1. Find slow queries from your query log or pg_stat_statements.
2. Add the most selective index for the most common access pattern.
3. Verify with EXPLAIN that the plan changed.
4. Monitor write latency and index bloat.
5. Drop unused indexes quarterly.

Conclusion

Indexes are the difference between a database that serves requests and one that crawls under load. Understand the three primitives — B-tree for ordered data, hash for exact matches, and composite/covering for multi-column access patterns — and you’ll design schemas that stay fast without guessing. Measure first, index second, and re-check the plan afterward.