Why Database Indexes Speed Up Queries: Binary Search & Disk I/O Explained

Overview

The evolution of information storage culminates in modern databases, where fast data access is a key advantage. A major reason for this speed is the index. This article explores why indexes make database queries faster.

Computer Storage Principles

Data persists on storage devices. Faster storage (RAM) is volatile and expensive; slower storage (hard disks) is non-volatile and cheaper. Data resides on hard disks, so database access inevitably incurs disk I/O overhead.

A mechanical hard disk contains platters divided into tracks and sectors. Reading data requires three steps: (1) move the head to the correct track (seek), (2) rotate the platter to position the target sector under the head, (3) read the full sector. Sequential sectors reduce overhead, but random access is common.

Because of this mechanical latency, the OS never reads directly from disk for applications. Data is first transferred to RAM, then accessed from there. RAM has no moving parts, so access is near-instantaneous, but it loses data on power loss — hence the need for disks.

How Indexes Work

An index is like a book's table of contents. Without it, finding a character in a 500-page unordered dictionary requires scanning every page. The directory (index) lets you jump directly to the relevant page.

In a database table with 100,000 records, a full scan checks every row. An index lets the engine locate the target data block without scanning the whole table.

Binary Search

Binary search requires sorted data but drastically improves lookup efficiency. Example calculation:

Fixed record size = 204 bytes, block size = 1024 bytes

Records per block = 1024 / 204 = 5 records. 100,000 records = 20,000 blocks.

Without an algorithm, worst-case requires scanning all 20,000 blocks. With binary search on sorted values, only log₂(20,000) ≈ 14.29 ≈ 14 probes are needed. That's roughly an 800× improvement over linear scan (O(n) vs O(log n)).

For N=8, O(log₂8)=3 steps. For N=10,000, O(log₂10000)≈13 vs O(10000) linear — about 800× faster.

Why Indexes Make Queries Faster

Indexed data is pre-sorted, enabling binary search during lookup. This is why indexes should be built on unique columns like primary keys — a binary search tree built on unique values yields maximum efficiency.

Why Not Too Many Indexes?

If an index grows as large as the table itself, it becomes another structure to scan, negating its benefit. Like a dictionary whose table of contents is as long as the book — the directory's efficiency collapses.

Index Drawbacks

Indexes improve read performance but degrade write performance. Every INSERT or UPDATE requires two writes: one for the data, one for the index. Key guidelines:

Each indexed column reduces write throughput.

Prefer indexing columns with unique values.

Foreign key columns must be indexed to support cross-table joins.

Indexes consume disk space; choose indexed columns carefully.

Clustered Index

A clustered index (clustered index) means the physical row order on disk matches the logical order of the indexed column (usually the primary key). Only one clustered index per table is allowed.

In a clustered index, leaf nodes of the B-tree are the actual data pages. In a non-clustered index, leaf nodes are index entries with pointers to data blocks. Primary keys typically create a clustered index by default.

Consider clustered indexes for:

Columns with many distinct values.

Range queries using BETWEEN, >, >=, <, <=.

Columns accessed sequentially.

Large result sets.

Join or GROUP BY columns (often foreign keys).

ORDER BY / GROUP BY columns — avoids sorting because rows are already ordered.

OLTP single-row lookups via primary key.

Avoid clustered indexes on frequently updated columns — each change forces physical row movement to maintain order, which is costly in high-volume transaction systems.

Typical Index Failure Cases

Using OR in a WHERE clause prevents index usage even if one condition has an index. Prefer IN instead.

Common SQL Optimization Techniques

1. Avoid Full Table Scans

Full scans occur when:

Columns in ON or WHERE clauses lack indexes.

Table is very small (<10 rows, short rows) — index overhead exceeds scan cost.

2. Avoid Index Invalidation

Do not apply functions, calculations, or implicit/explicit type conversions on indexed columns — this forces a full scan. The storage engine cannot use index columns to the right of a range condition (e.g., if age uses a range, pos index becomes ineffective). Use covering indexes (query columns match index columns) and avoid SELECT *.

MySQL-specific cases where indexes are not used:

Inequality operators (!= or <>) trigger full scans.

IS NULL / IS NOT NULL cannot use indexes.

LIKE with leading wildcard ('%abc%') causes full scan.

3. Avoid Sorting; If Unavoidable, Use Index Order

4. Avoid Selecting Unnecessary Columns

5. Avoid Temporary Table Creation and Deletion