Why Indexes Exist

Without an index, the database answers SELECT * FROM users WHERE email = '[email protected]' by scanning every row in the table. With one billion users, that is one billion comparisons - several minutes per query. With an index on email, the database does roughly log2(1_000_000_000) = 30 comparisons. That is the entire point of indexing: turn linear scans into logarithmic lookups.

Think of an index as the alphabetical thumb tabs on a paper dictionary. The dictionary itself is the table. Without tabs, you flip page by page. With tabs, you jump directly to 'M' and search a small range.

How a B-Tree Index Works

Most relational databases (Postgres, MySQL/InnoDB, SQL Server, Oracle) use a B+ tree as the default index structure. A B+ tree is a balanced tree where:

• Each internal node holds many keys (typically 100-1000) so the tree stays shallow even for huge tables.
• All actual data pointers live in the leaf nodes, which are linked together in a sorted doubly-linked list. That linked list is what makes range scans (WHERE created_at BETWEEN ... AND ...) cheap.
• Trees stay balanced as you insert and delete: nodes split or merge to keep the height roughly log_B(N) where B is the branching factor.

---------- B+ Tree on email column ----------
                       [ M ]
                  /            \
          [ E , H ]            [ R , T ]
         /    |    \          /    |    \
      [A,B] [F,G] [I,K]    [N,P] [S]    [U,Z]
        \____\____\____ leaf list ____/____/____/

A lookup for email = 'I...' walks the tree: root -> middle child -> leaf containing I,K. The actual table row is fetched via the row pointer stored at the leaf.

For a 1 billion row table with branching factor 100, the tree height is only 5. Five page reads per lookup, even at huge scale.

Clustered vs Secondary Indexes

• A clustered index stores the table rows themselves in the leaves. There is one per table (because the data can only be sorted one way). MySQL's InnoDB makes the primary key the clustered index. Looking up by primary key returns the full row in one tree traversal.
• A secondary (non-clustered) index stores only the indexed columns plus a pointer to the row (in InnoDB, that pointer is the primary key). Looking up by a secondary index requires two tree walks: one in the secondary index, then one in the clustered index to fetch the row. Postgres calls this a 'heap fetch' and it is one reason composite/covering indexes matter.

Other Index Types

B-tree is the default but not the only choice. Different workloads need different structures.

For a web app you will use B-tree 95% of the time. Reach for the others when you have a specific access pattern (full text, geo, time series).

Composite and Covering Indexes

Real queries filter on multiple columns. Composite indexes (also called multi-column indexes) speed those up.

Leftmost-Prefix Rule

A composite index (a, b, c) can serve queries that filter on a, (a, b), or (a, b, c). It cannot help a query that filters only on b or only on c. Always order the columns in the index from highest to lowest selectivity, with WHERE = columns before WHERE > columns and finally ORDER BY columns.

-- Composite index supporting (status, created_at)
CREATE INDEX idx_orders_status_created
    ON orders (status, created_at DESC);

-- Uses the index efficiently:
SELECT id FROM orders WHERE status = 'pending' ORDER BY created_at DESC LIMIT 50;

-- Can also use the index (just the leftmost column):
SELECT id FROM orders WHERE status = 'pending';

-- Cannot use the index efficiently (no leading column):
SELECT id FROM orders WHERE created_at > NOW() - INTERVAL '1 day';

Covering Indexes

If the index already contains every column the query needs (in WHERE, ORDER BY, and SELECT), the database can answer the query without ever touching the heap. This is called an index-only scan in Postgres or a covering index in MySQL/SQL Server.

-- Covering index: includes status + created_at + id (the columns we SELECT)
CREATE INDEX idx_orders_covering
    ON orders (status, created_at DESC) INCLUDE (id, total_cents);

-- This query is now an index-only scan: no heap fetch
SELECT id, total_cents
  FROM orders
 WHERE status = 'pending'
 ORDER BY created_at DESC
 LIMIT 50;

Covering indexes are a tail-latency superpower. They commonly cut p99 latency by 5-10x for hot read paths.

Reading an EXPLAIN Plan

Every serious DB engineer reads query plans. The shape of the plan tells you whether your index is doing its job.

EXPLAIN ANALYZE
SELECT id FROM orders WHERE status = 'pending' ORDER BY created_at DESC LIMIT 50;

A Postgres plan:

---------- Postgres EXPLAIN sample ----------
Limit  (cost=0.43..18.20 rows=50 width=8) (actual time=0.05..0.42 rows=50 loops=1)
  ->  Index Scan using idx_orders_status_created on orders
        (cost=0.43..3554.21 rows=10000 width=8)
        (actual time=0.05..0.41 rows=50 loops=1)
        Index Cond: (status = 'pending')
Planning Time: 0.18 ms
Execution Time: 0.46 ms

Look for these signals:

• Seq Scan on a large table -> probably missing or unused index.
• Index Scan -> index is being used, but a heap fetch follows.
• Index Only Scan -> covering index, no heap fetch (best case).
• Bitmap Index Scan + Bitmap Heap Scan -> useful for combining multiple index conditions.
• A huge gap between the planner's estimated rows and the actual rows -> stats are stale; run ANALYZE.

Programmatic example: comparing with and without index

import pg from 'pg';
const client = new pg.Client();
await client.connect();

async function explain(sql) {
    const res = await client.query(`EXPLAIN ANALYZE ${sql}`);
    return res.rows.map((r) => r['QUERY PLAN']).join('\n');
}

console.log(await explain(
    "SELECT id FROM orders WHERE status = 'pending' ORDER BY created_at DESC LIMIT 50"
));

When Indexes Hurt

Indexes are not free. Each index pays cost on every write because the database must update the index pages alongside the table.

A practical rule: add an index when a frequent query is slow, drop indexes that are never used. Postgres exposes usage stats in pg_stat_user_indexes; MySQL has sys.schema_unused_indexes.

Common Index-Killing Patterns

These are the patterns interviewers love to ask about. Memorize them.

1. Leading wildcard in LIKE

-- Cannot use a B-tree index on email
SELECT * FROM users WHERE email LIKE '%@gmail.com';

Fix: store the reversed string and search for LIKE 'moc.liamg@%', or use a trigram index (Postgres pg_trgm) for substring search.

2. Function on indexed column

-- Index on created_at is useless: the function hides the column
SELECT * FROM events WHERE DATE(created_at) = '2026-04-26';

Fix: rewrite as a range, which preserves index usage:

SELECT * FROM events
 WHERE created_at >= '2026-04-26'
   AND created_at <  '2026-04-27';

Or create an expression index: CREATE INDEX ON events (DATE(created_at));

3. Type mismatch

-- user_id is BIGINT; comparing to a string forces an implicit cast
SELECT * FROM orders WHERE user_id = '42';

Most engines drop the index in this case. Always pass parameters with the correct type from your driver.

4. Low-cardinality columns

A boolean is_active column has only two values. An index on it is rarely useful because the planner expects to scan half the table anyway. Use a partial index that only indexes rows matching a specific value:

CREATE INDEX idx_users_active_only
    ON users (created_at)
    WHERE is_active = true;

5. OR across columns

SELECT * FROM orders WHERE status = 'pending' OR user_id = 42;

The planner often cannot use two separate indexes for an OR. Either rewrite as UNION ALL, or create a multi-column index, or accept a sequential scan if the table is small.