Why Database Indexes Speed Up Queries: From Storage Basics to Binary Search

Overview

Human information storage has evolved, and modern companies keep data in databases; databases offer fast data access largely because of indexes.

Computer Storage Principles

Persisted data resides on computer storage devices. Faster storage such as RAM is expensive and low‑capacity, while slower storage like hard disks provides persistence. Operating systems move data from disks to RAM before applications access it.

Hard disks consist of rotating platters, tracks, and sectors, requiring seek, rotation, and transfer steps that introduce latency.

How Indexes Work

An index acts like a book's table of contents, allowing rapid location of rows without scanning the entire table. It maps key values to data blocks, enabling the database engine to fetch only the relevant pages.

Binary Search

Binary search requires sorted data and reduces lookup steps dramatically. For example, searching 100,000 records can drop from 20,000 linear scans to about 14 comparisons, yielding roughly an 800‑fold speed improvement.

Why Indexes Speed Up Queries

Indexes store data in sorted order, enabling binary search and efficient tree traversal, especially when built on primary‑key columns, which are unique and thus produce optimal search trees.

Too Many Indexes

Excessive indexes increase write overhead and can degrade performance, similar to an overly detailed table of contents that becomes a burden.

Index Drawbacks

While indexes improve read performance, they slow writes because each insert or update must also modify the index structures.

Clustered Index

A clustered (or "clustered") index stores rows physically in the order of the indexed column; a table can have only one. Non‑clustered indexes store pointers to the data instead of the data itself.

Common SQL Optimization Techniques

Avoid full‑table scans by indexing columns used in WHERE and JOIN conditions.

Prevent index loss by not applying functions, type casts, or OR conditions on indexed columns.

Use covering indexes and avoid SELECT * to reduce I/O.

Prefer index‑ordered results to avoid costly sorting.

Minimize creation and deletion of temporary tables.