Why Do Indexes Speed Up Database Queries?

Overview

The author notes that modern enterprises store data in databases, whose fast access largely depends on indexes, and sets out to explain why indexes improve query speed.

Computer Storage Principles

Data persisted in a database resides on physical storage devices such as hard disks, which involve mechanical movements (seek, rotate, transfer) that add latency. Faster volatile memory (RAM) is used as a cache, but data must ultimately be stored on slower disks for durability, making disk I/O a major performance bottleneck.

How Indexes Work

Indexes act like a book's table of contents: they provide a pre‑sorted structure that lets the database locate rows without scanning the entire table. The article uses the analogy of a 500‑page dictionary where a catalog (index) lets you jump directly to relevant entries.

Binary Search

When data is sorted, binary search can be applied. Assuming fixed‑length records of 204 bytes and a block size of 1024 bytes, each block holds 5 records, so 100 000 records occupy 20 000 blocks. A full scan would examine all 20 000 blocks, whereas binary search needs only log₂(20 000) ≈ 14 comparisons, reducing the number of I/O operations by roughly 800×.

固定记录大小=204字节，块大小=1024字节

Why Indexes Speed Up Queries

Because the index stores keys in sorted order, the database can apply binary search to locate rows, especially when the index is built on a unique column such as a primary key, yielding the highest lookup efficiency.

Why Too Many Indexes Hurt Performance

Creating an index on every column adds overhead similar to scanning a full table; the index itself becomes large enough to require additional I/O, analogous to an overly detailed dictionary catalog.

Drawbacks of Indexes

Each indexed column slows write operations because inserts/updates must modify both the data row and the index.

Prefer indexing columns with unique values.

Foreign‑key columns should be indexed to aid join queries.

Indexes consume disk space, so choose indexed columns carefully.

What Is a Clustered Index

A clustered (or “聚集”) index stores rows physically in the same order as the indexed column (usually the primary key). Only one clustered index can exist per table; non‑clustered indexes store pointers to the data rows.

Clustered indexes are ideal for columns with many distinct values, range queries (BETWEEN, >, <), columns frequently used in joins or GROUP BY, and columns that benefit from ordered retrieval. They are unsuitable for frequently updated columns because row movement can be costly.

Typical Cases of Index Failure

Using OR in a WHERE clause can prevent index usage; replacing OR with IN is recommended.

Common SQL Optimization Techniques

1. Avoid Full Table Scans

Ensure columns used in ON or WHERE clauses have indexes.

For very small tables, a full scan may be cheaper than using an index.

2. Prevent Index Invalidations

Avoid functions, implicit casts, or calculations on indexed columns.

Use covering indexes (select only indexed columns) to avoid accessing the table.

3. Prefer Index‑Based Sorting

Let the index provide the order instead of sorting results after retrieval.

4. Select Only Needed Columns

Fetching fewer columns reduces I/O.

5. Minimize Temporary Table Creation

Temporary tables add overhead and should be avoided when possible.