Database Indexing Deep Dive

Why This Comes Up in Interviews

Every system design involves databases, and indexes are the #1 performance lever. Interviewers want to hear:

• How indexes work internally (B-Tree vs Hash vs LSM)
• When to add an index vs when NOT to (write amplification trade-off)
• Composite index design and column ordering
• How to identify missing indexes from query patterns

How Indexes Work — The Mental Model

Without index: Database reads every row to find matches (full table scan) With index: Database jumps directly to matching rows (like a book's index)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "Without Index (Full Scan)"
        T1[Row 1] --> T2[Row 2] --> T3[Row 3] --> T4[...] --> TN[Row 10M]
    end

    subgraph "With B-Tree Index (3 hops)"
        R[Root] --> I1[Internal Node]
        R --> I2[Internal Node]
        I1 --> L[Leaf → Row pointer]
    end

    style TN fill:#ef4444,color:#fff
    style L fill:#22c55e,color:#fff

Index Types

B-Tree Index (Default — 90% of cases)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    R["Root: [50]"]
    R --> L["[10, 30]"]
    R --> M["[70, 90]"]
    L --> LL["[1,5,8]"]
    L --> LM["[12,20,25]"]
    L --> LR["[35,40,45]"]
    M --> ML["[55,60,65]"]
    M --> MR["[75,80,85]"]

    style R fill:#3b82f6,color:#fff

Hash Index

Other Index Types

Composite Index Design

Rule: Left-to-right matching. Column order matters.

CREATE INDEX idx_orders ON orders(customer_id, status, created_at);

Column Ordering Rules

1. Equality conditions first (=)
2. Range conditions last (>, <, BETWEEN, LIKE 'prefix%')
3. High-cardinality columns before low-cardinality (user_id before status)

The Write Amplification Trade-off

Rule of thumb: Each index adds ~10-20% write overhead. A table with 10 indexes means every INSERT updates 10 B-Trees.

Identifying Missing Indexes

From Query Patterns

-- Slow query log shows:
SELECT * FROM orders WHERE customer_id = ? AND created_at > ? ORDER BY created_at DESC LIMIT 20;

-- Solution: composite index
CREATE INDEX idx_orders_customer_date ON orders(customer_id, created_at DESC);

Using EXPLAIN

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 123;

-- Bad: "Seq Scan on orders" (full scan)
-- Good: "Index Scan using idx_orders_customer" 

-- Key metrics:
--   Actual rows: how many rows examined
--   Planning time vs Execution time
--   "Rows Removed by Filter" = wasted work

Index Anti-Patterns

Interview Cheat Sheet

Back-of-Envelope: Index Size

Table: 100M rows, indexed column is BIGINT (8 bytes)

Was this helpful?

Yes Needs more

Thanks for your feedback!

Discussion

Markdown supported Post

Sign in to join the discussion Sign In

Loading comments...