Why Indexes Exist

1. Introduction

An index is a data structure that enables the database to find rows without scanning the entire table. Just like a book's index lets you jump to the right page instead of reading every page, a database index lets the query planner locate data in O(log N) time instead of O(N). Without indexes, every query on a million-row table would require reading all million rows.

2. Why It Matters

• Query speed: A well-placed index can turn a 30-second sequential scan into a 2ms index lookup — a 15,000x improvement.
• Scalability: Without indexes, query time grows linearly with table size. With indexes, it grows logarithmically — a billion-row table is only ~30 lookups deep.
• JOIN performance: Foreign key columns without indexes cause nested loop joins to degrade to O(N×M). Indexes on FK columns enable efficient index-based joins.
• Sorting: B-tree indexes store data in sorted order, enabling the planner to skip expensive sort operations for ORDER BY queries.

3. Real-World Analogy

4. How It Works

-- Without index: sequential scan (reads ALL rows)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Seq Scan on users (cost: 0.00..25000.00 rows=1)
-- Create index
CREATE INDEX idx_users_email ON users(email);
-- With index: index scan (reads ~3 pages)
SELECT * FROM users WHERE email = 'alice@example.com';
-- Index Scan using idx_users_email (cost: 0.43..8.45 rows=1)
-- Index creation on existing large table (non-blocking)
CREATE INDEX CONCURRENTLY idx_orders_date ON orders(created_at);
-- CONCURRENTLY doesn't lock the table during creation

5. Internal Architecture

B-Tree Index Structure (default index type):
Root Node (1 page)
├── Internal Node → [key=100, key=200, key=300]
│   ├── Leaf → [1, 2, 3, ... 99]  → Heap pointers
│   ├── Leaf → [100, 101, ... 199] → Heap pointers
│   └── Leaf → [200, 201, ... 299] → Heap pointers
├── Internal Node → [key=400, key=500]
│   └── ...
└── ...
Each node is an 8KB page.
Lookup depth: log_fanout(N) where fanout ≈ 200-400
For 1 billion rows: depth ≈ 3-4 levels = 3-4 page reads
Index vs Heap:
  Index stores: (key_value, heap_pointer)
  Heap stores:  actual row data
  Index scan: traverse B-tree → get heap pointer → read row from heap
  Index-only scan: all needed columns in index → skip heap read

6. Visual Explanation

7. Practical Example

-- Finding missing indexes on FK columns
SELECT
    tc.table_name,
    kcu.column_name,
    ccu.table_name AS references_table
FROM information_schema.table_constraints tc
JOIN information_schema.key_column_usage kcu
    ON tc.constraint_name = kcu.constraint_name
JOIN information_schema.referential_constraints rc
    ON tc.constraint_name = rc.constraint_name
JOIN information_schema.constraint_column_usage ccu
    ON rc.unique_constraint_name = ccu.constraint_name
WHERE tc.constraint_type = 'FOREIGN KEY'
    AND NOT EXISTS (
        SELECT 1 FROM pg_indexes
        WHERE tablename = tc.table_name
        AND indexdef LIKE '%' || kcu.column_name || '%'
    );
-- Create missing FK indexes
CREATE INDEX idx_orders_customer_id ON orders(customer_id);
CREATE INDEX idx_order_items_order_id ON order_items(order_id);
CREATE INDEX idx_order_items_product_id ON order_items(product_id);

8. Common Mistakes

9. Quick Quiz

10. Scenario-Based Challenge

11. Debugging Exercise

CREATE INDEX idx_users_name ON users(name);
-- Query: SELECT * FROM users WHERE LOWER(name) = 'alice';
-- EXPLAIN shows Seq Scan instead of Index Scan

12. Interview Questions

13. Production Considerations

• CREATE INDEX CONCURRENTLY: Always use this for production tables. Regular CREATE INDEX locks the table for writes during creation, which can cause downtime on large tables.
• Monitor unused indexes: Query pg_stat_user_indexes to find indexes with zero scans. Each unused index adds write overhead without benefit — drop them.
• Index bloat: High-update tables cause index bloat (dead entries). Schedule REINDEX CONCURRENTLY or ensure autovacuum is properly configured.
• Disk space: Indexes can consume more disk than the table data itself. Budget accordingly and regularly audit index-to-data ratio.