Index Basics — Explain what an index is and why it helps (conceptual) - SQL

SECTION 1

Historical Context & Motivation

The concept of an index predates computers entirely — think of the alphabetical index at the back of a textbook, which allows you to jump directly to a relevant page rather than reading cover to cover. When relational databases emerged in the 1970s, their designers recognized that storing data in flat, unordered heaps would make queries painfully slow as tables grew. The fundamental problem was simple: without additional structure, the only way to find a specific row is to examine every row in the table — an operation called a full table scan. As data volumes exploded from kilobytes to terabytes, this linear search approach became a critical bottleneck that demanded a more efficient solution.

1970 • Codd's Relational Model

Edgar F. Codd publishes his seminal paper at IBM, defining relational algebra and the conceptual foundation for SQL. Early prototypes stored tuples in flat files with no indexing, revealing immediate performance challenges.

1972 • B-Tree Invention

Rudolf Bayer and Edward McCreight introduce the B-tree — a self-balancing tree structure optimized for disk-based storage. This data structure would become the backbone of nearly all relational database indexes.

1979 • Oracle V2 and System R

The first commercial SQL databases ship with B-tree index support built in, proving that auxiliary index structures could deliver orders-of-magnitude speedups for real-world workloads.

1986 • SQL Standardization (ANSI SQL-86)

The first ANSI SQL standard is ratified. Although indexing is left as an implementation detail rather than a standard clause, the CREATE INDEX syntax becomes ubiquitous across vendors.

2000s+ • Modern Index Diversity

Databases adopt hash indexes, GiST, GIN, bitmap indexes, and columnar storage indexes. Query optimizers become sophisticated enough to automatically select among multiple indexes per query.

The core question that drove all of this innovation remains relevant today: how can we locate specific rows in a table without examining every single row? This is fundamentally a search problem, and as you will see, the answer draws directly on data structures and algorithms you have studied — particularly balanced search trees and their asymptotic guarantees.

SECTION 2

Core Principles & Definitions

An index in a relational database is a separate, auxiliary data structure that maintains a sorted or hashed mapping from column values (the search key) to the physical locations of the corresponding rows on disk. Rather than replacing or reorganizing the original table data, an index sits alongside the heap file — the unsorted collection of data pages — and provides efficient lookup paths. The database's query optimizer decides at query planning time whether using an index is cheaper than a sequential scan, based on cost estimates that factor in table size, selectivity, and I/O patterns.

Search Key

The column or combination of columns on which the index is built. When you issue WHERE email = 'alice@example.com', the email column is the search key. A composite index uses multiple columns as a compound key.

Row Pointer (RID)

Each index entry stores a pointer — typically a row identifier consisting of a page number and slot number — that tells the storage engine exactly where the matching row lives on disk, enabling direct retrieval without scanning.

Sorted Structure

Most indexes maintain keys in sorted order (e.g., B-tree indexes). This ordering supports not only equality lookups (= 42) but also range queries (BETWEEN 10 AND 50) and sorted output (ORDER BY).

Trade-off: Space & Write Cost

Indexes accelerate reads but impose overhead on writes. Every INSERT, UPDATE, or DELETE must also update each relevant index. They also consume additional disk space, sometimes approaching the size of the table itself.

✦

KEY TAKEAWAY

Think of a database index like the card catalog in a university library. The books (rows) are arranged on shelves by acquisition date (heap order), which is useless if you are searching by author. The card catalog (index) is a separate structure, organized alphabetically by author, where each card contains a shelf location. Finding a book by author goes from walking every aisle to flipping to the right drawer and pulling a single card — but whenever the library acquires a new book, a new card must also be filed in the catalog.

SECTION 3

Visual Explanation — How an Index Accelerates Lookup

Left: without an index, the database must scan every row sequentially until it finds id = 7, resulting in O(n) I/O operations. Right: with a B-tree index, the engine traverses a balanced tree of sorted keys and follows a pointer directly to the target row, requiring only O(log n) page reads.

The diagram above captures the essential dichotomy. On the left, the table is stored as an unordered heap file — rows are appended in insertion order with no regard for the value of id. To satisfy SELECT * FROM users WHERE id = 7, the engine must perform a sequential scan through every data page. On the right, the B-tree index organizes key values into a balanced tree where each internal node contains multiple keys and child pointers, enabling the engine to eliminate large portions of the search space at each level. The leaf node contains the row identifier (RID) — a (page, slot) pair — which lets the storage manager fetch the exact data page containing the target row in a single disk read.

SECTION 4

Mathematical Framework — Why Indexes Are Fast

The performance advantage of an index can be understood rigorously through asymptotic analysis. A full table scan has linear time complexity in the number of data pages, while a B-tree index lookup has logarithmic time complexity measured in tree levels traversed. The key insight is that the logarithm's base is the fan-out of the tree — the number of child pointers per node — which for disk-based B-trees is typically in the hundreds, making the tree extremely shallow even for billions of rows.

FULL TABLE SCAN COST

Cost_scan = ⌈N / R⌉ = P (page reads)

Where N = total number of rows, R = rows per page, and P = total data pages. Every page must be read from disk, so cost grows linearly with table size.

B-TREE INDEX LOOKUP COST

Cost_index = ⌈log_f(N)⌉ + 1 (page reads)

Where f = fan-out (number of keys per node, typically 100–500), N = total rows. The ⌈ $\log_f$ (N)⌉ term is the tree height (number of index pages traversed), and the +1 accounts for the final data page fetch.

SPEEDUP RATIO

Speedup = P / (⌈log_f(N)⌉ + 1)

For N = 10⁶ rows, R = 100 rows/page → P = 10,000 pages. With f = 200, ⌈log₂₀₀(10⁶)⌉ = ⌈2.6⌉ = 3. So Speedup = 10,000 / (3 + 1) = 2,500× fewer page reads.

The critical takeaway from these equations is that the fan-out f is not a small constant like 2 (as in a binary tree). Because B-tree nodes are sized to match disk pages (typically 4–16 KB), each node can hold hundreds of keys and pointers. A B-tree with fan-out 200 can index 200³ = 8 × 10⁶ rows in just 3 levels, and 200⁴ = 1.6 × 10⁹ rows in 4 levels. This is why even tables with billions of rows can be queried with a handful of disk reads when the right index exists.

SECTION 5

Detailed Breakdown — Types of Indexes

While the B-tree is the default index structure in most relational databases, several alternative index types exist, each optimized for different access patterns. Understanding when each type excels is essential for effective schema design. The following diagram and table summarize the most common index types and their characteristics.

Six common index types. The B-tree is the default workhorse. Hash indexes excel at point lookups. Clustered indexes physically reorder table data, and covering indexes avoid the final table lookup entirely by including all required columns in the index itself.

Index Type	Best For	Equality (=)	Range (<, >)	Sort (ORDER BY)
B-tree	General purpose	✓ Fast	✓ Fast	✓ Supported
Hash	Point lookups	✓ Fastest	✗ No	✗ No
Bitmap	Low cardinality	✓ Fast	✓ Via OR	✗ No
Clustered	Range scans on PK	✓ Fast	✓ Very Fast	✓ Natural
GIN	Full-text, arrays	✓ Contains	✗ No	✗ No

Index type capabilities comparison

SECTION 6

Worked Example — Creating and Reasoning About an Index

Consider a customers table with 1,000,000 rows. Each row is approximately 200 bytes, and the database uses 8 KB pages. We frequently run the query SELECT * FROM customers WHERE last_name = 'Zhang' and want to understand whether creating an index on last_name is worthwhile. Let us walk through the analysis.

Index Cost-Benefit Analysis for a Customer Lookup Query

1
Step 1 — Calculate Table Size Without Index

Each page holds 8,192 / 200 ≈ 40 rows. With 1,000,000 rows, the table occupies ⌈1,000,000 / 40⌉ = 25,000 data pages. A full table scan must read all 25,000 pages.

P = 25,000 page reads for a full scan
2
Step 2 — Estimate B-tree Index Height

Assume each index entry (last_name key + RID pointer) is approximately 40 bytes. An 8 KB node holds ⌊8,192 / 40⌋ ≈ 200 entries, giving fan-out f = 200. The tree height is ⌈log₂₀₀(1,000,000)⌉ = ⌈2.61⌉ = 3 levels.

Tree height h = 3 levels
3
Step 3 — Count Page Reads for Indexed Lookup

An equality lookup traverses 3 index pages (one per tree level) to reach the leaf, then follows the RID pointer to read 1 data page. If the root node is cached in the buffer pool (common), this drops to 2 index reads + 1 data read = 3 total disk I/Os.

Cost_index = 3 + 1 = 4 page reads (3 with caching)
4
Step 4 — Compute Speedup

Speedup = 25,000 / 4 = 6,250×. Even with a conservative estimate, the indexed lookup is thousands of times faster. If each page read takes 10 ms on spinning disk, the scan takes 250 seconds while the index lookup takes 40 milliseconds — a difference between an unacceptable wait and an instant response.

Speedup ≈ 6,250× (250 s → 0.04 s)
5
Step 5 — Assess Write Overhead

Each INSERT into customers must now also insert a key into the B-tree, requiring 3–4 additional page reads/writes. For a table with infrequent writes but frequent last_name lookups, this overhead is negligible. If writes dominated the workload, we would need to weigh the write penalty more carefully.

Write overhead: ~3–4 extra I/Os per INSERT — acceptable for read-heavy workloads

💡

The SQL

Creating this index is a single DDL statement: CREATE INDEX idx_customers_last_name ON customers(last_name); — the database engine handles all tree construction, balancing, and maintenance internally. You can verify the optimizer's plan by running EXPLAIN ANALYZE SELECT * FROM customers WHERE last_name = 'Zhang'; before and after index creation.

SECTION 7

Strengths, Limitations, and Trade-offs

Indexes are not a free lunch. While the read performance benefits are dramatic, every index introduces costs that must be weighed against the workload profile. A common mistake among novice database administrators is to create an index on every column, which can degrade write performance, consume excessive disk space, and confuse the query optimizer. The following table summarizes the key trade-offs.

Dimension	Benefit of Indexing	Cost of Indexing
Query Speed	O(log n) point lookups and range scans replace O(n) full scans; can reduce query time from minutes to milliseconds	No inherent cost to read queries, but the optimizer may choose a suboptimal index if multiple exist
Write Performance	Unique indexes enforce constraints without full scans	Every INSERT/UPDATE/DELETE must maintain all indexes on the table, adding I/O and latch contention
Disk Space	Covering indexes can eliminate data page reads entirely	Each index can consume 10–30% of the base table size; composite indexes are larger
Maintenance	Self-balancing trees require no manual reorganization	Index bloat from fragmentation may require periodic REINDEX or REBUILD operations
Optimizer Complexity	More indexes give the optimizer more plan choices	Too many indexes increase planning time and risk suboptimal plans due to stale statistics

Index trade-off matrix

✦

KEY TAKEAWAY

An index is like a cache in systems design — it trades space and write amplification for dramatically faster reads. Just as adding too many caches creates coherency headaches, adding too many indexes creates write bottlenecks. The art of indexing lies in identifying the critical read paths in your application and building targeted indexes for those queries, while resisting the temptation to index everything.

SECTION 8

Connection to Advanced Topics

The conceptual foundation of indexing connects to several advanced database topics that you will encounter in upper-division courses and in production systems. Understanding basic B-tree indexes is prerequisite knowledge for query optimization, concurrency control on index structures, and distributed database design. The table below maps the concepts from this lesson to their advanced counterparts.

Basic Concept (This Lesson)	Advanced Extension	Where You'll See It
B-tree index on one column	Composite indexes with leftmost prefix rule	Multi-column WHERE clauses, covering indexes
Index speeds up reads	Cost-based query optimizer choosing among scan, index, hash join	EXPLAIN plans, join ordering, statistics
Single-row lookup via RID	Buffer pool management and page replacement policies	LRU/clock eviction, pinning hot index pages
Index write overhead	Write-ahead logging (WAL) and crash recovery for index pages	ARIES protocol, physiological logging
Index on a single node	Distributed indexes across shards, global vs. local secondary indexes	Sharding strategies, DynamoDB GSIs, CockroachDB

From index basics to advanced database internals

As you progress, you will learn that the query optimizer's decision of whether to use an index is itself a fascinating algorithmic problem. For queries that return a large fraction of the table — say 30% or more — the optimizer often determines that a sequential scan is cheaper than an index scan because sequential I/O is far faster than the random I/O pattern produced by following scattered RID pointers. This concept, known as selectivity, is central to understanding when indexes help and when they do not. In advanced courses, you will study how the optimizer estimates selectivity from column statistics (histograms, distinct counts) maintained by ANALYZE commands.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain, in your own words, why a database engine cannot simply keep the table rows sorted by every column simultaneously. How does this limitation motivate the need for indexes as separate data structures?

Show answer

A table's rows have a single physical ordering on disk — they can be sorted by at most one column (the clustered index key) at a time. If you need fast lookups on last_name and email and created_at, you cannot physically sort the table three different ways at once. Indexes solve this by creating separate, auxiliary sorted structures (one per search key) that each maintain their own ordering and point back to the original rows via RID pointers. This is analogous to having one bookshelf but multiple card catalogs organized by different criteria.

Question 2: BASIC CALCULATION

A table has 5,000,000 rows, each 100 bytes, stored in 8 KB pages. Assuming a B-tree index with fan-out f = 250, calculate: (a) the number of data pages P, (b) the B-tree height h, and (c) the speedup of an indexed point query over a full scan.

Show answer

(a) Rows per page = ⌊8,192 / 100⌋ = 81. P = ⌈5,000,000 / 81⌉ = 61,729 pages. (b) h = ⌈log₂₅₀(5,000,000)⌉ = ⌈log(5 × 10⁶) / log(250)⌉ = ⌈6.699 / 2.398⌉ = ⌈2.79⌉ = 3. (c) Index cost = 3 + 1 = 4 page reads. Speedup = 61,729 / 4 ≈ 15,432×. The indexed lookup is over fifteen thousand times faster than a full scan.

Question 3: INTERMEDIATE

You have a transactions table with columns (id, user_id, amount, created_at, status). Your application primarily runs two queries: (1) SELECT * FROM transactions WHERE user_id = ? AND created_at > ? and (2) SELECT * FROM transactions WHERE status = 'pending'. There are 10 million rows, and the status column has only 4 distinct values. Which indexes would you recommend, and why?

Show answer

For query (1), create a composite B-tree index on (user_id, created_at). The equality predicate on user_id should come first (leftmost prefix rule), and the range predicate on created_at second, so the B-tree can efficiently narrow by user then scan the date range. For query (2), an index on status is questionable. With only 4 distinct values and 10M rows, each value matches ~2.5M rows (25% selectivity). The optimizer would likely prefer a sequential scan over following 2.5 million random RID pointers. A partial index like CREATE INDEX idx_pending ON transactions(id) WHERE status = 'pending' would be far more effective if 'pending' represents a small fraction of rows.

Question 4: APPLIED

An e-commerce application experiences acceptable read latency but INSERT throughput has degraded to 500 rows/second on the order_items table, which has 7 indexes. The DBA reports that the table receives 50 writes per second and only 2 queries per second. Diagnose the likely cause and propose a solution, explaining the index maintenance overhead conceptually.

Show answer

The write throughput is degraded because every INSERT must update all 7 indexes, multiplying the I/O cost roughly 7×. Each index update involves traversing the B-tree to find the correct leaf (3–4 page reads), potentially splitting nodes, and writing dirty pages back to disk with WAL logging. For a write-heavy workload (50 writes/s vs. 2 reads/s), the maintenance cost of 7 indexes far outweighs their read benefit. The solution is to audit index usage — most databases provide views like pg_stat_user_indexes (PostgreSQL) or sys.dm_db_index_usage_stats (SQL Server) — and drop any indexes not used by the 2 frequent queries. Reducing to 2–3 targeted indexes would approximately halve the write I/O.

Question 5: CRITICAL THINKING

A colleague argues: "Since SSDs have eliminated the seek time penalty of random I/O, indexes are no longer necessary — we can just do full table scans on everything." Construct a rigorous counterargument. Consider both the asymptotic complexity perspective and practical hardware characteristics. Are there scenarios where your colleague might be partially correct?

Show answer

The colleague is wrong in general but right at the margins. While SSDs reduce random read latency from ~10 ms (HDD) to ~0.1 ms, the asymptotic gap between O(n) and O(log n) is independent of hardware speed — it is a function of data volume. For 10 billion rows, a scan still reads millions of pages even on SSD, while an index reads 4–5 pages. The constant factor improvement from SSDs shifts the crossover point (where scans become competitive) to smaller tables and lower selectivity thresholds, but it does not eliminate the exponential gap for large datasets. Furthermore, SSDs have limited write endurance (P/E cycles), and full scans consume bandwidth that could serve other queries. However, the colleague is partially correct for: (1) small tables (thousands of rows) where a scan fits in a single sequential read, (2) analytical queries scanning large fractions of data where columnar storage and vectorized execution are more appropriate than index-based row-at-a-time retrieval, and (3) in-memory databases where the I/O cost model no longer applies and CPU cache behavior dominates.

SUMMARY

Summary

A database index is an auxiliary data structure — most commonly a B-tree — that maintains a sorted mapping from search key values to physical row identifiers (RIDs) on disk. By replacing O(n) full table scans with O(log n) tree traversals, indexes deliver speedups of thousands to millions of times for point queries on large tables. The high fan-out of B-tree nodes (100–500 keys per node) keeps tree heights remarkably shallow — typically 3–4 levels even for billion-row tables.

However, indexes are not free: they consume additional disk space, impose write overhead on every INSERT, UPDATE, and DELETE, and can complicate the query optimizer's plan selection when too many exist. The art of indexing is choosing the right columns based on your workload's read/write ratio and query selectivity. Different index types — B-tree, hash, bitmap, GIN, and covering indexes — each serve different access patterns, and understanding their trade-offs is foundational to database performance engineering.