Database Indexing: The Complete Guide to Indexes Every Developer Must Understand

-- Default index type: B-tree (balanced binary search tree)
-- Structure: sorted tree of (value, row_pointer) pairs

-- Without index on email:
-- SELECT * FROM users WHERE email = 'alice@example.com';
-- → Sequential scan: read every row, compare email (O(n))
-- 1M users: ~500K comparisons on average

-- With B-tree index on email:
CREATE INDEX idx_users_email ON users(email);
-- → Index scan: binary search through tree (O(log n))
-- 1M users: ~20 comparisons (log₂ 1,000,000 ≈ 20)

-- B-tree supports:
-- Equality: WHERE email = 'x' ✓
-- Range: WHERE age BETWEEN 18 AND 30 ✓
-- Prefix: WHERE name LIKE 'Alice%' ✓ (prefix only!)
-- Sort: ORDER BY created_at ✓ (index is already sorted)
-- NOT supported by index:
-- WHERE name LIKE '%Alice%' ✗ (leading wildcard, use full-text)
-- WHERE LOWER(email) = 'x' ✗ (function on column, use functional index)

-- Composite index: (col1, col2, col3) — left-to-right prefix rule
-- Index can be used for:
-- WHERE col1 = x ✓ (uses prefix)
-- WHERE col1 = x AND col2 = y ✓ (uses prefix)
-- WHERE col1 = x AND col2 = y AND col3 = z ✓ (full index)
-- WHERE col2 = y ✗ (skips col1 — index UNUSABLE)
-- WHERE col1 = x AND col3 = z ✓ (partial: only col1 used)

-- The (equality, range, sort, select) rule:
-- Query:
SELECT id, email FROM users
WHERE status = 'active' -- equality filter first
 AND created_at > '2026-01-01' -- range filter second
ORDER BY created_at DESC -- sort third
LIMIT 20;

-- Optimal composite + covering index:
CREATE INDEX idx_users_status_created_cover
ON users(status, created_at DESC)
INCLUDE (id, email); -- Covering: id and email included
-- PostgreSQL: Index Only Scan — never touches the table!

-- Every index adds overhead to INSERT, UPDATE, DELETE
-- For every row modified: every index on the table must be updated

-- Table with 10 indexes:
-- INSERT: writes row + updates 10 index trees
-- UPDATE (indexed column): updates row + rebuilds affected index entries
-- DELETE: removes row + removes from 10 index trees

-- Write-heavy tables: fewer indexes = faster writes
-- Bulk inserts: consider dropping indexes, bulk insert, recreate indexes

-- Finding unused indexes (PostgreSQL):
SELECT indexrelid::regclass AS index, idx_scan AS scans
FROM pg_stat_user_indexes
WHERE idx_scan = 0
 AND indisunique IS FALSE;
-- Zero scans = index that's never used = pure write overhead
-- Drop unused indexes!

-- Index size:
SELECT indexname, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes
WHERE tablename = 'orders'
ORDER BY pg_relation_size(indexrelid) DESC;