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

Source: https://www.techinterview.org/post/3233461821/database-indexing-interview-guide/
Updated: 2026-04-16 · 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 = 'x@y.com' 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](https://techinterview.org/linkedin-software-engineer-interview/)

- [Databricks Interview Guide](https://techinterview.org/databricks-interview-guide/)

- [Stripe Interview Guide](https://techinterview.org/stripe-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Shopify Interview Guide](https://techinterview.org/shopify-software-engineer-interview/)