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.
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.
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
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)
Sorted Structure
= 42) but also range queries (BETWEEN 10 AND 50) and sorted output (ORDER BY).Trade-off: Space & Write Cost
INSERT, UPDATE, or DELETE must also update each relevant index. They also consume additional disk space, sometimes approaching the size of the table itself.Visual Explanation — How an Index Accelerates Lookup
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.
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.
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 2003 = 8 × 106 rows in just 3 levels, and 2004 = 1.6 × 109 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.
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.
| 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 |
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.
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.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.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 |
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 |
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.
Practice Problems
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?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.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.