Database Indexing Interview Guide: B-Trees, Composite Indexes, Query Optimization

Updated April 16, 2026 · techinterview.org

Why Indexes Matter

A database index is a data structure that enables fast lookup of rows without scanning the entire table. Without an index, a query SELECT * FROM users WHERE email = ‘[email protected]’ on a 100M-row table requires scanning all 100M rows (full table scan). With a B-tree index on email, the query finds the matching row in O(log n) — roughly 27 comparisons. Indexes trade write overhead (maintain index on INSERT/UPDATE/DELETE) for read speed. Every table should be designed with its query patterns in mind — indexes are one of the highest-leverage performance optimizations.

B-Tree Index Internals

MySQL/PostgreSQL use B+ tree indexes (B-tree where all data lives in leaf nodes; internal nodes only store keys). Structure: a balanced tree where each node is a disk page (typically 16KB). Leaf nodes form a doubly linked list (enabling range scans). For an index on a 100M-row table with 100 rows per leaf node: ~3-4 levels deep. Reading any row requires 3-4 page reads (each from the OS page cache — fast if warm, slow if from disk). Range query: find the leftmost matching leaf node, then traverse the linked list of leaf nodes until the range ends — very efficient for ORDER BY + LIMIT queries.

Index lookup vs full table scan: MySQL’s query optimizer estimates the cost of each approach. If the query predicate matches > ~20% of rows, a full table scan may be cheaper than index lookup + row fetch (each row fetch is a random I/O to the heap). The optimizer uses table statistics (row count, cardinality per column) to decide.

Composite Indexes and Index Order

A composite index on (a, b, c) supports queries on: a alone, (a, b), or (a, b, c) — the leftmost prefix rule. It does NOT support queries on b alone or c alone (without a).

Rule: order columns in the composite index from highest to lowest cardinality if no equality predicates differ, or put equality columns first and range columns last. Example: SELECT * FROM orders WHERE user_id = 123 AND status = ‘pending’ AND created_at > ‘2024-01-01’. Index design: (user_id, status, created_at) — user_id (equality, high cardinality), then status (equality), then created_at (range — must be last in a composite index for the range to be used efficiently). An index on (created_at, user_id, status) would require a full scan of all orders since 2024-01-01 then filter by user_id — much less selective.

Covering Index

A covering index contains all columns needed by the query — no need to fetch the actual row from the heap. SELECT user_id, email FROM users WHERE last_name = ‘Smith’ with index (last_name, user_id, email): MySQL can answer this query entirely from the index (index-only scan), avoiding the heap lookup entirely. Covering indexes are one of the highest-impact optimizations: eliminates random I/O to the heap, keeping queries entirely in sequential index reads. Trade-off: wider indexes use more storage and slower writes.

Index Types

• Unique index: enforces uniqueness constraint and enables faster equality lookup (stops at first match).
• Partial index: index only rows matching a condition: CREATE INDEX ON orders (user_id) WHERE status = ‘pending’. Smaller index, only useful for queries that match the partial condition. Excellent for sparse predicates (most orders are completed; only pending orders need fast lookup).
• Functional/expression index: index on an expression: CREATE INDEX ON users (LOWER(email)). Enables case-insensitive lookups without full table scan.
• Hash index: O(1) equality lookup (no range support). PostgreSQL supports hash indexes; MySQL InnoDB uses B-tree even for hash indexes. Only useful when range queries are never needed.
• Full-text index: tokenizes and indexes text for MATCH AGAINST queries. PostgreSQL tsvector + GIN index; MySQL FULLTEXT index. For simple LIKE ‘%keyword%’ queries, full-text indexes are the only performant solution (B-tree cannot accelerate leading-wildcard LIKE).
• Spatial/GIS index: R-tree index for geospatial queries (PostGIS GIST index, MySQL spatial index). Enables efficient “points within radius” queries.

Query Optimization Checklist

EXPLAIN plan: always check EXPLAIN before optimizing. Look for: type (ALL = full scan, ref = index lookup, eq_ref = unique index lookup), rows (estimated rows scanned), Extra (Using index = covering index; Using filesort = sort not using index).

N+1 query problem: fetching a list of N objects then making N individual queries for related data. Solution: JOIN or batch fetch. ORM users: use eager loading (Django select_related, Rails includes).

SELECT * anti-pattern: fetches all columns including large BLOB/TEXT columns. Select only needed columns — allows covering index usage.

Leading wildcard LIKE: LIKE ‘%keyword’ cannot use a B-tree index (must scan all leaf nodes). Solution: full-text search, or reverse the string and use a trailing-wildcard LIKE on the reversed value.

Functions on indexed columns: WHERE YEAR(created_at) = 2024 disables index use (function applied before comparison). Solution: WHERE created_at BETWEEN ‘2024-01-01’ AND ‘2024-12-31’.

Index selectivity: low-selectivity indexes (gender: male/female = 50% of rows) are rarely used by the optimizer. High-selectivity indexes (email: nearly unique) are very efficient.

• LinkedIn Interview Guide

• Databricks Interview Guide

• Stripe Interview Guide

• Atlassian Interview Guide

• Uber Interview Guide

• Shopify Interview Guide