Database Indexing and Query Optimization Interview Guide

Updated April 17, 2026 · techinterview.org

Database Indexing and Query Optimization for Interviews

Database indexing questions appear frequently in system design interviews and sometimes as standalone deep-dives. Understanding B-trees, index types, and query optimization is essential for senior engineering roles and is commonly tested at companies like Amazon, Google, Meta, and Databricks.

Why Indexes Matter

Without an index, a query scans every row (O(n)). With a B-tree index, lookup is O(log n). For a table with 100 million rows: full scan = 100M reads, B-tree index lookup = ~27 comparisons (log₂(100M) ≈ 27).

-- Without index: full table scan (100M row reads)
SELECT * FROM orders WHERE user_id = 12345;

-- With index on user_id: B-tree lookup then row fetch
-- ~27 comparisons to find the index entry, then row fetch
CREATE INDEX idx_orders_user_id ON orders(user_id);

B-Tree Index Structure

PostgreSQL, MySQL (InnoDB), and most RDBMS use B+ trees (a variant where all data lives in leaf nodes):

• Root node: Starting point, contains key ranges pointing to child nodes
• Internal nodes: Key ranges pointing to child nodes (no data)
• Leaf nodes: Actual index entries (key + row pointer/clustered data)
• Linked leaf nodes: Leaves form a doubly-linked list for range scans

B+ Tree visualization (order 3):
          [10 | 20]
         /    |    
      [5|8] [15|18] [25|30]
      ↓↓↓    ↓↓↓     ↓↓↓
   row ptrs row ptrs row ptrs  (leaf nodes linked: →→→)

Height: For n rows and branching factor b (typically 100-1000 for disk pages), height = log_b(n). A billion rows with b=1000: height = 3. Only 3 disk I/Os to find any row!

Types of Indexes

1. B-Tree Index (default)

CREATE INDEX idx_name ON table(column);
-- Supports: =, , =, BETWEEN, LIKE 'prefix%'
-- Does NOT support: LIKE '%suffix', functions on column

2. Composite (Multi-Column) Index

CREATE INDEX idx_user_date ON orders(user_id, created_at);
-- This index can serve:
-- WHERE user_id = 5                          ✓ (leftmost prefix)
-- WHERE user_id = 5 AND created_at > '2024' ✓ (full use)
-- WHERE created_at > '2024'                  ✗ (not leftmost — index not used)
-- Rule: Leftmost prefix rule — must include leading columns

3. Hash Index

-- Only supports equality (=), NOT range queries
-- Memory engine in MySQL, Redis, Hash indexes in PostgreSQL
-- O(1) lookup vs O(log n) for B-tree
-- Use case: exact-match lookups (session cache, user lookup by email)
CREATE INDEX idx_email_hash ON users USING HASH (email);

4. Covering Index

-- Index contains ALL columns needed by query — no table lookup needed
CREATE INDEX idx_covering ON orders(user_id, total_amount, status);

-- This query is served entirely from the index (no heap fetch):
SELECT user_id, total_amount, status
FROM orders WHERE user_id = 5;
-- "Index only scan" in EXPLAIN — fastest possible

5. Partial Index

-- Index only rows matching a condition — smaller, faster
CREATE INDEX idx_active_users ON users(email) WHERE is_active = true;

-- Only indexes ~10% of users (active ones)
-- Much smaller than full-table index
-- Use case: soft-deleted records, status flags

6. GIN/GiST Indexes (PostgreSQL)

-- GIN (Generalized Inverted Index): for full-text search, JSONB, arrays
CREATE INDEX idx_tags ON posts USING GIN (tags);
SELECT * FROM posts WHERE tags @> ARRAY['python'];

-- GiST (Generalized Search Tree): for geometric/spatial data
CREATE INDEX idx_location ON stores USING GIST (location);
SELECT * FROM stores WHERE location <-> POINT(40.7, -74.0) < 10;

Clustered vs Non-Clustered Indexes

Property	Clustered	Non-Clustered
Data storage	Rows stored in index order	Separate from row data
Per table	Only one allowed	Multiple allowed
Range scans	Extremely fast (rows adjacent)	Random I/O for each row
MySQL InnoDB	Primary key is clustered	Secondary indexes store PK
PostgreSQL	CLUSTER command (one-time)	All heap indexes

InnoDB secondary index overhead: Secondary indexes store the primary key value. Lookup on secondary index → get PK → lookup clustered index (double lookup). This is why wide primary keys (UUIDs) are expensive in MySQL InnoDB — every secondary index carries the UUID overhead.

EXPLAIN and Query Planning

-- EXPLAIN shows query plan without executing
EXPLAIN SELECT * FROM orders WHERE user_id = 5 AND total > 100;

-- EXPLAIN ANALYZE actually runs query and shows real timing
EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 5 AND total > 100;

-- Key things to look for:
-- Seq Scan: full table scan — missing index
-- Index Scan: using B-tree index
-- Index Only Scan: covering index — no heap fetch
-- Bitmap Heap Scan: multiple index conditions combined
-- Nested Loop / Hash Join / Merge Join: join strategies

-- Rows estimate vs actual: large difference = stale statistics
-- Run ANALYZE to update: ANALYZE orders;

Common Index Pitfalls

Functions on Indexed Columns

-- BAD: index on created_at is NOT used (function applied first)
SELECT * FROM orders WHERE YEAR(created_at) = 2024;
SELECT * FROM orders WHERE LOWER(email) = '[email protected]';

-- GOOD: rewrite to allow index use
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31';

-- GOOD: functional index (PostgreSQL)
CREATE INDEX idx_lower_email ON users (LOWER(email));
SELECT * FROM users WHERE LOWER(email) = '[email protected]';

Leading Wildcard

-- BAD: leading wildcard forces full scan
SELECT * FROM products WHERE name LIKE '%phone%';

-- GOOD: trailing wildcard uses index
SELECT * FROM products WHERE name LIKE 'phone%';

-- GOOD: for full-text search use GIN/tsvector
CREATE INDEX idx_fts ON products USING GIN(to_tsvector('english', name));
SELECT * FROM products WHERE to_tsvector('english', name) @@ 'phone';

NULL Values

-- B-tree indexes DO include NULL values in PostgreSQL
-- IS NULL / IS NOT NULL CAN use B-tree index in PostgreSQL

-- Partial index trick for sparse non-null columns:
CREATE INDEX idx_premium ON users(premium_expires) WHERE premium_expires IS NOT NULL;

Index Selectivity and Cardinality

Selectivity = unique values / total rows. High selectivity (close to 1.0) → index is valuable. Low selectivity → index scan may be slower than full table scan.

-- Check cardinality
SELECT COUNT(DISTINCT status) / COUNT(*) AS selectivity FROM orders;
-- status has values: pending/processing/completed/cancelled
-- selectivity ≈ 4/1,000,000 = 0.000004 — BAD candidate for B-tree index
-- user_id: unique per user → selectivity ≈ 1.0 — GREAT candidate

-- Rule of thumb: index is efficient when it eliminates >80% of rows
-- For status column: use partial index or bitmap index

Write Overhead of Indexes

Every index slows down INSERT/UPDATE/DELETE because the index must be maintained. Each index = one additional B-tree write per DML operation. Guidelines:

• OLTP tables: 3-5 indexes max per table
• Data warehouse (OLAP): more indexes acceptable (fewer writes)
• Bulk insert: drop indexes, insert, rebuild — much faster than online maintenance
• PostgreSQL: CREATE INDEX CONCURRENTLY to build index without locking table

Interview Questions and Answers

• Why choose a composite index over two separate indexes? Composite index can serve multi-column WHERE clauses with one lookup. Two separate indexes require a bitmap AND operation or optimizer must choose one. Composite is faster when both columns commonly appear together in queries.
• When does the optimizer ignore an index? When estimated cost of index scan + row fetch exceeds sequential scan (e.g., query returns >10-20% of table). Stale statistics cause wrong estimates — run ANALYZE.
• How do you find slow queries in production? PostgreSQL: pg_stat_statements extension, pg_stat_user_tables for sequential scan counts. MySQL: slow query log, performance_schema. Then EXPLAIN ANALYZE the top offenders.