Loading learning content...
Imagine you're searching for a specific book in a library with one million volumes. Without any organizational system, you'd need to examine each book one by one—a process that could take weeks. But with an index card catalog organized by author, title, and subject, you can locate any book in seconds. This fundamental principle—creating organized lookup structures to accelerate searches—forms the foundation of database indexing.
Database indexes are the single most impactful performance optimization in data-intensive systems. A well-designed index can transform a query that takes minutes into one that completes in milliseconds. Conversely, missing or poorly designed indexes are responsible for more production performance incidents than almost any other cause.
In this comprehensive module, we'll explore indexes from their conceptual foundations through their low-level mechanics, giving you the deep understanding needed to design indexing strategies that perform optimally at any scale.
By the end of this page, you will understand what indexes fundamentally are, why they exist, how they accelerate queries, their internal anatomy, and the critical principles that govern their design. You'll develop the mental model that separates engineers who guess at indexing from those who engineer it systematically.
To understand indexes, we must first understand the problem they solve. At its core, every database query asks a fundamental question: "Where is the data I'm looking for?"
Without indexes, databases have only one option: sequential scan (also called a full table scan). This means reading every single row in the table, examining each one to determine if it matches the query conditions.
The Mathematics of Sequential Scans:
Consider a table with N rows. A sequential scan has O(N) time complexity—the query time grows linearly with table size:
For a table with one billion rows, even if each comparison takes 1 microsecond, a sequential scan requires approximately 16 minutes. At 10 queries per second, your database becomes completely non-functional.
| Table Size | Disk Reads (Estimated) | Time at 100MB/s | Queries/Second Possible |
|---|---|---|---|
| 10,000 rows (1MB) | ~10 blocks | 10ms | ~100 QPS |
| 1 million rows (100MB) | ~1,000 blocks | 1 second | ~1 QPS |
| 100 million rows (10GB) | ~100,000 blocks | 100 seconds | ~0.01 QPS |
| 1 billion rows (100GB) | ~1,000,000 blocks | 16+ minutes | Unusable |
The Index Solution:
Indexes solve this problem by creating a secondary data structure that enables the database to locate rows without scanning the entire table. Instead of O(N) time complexity, properly indexed queries achieve O(log N) or even O(1) complexity:
This is the magic of indexing: a billion-row table requires only 30 comparisons instead of a billion. The improvement factor is on the order of 30 million—transforming impossible queries into instantaneous ones.
O(log N) complexity is extraordinarily powerful. Doubling your data only adds one more comparison. Going from 1 million to 1 billion rows only adds 10 more comparisons. This logarithmic scaling is what enables databases to serve billions of records with consistent, predictable performance.
A database index is a separate data structure that maintains an organized copy of selected column values, paired with pointers to the corresponding rows in the main table. This definition contains several crucial concepts:
1. Separate Data Structure:
An index is not part of the table itself—it's an auxiliary structure stored alongside the table. When you create an index, the database allocates new storage and builds a new data structure. This separation is fundamental to understanding index behavior and trade-offs.
2. Organized Copy:
Unlike the table data (which is often stored in insertion order or heap order), index data is organized according to a specific structure optimized for searching. The organizational structure varies by index type:
3. Selected Column Values:
An index doesn't copy the entire row—only the columns specified in the index definition. An index on email contains only email values, not names, addresses, or other columns. This selective copying is crucial for index efficiency.
4. Pointers to Rows:
Each index entry contains a pointer (often called a Row ID, tuple ID, or physical address) that tells the database exactly where to find the complete row in the main table. This pointer enables the database to go directly to the data without scanning.
A book's index lists terms alphabetically (organized copy of selected content) with page numbers (pointers to the full content). You don't read the entire book to find mentions of 'photosynthesis'—you look in the index, find the term, and go directly to pages 45, 102, and 217. Database indexes work identically: organized content with pointers to the full data.
The Formal Definition:
More formally, an index on columns (C₁, C₂, ..., Cₙ) is a data structure I that:
This formal view reveals that indexes are essentially specialized search trees or hash tables that map column values to row locations.
Understanding the physical structure of indexes is essential for reasoning about their performance characteristics. While different index types have different internal organizations, they share common structural elements.
Index Pages (Blocks):
Indexes, like tables, are stored in fixed-size pages (typically 4KB, 8KB, or 16KB depending on the database system). Each page can hold multiple index entries. The number of entries per page depends on:
Leaf Nodes and Internal Nodes:
Most index structures distinguish between:
Root Node:
The root is the entry point for all index lookups. For small indexes, the root might also be the only leaf. For larger indexes, the root routes to internal nodes, which route to leaf nodes.
Index Structure Visualization (B-tree Index on 'email' column) ┌─────────────────────┐ │ ROOT NODE │ │ [E] [M] │ ← Keys partition the search space │ ↓ ↓ │ └─────────────────────┘ │ │ ┌───────────────┘ └───────────────┐ ▼ ▼┌─────────────────┐ ┌─────────────────┐│ INTERNAL NODE │ │ INTERNAL NODE ││ [B] [C] [D] │ │ [J] [K] [L] │└─────────────────┘ └─────────────────┘ │ │ │ │ │ │ ▼ ▼ ▼ ▼ ▼ ▼┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐│ LEAF │ │ LEAF │ │ LEAF │ │ LEAF │ │ LEAF │ │ LEAF ││ │ │ │ │ │ │ │ │ │ │ ││alice │ │bob │ │carol │ │jane │ │kate │ │lisa ││→row1 │ │→row5 │ │→row2 │ │→row8 │ │→row4 │ │→row9 ││ │ │ │ │ │ │ │ │ │ │ ││amy │ │brian │ │dan │ │john │ │ken │ │luke ││→row3 │ │→row6 │ │→row7 │ │→row10│ │→row11│ │→row12│└──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘ ↔ ↔ ↔ ↔ ↔ ↔ Leaf nodes are linked for efficient range scansIndex Height (Depth):
The height of an index determines the number of page reads required to reach a leaf node. For B-tree indexes:
Because B-trees are extremely wide (hundreds to thousands of entries per node), even billion-row tables typically have index heights of only 3-4 levels. This is why B-tree lookups remain fast regardless of table size.
Fan-out:
Fan-out refers to the number of child pointers in each internal node. B-trees have high fan-out (typically 100-500 children per node), which keeps tree height low. A tree with fan-out 200 and height 3 can index 200³ = 8 million entries. With height 4, it can index 200⁴ = 1.6 billion entries.
Each level of the index requires one disk I/O operation. A height-4 B-tree index means any lookup requires at most 4 disk reads (often fewer, since the root and upper levels are typically cached in memory). Compare this to sequential scans that might require thousands or millions of disk reads.
When a query uses an index, the database executes a precise series of operations to locate the requested data. Understanding this process reveals why indexes are so effective and helps you reason about query performance.
Step-by-Step Index Lookup Process:
123456789
-- Example query that uses an indexSELECT * FROM users WHERE email = 'alice@example.com'; -- Behind the scenes, the database:-- 1. Consults the index on 'email' column-- 2. Navigates: ROOT → 'A' branch → 'AL' branch → leaf-- 3. Finds entry: ('alice@example.com', ptr_to_row_47)-- 4. Uses ptr_to_row_47 to read row 47 from the users table-- 5. Returns the complete row dataIndex-Only Scans (Covering Indexes):
In some cases, the database can skip step 6 entirely. If the index contains all the columns requested by the query, the database can return results directly from the index without accessing the main table. This is called an index-only scan or covering index.
For example, if you have an index on (email, created_at) and your query is:
SELECT email, created_at FROM users WHERE email = 'alice@example.com';
The database can satisfy the entire query from the index alone, avoiding the heap access entirely. This can double or triple query performance for read-heavy workloads.
Range Scans:
For range queries, the process is slightly different:
created_at >= '2024-01-01')The heap access (step 6) is often the most expensive part of an indexed query. Each row pointer may point to a different disk location, causing random I/O. For queries returning many rows, this random I/O can make indexed access slower than a sequential scan. This is why the query optimizer sometimes chooses sequential scans even when indexes exist.
Indexes are not free. Every index on a table creates ongoing maintenance overhead that affects write performance. Understanding these costs is crucial for making informed indexing decisions.
Write Amplification:
When you insert, update, or delete a row, the database must also update every index on that table. If a table has 5 indexes, every write operation effectively becomes 6 operations (1 table write + 5 index updates).
Insert Operations:
Update Operations:
Updates are particularly expensive if the updated columns are indexed:
Delete Operations:
of Indexes | Insert Overhead | Update Overhead* | Relative Write Speed |
|---|---|---|---|
| 0 indexes | 1x (baseline) | 1x | 100% |
| 1 index | ~1.5x | ~2x | ~65% |
| 3 indexes | ~2.5x | ~4x | ~40% |
| 5 indexes | ~4x | ~6x | ~25% |
| 10 indexes | ~7x | ~10x | ~15% |
*Update overhead varies significantly based on which columns are updated and indexed.
Storage Overhead:
Indexes consume disk space proportional to:
A typical B-tree index adds 10-30% storage overhead per indexed column. A table with 5 indexes might consume 50-150% additional storage beyond the raw table data.
A common mistake is creating indexes on every column 'just in case.' This approach devastates write performance and wastes storage. Production tables with 20+ indexes are not uncommon—and are almost always a sign of poor indexing strategy. Each index should justify its existence through measurable query performance improvements.
Indexes are not universally beneficial. Understanding when they help—and when they hurt—is essential for effective database design.
The Selectivity Threshold:
One of the most important concepts in indexing is selectivity—the fraction of rows that match a query condition. The query optimizer uses selectivity estimates to decide whether an index is worthwhile:
The exact threshold varies by database and configuration, but a common rule of thumb is:
This explains why an index on a status column with only 3 possible values rarely helps—even if you're searching for status = 'active', you might be matching 40% of the table.
The query optimizer doesn't blindly use indexes. It estimates the cost of different execution strategies and chooses the cheapest one. Sometimes the 'expensive' sequential scan is actually cheaper than the 'cheap' index lookup. Trust the optimizer, but verify with EXPLAIN ANALYZE.
Primary keys and unique indexes are special index types that enforce data integrity constraints while also providing performance benefits.
Primary Key Index:
In most database systems, defining a primary key automatically creates a unique index on the primary key column(s). In some systems (notably MySQL's InnoDB), the primary key has even greater significance:
PostgreSQL and many other systems use a different approach:
12345678910111213141516171819202122
-- Primary key creates an index automaticallyCREATE TABLE users ( id UUID PRIMARY KEY, -- Automatic unique index email VARCHAR(255), created_at TIMESTAMP); -- Explicit unique index (different from primary key)CREATE UNIQUE INDEX idx_users_email ON users(email); -- Compound primary keyCREATE TABLE order_items ( order_id INTEGER, product_id INTEGER, quantity INTEGER, PRIMARY KEY (order_id, product_id) -- Composite primary key index); -- The primary key index enables:-- 1. O(log N) lookups by id-- 2. Enforcement of uniqueness (no duplicate ids)-- 3. Foreign key relationships from other tablesUnique Indexes:
Unique indexes serve a dual purpose:
The database uses the unique index to check for duplicates during INSERT and UPDATE operations. If a duplicate is detected, the operation is rejected.
Unique vs Non-Unique Index Performance:
For single-row lookups, unique indexes are slightly faster because the database can stop searching immediately upon finding a match (it knows there can be only one). Non-unique indexes must continue checking for additional matches.
However, this difference is negligible in practice. The primary reason to create a unique index is data integrity, not performance.
Primary keys can be natural (business-meaningful like ISBN, SSN) or surrogate (artificial like auto-increment integers, UUIDs). Surrogate keys typically make better primary keys—they're immutable, compact, and avoid business logic coupling. Natural keys can still be indexed as unique secondary indexes.
One of the most important distinctions in indexing is between clustered and non-clustered (secondary) indexes. This distinction fundamentally affects storage organization and query performance.
Clustered Index:
A clustered index determines the physical storage order of table data. The leaf nodes of a clustered index contain the actual table rows, not pointers to rows elsewhere.
Non-Clustered (Secondary) Index:
A non-clustered index is a separate structure whose leaf nodes contain:
| Characteristic | Clustered Index | Non-Clustered Index |
|---|---|---|
| Number per table | Exactly one | Many (typically limited to ~999) |
| Leaf node contents | Actual row data | Indexed columns + row pointer |
| Lookup for covered queries | Single index traversal | Single index traversal |
| Lookup for non-covered queries | Single index traversal | Index traversal + heap/clustered lookup |
| Range scan efficiency | Excellent (data is contiguous) | Potentially poor (random I/O to heap) |
| Insert location | Determined by key value | Append to heap + insert into index |
| Storage overhead | None (it IS the table) | Additional storage for index structure |
Performance Implications:
Clustered Index Advantages:
Clustered Index Disadvantages:
Practical Guidance:
Random UUIDs as clustered index keys cause severe fragmentation. Each insert goes to a random location, causing constant page splits. Consider ULIDs (Universally Unique Lexicographically Sortable Identifiers) or time-prefixed UUIDs for sequential ordering while maintaining uniqueness.
We've established a comprehensive foundation for understanding database indexes. Let's consolidate the essential concepts:
What's Next:
With this conceptual foundation in place, we'll dive deep into the most important index type in the next page: B-tree indexes. You'll understand their internal structure, splitting behavior, and the specific query patterns they optimize.
You now understand what indexes fundamentally are, why they exist, and the principles governing their effectiveness. This mental model will guide every indexing decision you make as we explore specific index types and advanced strategies in the coming pages.