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.

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:

• 1,000 rows → 1,000 comparisons
• 1,000,000 rows → 1,000,000 comparisons
• 1,000,000,000 rows → 1,000,000,000 comparisons

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.

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:

• 1,000 rows → ~10 comparisons (log₂ 1000 ≈ 10)
• 1,000,000 rows → ~20 comparisons (log₂ 1000000 ≈ 20)
• 1,000,000,000 rows → ~30 comparisons (log₂ 1000000000 ≈ 30)

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.

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:

• B-tree indexes: sorted tree structure enabling range queries
• Hash indexes: hash table structure enabling exact-match lookups
• GiST/GIN indexes: specialized structures for full-text search, geographic data, etc.

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.

The Formal Definition:

More formally, an index on columns (C₁, C₂, ..., Cₙ) is a data structure I that:

1. Stores entries of the form (v₁, v₂, ..., vₙ, ptr) where vᵢ is a value from column Cᵢ and ptr is a pointer to the table row
2. Organizes these entries to support efficient lookup operations on the indexed columns
3. Maintains consistency with the base table through automatic updates when rows are inserted, updated, or deleted

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:

• The size of the indexed column values
• The size of the row pointers
• Any overhead for page metadata

Leaf Nodes and Internal Nodes:

Most index structures distinguish between:

• Leaf nodes: Contain the actual index entries (column values + row pointers)
• Internal nodes: Contain routing information to navigate to the correct leaf nodes

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 Height (Depth):

The height of an index determines the number of page reads required to reach a leaf node. For B-tree indexes:

• Height 1: Root is also the leaf (very small tables)
• Height 2: Root → Leaf (thousands of rows)
• Height 3: Root → Internal → Leaf (millions of rows)
• Height 4: Root → Internal → Internal → Leaf (billions of rows)

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.

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:

Index-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 = '[email protected]';

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:

1. Navigate to the first matching entry (e.g., created_at >= '2024-01-01')
2. Follow the leaf node chain, reading consecutive entries
3. For each entry, either return from index (covering) or access the heap
4. Stop when the range condition is no longer satisfied

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:

1. Write the new row to the table heap
2. For each index: Insert a new entry in the correct position
3. If an index page is full, split the page and update parent nodes
4. Write all modified pages to disk (or transaction log)

Update Operations:

Updates are particularly expensive if the updated columns are indexed:

1. Mark the old row version as obsolete (MVCC databases)
2. Write the new row version to the heap
3. For each index on updated columns: Remove old entry, insert new entry
4. Handle any page splits or reorganization

Delete Operations:

1. Mark the row as deleted (or physically remove it)
2. For each index: Remove the corresponding entry
3. Handle any page underflow or compaction

*Update overhead varies significantly based on which columns are updated and indexed.

Storage Overhead:

Indexes consume disk space proportional to:

• Number of rows in the table
• Size of indexed column values
• Index internal overhead (node pointers, metadata)

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.

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:

• High selectivity (few matching rows): Index is typically faster
• Low selectivity (many matching rows): Sequential scan often wins

The exact threshold varies by database and configuration, but a common rule of thumb is:

• <5% of rows: Index almost always faster
• 5-15% of rows: Depends on data distribution, disk speed, caching
• >15% of rows: Sequential scan often faster

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.

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:

• Clustered Index: The table data is physically organized according to the primary key order. The primary key index is the table.
• Implicit in All Secondary Indexes: All secondary indexes include the primary key value to locate rows in the clustered index.

PostgreSQL and many other systems use a different approach:

• Heap Tables: Table data is stored in insertion order (heap)
• Primary Key = Unique B-tree Index: The primary key is a regular unique B-tree index with a constraint
• Row Pointers: Secondary indexes point directly to heap locations

Unique Indexes:

Unique indexes serve a dual purpose:

1. Constraint Enforcement: Prevent duplicate values in the indexed column(s)
2. Query Performance: Provide fast lookups, just like non-unique indexes

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.

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.

• There can be only one clustered index per table (data can only be sorted one way physically)
• In MySQL/InnoDB: The primary key is always the clustered index
• In SQL Server: You can choose which index is clustered
• In PostgreSQL: There is no true clustered index; CLUSTER command is a one-time physical reorganization

Non-Clustered (Secondary) Index:

A non-clustered index is a separate structure whose leaf nodes contain:

• The indexed column values
• A pointer to the actual row (either a heap pointer or the primary key value)

Performance Implications:

Clustered Index Advantages:

• Range scans are fast because data is physically contiguous
• No additional lookup needed to get row data
• Better cache utilization for range queries

Clustered Index Disadvantages:

• Inserts into the middle of the table require page splits
• Non-sequential primary keys (like UUIDs) cause fragmentation
• Secondary indexes are larger (they must store the primary key)

Practical Guidance:

1. Choose clustered index columns carefully: They should be used in range queries and shouldn't change frequently
2. Sequential keys reduce fragmentation: Auto-increment IDs are ideal for clustered indexes; random UUIDs are problematic
3. Consider access patterns: If you always query by date range, a clustered index on date might be optimal

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.