Database Indexing Explained — How Indexes Make Queries Fast

The query that takes 30 seconds#

You have a users table with 10 million rows. You run:

SELECT * FROM users WHERE email = 'mo@codelit.io';

Without an index, the database scans every single row — a full table scan. With an index on email, it finds the row in under 1 millisecond.

That's the difference an index makes: O(n) becomes O(log n).

How B-tree indexes work#

The most common index type. A balanced tree where:

• Root node points to intermediate nodes
• Intermediate nodes narrow the search range
• Leaf nodes contain the actual values and pointers to rows

For 10 million rows, a B-tree is only ~4 levels deep. Finding any value takes 4 disk reads instead of scanning millions of rows.

                    [M]
                   /   \
              [D, H]   [R, W]
             / | \     / | \
          [A-C][E-G] [N-Q][S-V][X-Z]
          (leaf nodes point to actual rows)

Types of indexes#

Single-column index#

CREATE INDEX idx_email ON users(email);

Best for: queries that filter or sort by one column.

Composite (multi-column) index#

CREATE INDEX idx_name_date ON orders(customer_id, created_at);

Column order matters. This index helps queries filtering by customer_id alone or customer_id + created_at, but NOT created_at alone (leftmost prefix rule).

Unique index#

CREATE UNIQUE INDEX idx_email ON users(email);

Enforces uniqueness + provides fast lookups. Primary keys are automatically unique indexes.

Covering index#

An index that contains all columns a query needs — the database never reads the actual table.

CREATE INDEX idx_covering ON orders(customer_id, status, total);

-- This query is served entirely from the index:
SELECT status, total FROM orders WHERE customer_id = 123;

Partial index (PostgreSQL)#

Only indexes rows matching a condition — smaller and faster.

CREATE INDEX idx_active ON users(email) WHERE active = true;

Hash index#

O(1) exact-match lookups. Cannot do range queries or sorting. Rarely used in practice since B-trees handle equality checks almost as fast.

When to add an index#

Yes, add an index when:

• A column appears frequently in WHERE clauses
• A column is used in JOIN conditions
• A column is used in ORDER BY or GROUP BY
• The table has more than a few thousand rows
• Query execution time is noticeably slow

No, don't add an index when:

• The table is small (under 1,000 rows — full scan is fine)
• The column has very low cardinality (boolean, status with 3 values)
• The table is write-heavy and rarely queried
• You already have too many indexes (each slows writes)

The cost of indexes#

Indexes aren't free:

• Storage — each index takes disk space (often 10-30% of table size)
• Write overhead — every INSERT, UPDATE, DELETE must update all indexes
• Maintenance — indexes can become fragmented over time

A table with 10 indexes means every INSERT triggers 10 index updates. For write-heavy workloads, this matters.

Reading execution plans#

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'mo@codelit.io';

Look for:

• Seq Scan — full table scan (bad for large tables)
• Index Scan — using the index (good)
• Index Only Scan — covering index, no table access (best)
• Bitmap Index Scan — combines multiple indexes

Common indexing mistakes#

Indexing every column. More indexes = slower writes. Index what queries actually use.

Wrong column order in composite indexes. Put the most selective column first (highest cardinality).

Not indexing foreign keys. JOINs on unindexed foreign keys cause full table scans on the joined table.

Ignoring query patterns. Look at your actual slow queries, not theoretical ones.

Visualize your database architecture#

See how your database, indexes, and query patterns fit into the full system — try Codelit to generate an interactive architecture diagram.

Key takeaways#

1. B-tree indexes turn O(n) scans into O(log n) lookups
2. Composite index column order matters — leftmost prefix rule
3. Covering indexes are the fastest — no table access needed
4. Every index slows writes — don't over-index
5. Use EXPLAIN ANALYZE to verify your indexes are actually being used
6. Always index foreign keys — JOINs depend on them