Home/Learn/System Design/Database Indexing

Database Indexing

Beginner

Data Management

An index is a data structure (usually B-Tree or hash) that speeds up reads by avoiding full table scans. Proper indexing is the single biggest performance lever for database-backed systems.

Overview

Without an index, a database must scan every row to find matching records (O(n)). An index creates a sorted lookup structure that enables O(log n) searches. The most common type is a B-Tree index, which supports equality, range, and prefix queries. Hash indexes are faster for exact lookups (O(1)) but do not support ranges. Composite indexes cover multiple columns and follow the leftmost prefix rule. Covering indexes include all columns needed by a query, enabling index-only scans. However, indexes have costs: they slow down writes (the index must be updated on every INSERT/UPDATE/DELETE), consume disk space, and require maintenance (reindexing, bloat management). In system design, indexing decisions directly impact query latency, throughput, and storage costs.

B-Tree vs Hash Indexes

B-Tree is the default index type — supports equality, range, sorting, and prefix queries. Hash indexes are O(1) for equality but cannot handle range queries or sorting.

SQL — B-Tree vs Hash indexes

// B-Tree index — most common, supports ranges
CREATE INDEX idx_orders_date ON orders (created_at);

SELECT * FROM orders
WHERE created_at BETWEEN '2025-01-01' AND '2025-03-31'
ORDER BY created_at DESC;
-- Uses B-Tree index for range scan + ordering

// Hash index — O(1) equality only (PostgreSQL)
CREATE INDEX idx_sessions_token ON sessions USING HASH (token);

SELECT * FROM sessions WHERE token = 'abc123';
-- Hash index: direct lookup, no range support

// B-Tree internals
//         [50]              ← root
//        /    \
//    [20,30]  [70,80]       ← internal nodes
//    / | \    / | \
//  [..] [..] [..] [..]     ← leaf nodes (sorted data pointers)
// O(log n) lookups — 4 levels can index ~1 billion rows

Composite & Covering Indexes

Composite indexes cover multiple columns. The leftmost prefix rule means the index is used only if the query filters on the leading columns. Covering indexes include all queried columns, eliminating table lookups.

SQL — composite and covering indexes

// Composite index — follows leftmost prefix rule
CREATE INDEX idx_user_status_date
  ON orders (user_id, status, created_at);

-- Uses index (all 3 leading columns match)
SELECT * FROM orders
WHERE user_id = 42 AND status = 'SHIPPED' AND created_at > '2025-01-01';

-- Uses index (leftmost prefix: user_id, status)
SELECT * FROM orders WHERE user_id = 42 AND status = 'PENDING';

-- Uses index (leftmost prefix: user_id only)
SELECT * FROM orders WHERE user_id = 42;

-- CANNOT use index (skips user_id — not a leftmost prefix)
SELECT * FROM orders WHERE status = 'SHIPPED';

// Covering index — includes all selected columns
CREATE INDEX idx_covering ON orders (user_id, status) INCLUDE (total, created_at);

SELECT status, total, created_at FROM orders WHERE user_id = 42;
-- Index-only scan: no table lookup needed → fastest possible read

Indexing Best Practices

Index columns used in WHERE, JOIN, and ORDER BY clauses. Avoid over-indexing — each index slows writes. Use EXPLAIN to verify index usage. Monitor for index bloat and unused indexes.

SQL + Monitoring — indexing best practices

// EXPLAIN ANALYZE — verify index usage
EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42;
-- Index Scan using idx_orders_user_id on orders
-- Index Cond: (user_id = 42)
-- Execution Time: 0.2 ms   (vs 150 ms full table scan)

// Find unused indexes (PostgreSQL)
SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelname NOT LIKE '%pkey%'
ORDER BY pg_relation_size(indexrelid) DESC;
-- Drop unused indexes to save space and speed up writes

// Write impact of indexes
// Table with 0 indexes: INSERT = 1x
// Table with 3 indexes: INSERT = ~2-3x slower
// Table with 10 indexes: INSERT = ~5-8x slower

// Rule of thumb:
// - OLTP tables: 3-5 well-chosen indexes
// - OLAP / read-heavy: more indexes acceptable
// - Write-heavy: minimise indexes, use batch inserts

Key Points to Remember

1B-Tree indexes support equality, range, sorting — the default choice for most queries.
2Composite indexes follow the leftmost prefix rule — column order in the index matters.
3Covering indexes include all queried columns, enabling index-only scans (fastest reads).
4Every index slows writes — balance read performance against write overhead.
5Always use EXPLAIN ANALYZE to verify queries are using indexes as expected.

Interview Questions

What is a database index and how does it improve query performance?

EasyInfosys

Explain the leftmost prefix rule for composite indexes.

MediumAmazon

What is a covering index and when would you use one?

MediumFlipkart

How do you identify and remove unused indexes in production?

MediumGoogle

Design an indexing strategy for a multi-tenant SaaS database with mixed read/write workloads.

HardAtlassian

Ask Aria about Database Indexing

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Consistent Hashing

ACID vs BASE