Database Indexing Explained: B-Trees, Composite Indexes and When Indexes Hurt

Most slow queries in real applications have the same cure: the right index. Most bad indexes have the same cause: not understanding how indexes are used. Here is the model you need, using PostgreSQL and MySQL (InnoDB) as examples.

What an index is

Without an index, finding WHERE email = 'a@b.com' means scanning every row: a full table scan, O(n). An index is a separate, sorted data structure that maps column values to row locations, so the database can jump straight to the matching rows.

The default index type almost everywhere is the B-tree (strictly a B+tree):

• a balanced tree with a high fan-out: each node holds hundreds of keys, so even billions of rows need only 3–4 levels;
• keys are kept sorted, and leaf pages are linked, so it supports equality (=), ranges (<, BETWEEN), prefix LIKE 'abc%' and ORDER BY efficiently;
• a lookup is O(log n) page reads, most of them usually already cached in memory.

MySQL InnoDB detail: the table itself is stored as a B-tree ordered by the primary key (a clustered index). Secondary indexes store the primary key value, so a secondary lookup is index → primary key → row. Keep primary keys short, and avoid random UUIDv4 keys for heavy inserts (they scatter writes); UUIDv7 or sequential IDs insert far better.

Composite indexes: column order matters

An index on (customer_id, status, created_at) is sorted by customer_id first, then status within each customer, then created_at. That gives the leftmost prefix rule:

*Some engines can do "skip scans" in special cases, but don't design around it.

How to order the columns: equality columns first, then the range or sort column. A range condition stops the index from narrowing any columns after it.

-- Query: a customer's open orders, newest first
SELECT id, total FROM orders
WHERE customer_id = 42 AND status = 'OPEN'
ORDER BY created_at DESC
LIMIT 20;

-- Index that serves the filter AND the sort (no separate sort step):
CREATE INDEX idx_orders_cust_status_created
  ON orders (customer_id, status, created_at DESC);

Covering indexes

If the index contains every column the query needs, the database can answer from the index alone, without touching the table (an index-only scan).

-- PostgreSQL: add non-key columns with INCLUDE
CREATE INDEX idx_orders_cover ON orders (customer_id, status, created_at DESC) INCLUDE (total);

Reading EXPLAIN

Always check what the planner actually does:

EXPLAIN ANALYZE SELECT ...;   -- PostgreSQL (runs the query)
EXPLAIN FORMAT=TREE SELECT ...;  -- MySQL 8

Look for:

• Seq Scan / type=ALL: a full scan (fine for small tables, bad for large ones);
• Index Scan / Index Only Scan / type=ref|range: the index is used;
• the estimated vs actual rows: big differences mean stale statistics (run ANALYZE).

Why your index isn't used

1. A function or expression on the column: WHERE LOWER(email) = ? or WHERE DATE(created_at) = ? can't use a plain index on that column. Rewrite as a range (created_at >= '2026-09-26' AND created_at < '2026-09-27') or create an expression index (CREATE INDEX ... ON users (LOWER(email))).
2. A leading wildcard: LIKE '%gmail.com' can't use a B-tree; use full-text or trigram indexes.
3. Type mismatches: comparing a string column to a number can force a conversion on every row.
4. Low selectivity: if a condition matches a large part of the table (like status = 'ACTIVE' on 90% of rows), a full scan is genuinely cheaper, and the planner is right.
5. OR across different columns may prevent a single index from being used (sometimes combined via bitmap scans).

When indexes hurt

Indexes aren't free:

• Every write updates every index. A table with 10 indexes makes each INSERT do 11 B-tree writes. Heavy-write tables need a lean set of indexes.
• Storage and memory: indexes compete with data for the buffer cache.
• Redundant indexes: (a) is redundant if (a, b) exists (for most queries). Remove unused ones: check pg_stat_user_indexes (PostgreSQL) or sys.schema_unused_indexes (MySQL).
• Low-cardinality columns (like a boolean) rarely benefit from a standalone index. A partial index can help: CREATE INDEX ... ON orders (created_at) WHERE status = 'OPEN'.

A practical workflow

1. Find the slow queries (pg_stat_statements, MySQL slow query log, APM traces).
2. EXPLAIN ANALYZE the worst ones.
3. Design an index for the filter + sort pattern (equality first, then range or sort).
4. Verify with EXPLAIN again, and measure write overhead.
5. Remove indexes that nothing uses.

Follow-up questions this topic invites — and their answers

Q: B-tree vs hash index? A: Hash indexes support only equality lookups. B-trees support equality, ranges and ordering, which is why they're the default. PostgreSQL also offers GIN (arrays, JSONB, full-text), GiST, and BRIN (huge, naturally ordered tables).

Q: Does an index on a foreign key matter? A: Yes. Joins and cascading deletes filter by the foreign key column. PostgreSQL doesn't create these automatically (MySQL InnoDB does).

Q: Why is COUNT(*) slow on big tables? A: Without a cheap way to count visible rows (MVCC means each row's visibility can differ per transaction), the database must scan an index or the table. Use approximate counts or maintained counters when exact numbers aren't required.

Q: How do indexes relate to the N+1 problem in JPA? A: They're separate problems. N+1 is too many queries (fix it with fetch joins or entity graphs); indexes make each query fast. You usually need both.

Explore more in our database fundamentals courses and the SQL interview questions.