Course contentsShow
← System Design
Lesson 307 of 1,9199. SQL vs NoSQL TradeoffsFree lesson

Indexes and Query Optimization

How B-tree and other indexes accelerate queries while the query optimizer automatically chooses efficient execution plans.

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.