Indexes and Query Optimization
You'll learn how databases use indexes like B-trees to speed up queries and how the query optimizer automatically selects efficient execution plans.
How Indexes Accelerate Queries
When you query a database without an index, it must scan every row in a table—like flipping through every page of a phone book to find one name. An index creates a sorted lookup structure that points directly to the data, letting the database jump straight to relevant rows.
B-tree indexes (balanced trees) are the most common type. They organize data hierarchically, allowing the database to search in logarithmic time—finding one record among millions in just a few steps, rather than checking millions of rows.
Index Types in Action
When you define an index on a column (say, user_id), the database builds a separate B-tree structure mapping each user_id value to its physical location. Queries filtering or sorting by user_id become dramatically faster because the database traverses the tree instead of scanning the entire table.
The Query Optimizer
The query optimizer is your database's smart assistant. When you write a query, it analyzes:
- Available indexes
- Table statistics (row counts, data distribution)
- Multiple possible execution strategies
It then generates an execution plan—the step-by-step instructions for retrieving data most efficiently. The optimizer might choose to use an index, perform a table scan if the index won't help, or reorder JOIN operations to minimize work.
Working Together
Indexes provide the tools, while the optimizer decides when and how to use them. A well-indexed table gives the optimizer options; a query analyzer (like EXPLAIN) shows you which plan it chose, helping you understand performance.
Key Takeaway: B-tree indexes dramatically accelerate queries by creating sorted lookup structures, while the query optimizer automatically analyzes available indexes and statistics to choose the most efficient execution plan for each query.