Why Database Indexes Speed Up Queries: Binary Search & Clustered Indexes Explained

Computer Storage Principles

Data persists on storage devices. Faster storage (RAM) is volatile and expensive; slower storage (hard disks) is non-volatile and cheaper. Databases store data on hard disks, so every query incurs disk I/O overhead.

A mechanical hard disk consists of platters divided into tracks and sectors. Reading data requires: (1) moving the head to the correct track (seek), (2) rotating the platter so the target sector passes under the head (rotational latency), and (3) reading the sector. Sequential sectors reduce head movement, but random access dominates typical workloads.

Because of this mechanical overhead, the OS never reads directly from disk into the application. Data is first transferred from disk to RAM, then the application reads from RAM.

How Indexes Work

An index is like a book's table of contents. Without it, finding a record in a 100,000-row table requires a full table scan. With an index, the database can locate the target data block directly.

Binary Search Example

Assume a table with 100,000 fixed-length records of 204 bytes each. Block size is 1,024 bytes, so each block holds 5 records ( 1024/204). The table occupies 20,000 blocks.

Linear scan worst case: 20,000 block reads.

Binary search on sorted index: log₂(20,000) ≈ 14.3 → 15 block reads.

That is roughly an 800× reduction in I/O operations. The article illustrates a binary search tree with time complexity O(log₂N) versus O(N) for linear traversal.

Why Indexes Make Queries Faster

Indexes pre-sort the indexed column values, enabling binary search (or B-tree traversal in practice). Primary keys are ideal index candidates because their uniqueness guarantees a balanced tree with minimal height.

Why Not Index Every Column

An index as large as the table itself becomes another full-scan target. The analogy: a dictionary index as long as the dictionary defeats its purpose.

Index Trade-offs

Read performance improves; write performance degrades. Every INSERT / UPDATE / DELETE requires updating the index (two writes: data + index).

Prefer unique columns for indexes.

Foreign key columns must be indexed to speed up joins.

Indexes consume disk space; choose indexed columns carefully.

Clustered Index

A clustered index (聚集索引/聚簇索引) stores table rows physically in the same order as the index key (usually the primary key). Only one clustered index per table is possible.

In a clustered index, the leaf nodes of the B-tree are the actual data pages. In a non-clustered index, leaf nodes contain pointers to data pages.

Because data is physically contiguous, range queries ( BETWEEN, >, <, >=, <=), ORDER BY, GROUP BY, and join columns benefit greatly. OLTP single-row lookups by primary key also benefit.

Avoid clustered indexes on frequently updated columns — updating the key forces the entire row to move to maintain physical order, which is costly in high-volume transaction systems.

Common Index Failure Cases

OR

conditions: even if one side has an index, the optimizer may choose a full scan. Use IN instead.

Operations on indexed columns (functions, calculations, implicit/explicit type conversion) prevent index use.

Range condition on a column prevents use of subsequent columns in a composite index.

MySQL-specific: != or <>, IS NULL / IS NOT NULL, LIKE with leading wildcard '%abc' all cause full table scans.

SQL Optimization Checklist

Avoid full table scans: ensure indexed columns in WHERE / ON clauses; small tables ( <10 rows) may scan faster.

Avoid index invalidation: no functions/calculations on indexed columns; watch composite index column order after range predicates.

Use covering indexes (index-only scans) and avoid SELECT *.

Avoid explicit sorts; let index order satisfy ORDER BY / GROUP BY.

Select only needed columns.

Minimize temporary table creation and deletion.