System Design (HLD)Indexes and Query Performance

Indexes and Query Performance

LevelIntermediate

Duration90 mins

TopicIndexes and Query Performance

1 / 5

What Are Indexes

The Silent Performance Multiplier

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.

What You Will Master

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.

The Fundamental Problem: Why Indexes Exist

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.

Sequential Scan Cost at Different Scales
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:

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.

The Power of Logarithmic Complexity

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.

What Is an Index, Precisely?

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 Book Index Analogy Made Precise

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:

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
Organizes these entries to support efficient lookup operations on the indexed columns
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.

Anatomy of an Index

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-structure-visualization.txt
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 scans

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.

Why This Matters for Performance

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.

How Index Lookups Work

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 Lookup Algorithm

•Query Parsing & Planning: The database parser analyzes the query and the optimizer determines whether an index can be used. It evaluates available indexes and their estimated costs.
•Root Page Access: The database reads the index root page (usually cached in memory). The root contains keys that partition the search space.
•Tree Navigation: Using binary search within each page, the database navigates down the tree, reading one page per level until reaching a leaf node.
•Leaf Node Search: The leaf node is searched for matching entries. For exact matches, this finds the target entry. For range queries, it finds the starting point.
•Row Pointer Extraction: The row pointer (physical address) is extracted from the matching index entry.
•Heap Access: Using the row pointer, the database reads the actual table row from the heap (main table storage).
•Result Return: The complete row data is returned to the query executor.

lookup-example.sql
SQL Query
1
2
3
4
5
6
7
8
9
-- Example query that uses an index
SELECT * 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 data

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 = '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:

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

The Heap Access Cost

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.

Index Maintenance: The Hidden Cost

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:

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

Update Operations:

Updates are particularly expensive if the updated columns are indexed:

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

Delete Operations:

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

Write Performance Impact by Number of Indexes
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:

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.

The Over-Indexing Anti-Pattern

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.

When Indexes Help (and When They Don't)

Indexes are not universally beneficial. Understanding when they help—and when they hurt—is essential for effective database design.

Indexes Generally Help When

•Queries are selective: Returning a small fraction of total rows (typically <10-15%)
•Columns have high cardinality: Many distinct values (like email, UUID, timestamps)
•Read-heavy workloads: Queries vastly outnumber writes
•Point queries: Exact match lookups (WHERE id = 123)
•Range queries on sorted data: Date ranges, price ranges, etc.
•ORDER BY and GROUP BY: Avoiding expensive sort operations
•Join conditions: Accelerating join operations on foreign keys

Indexes Often Don't Help When

•Queries return most rows: Sequential scan is faster for large result sets
•Low cardinality columns: Few distinct values (like boolean flags, status codes)
•Write-heavy workloads: Index maintenance overhead exceeds read benefits
•Small tables: Sequential scan of 100 rows is often faster than index lookup
•Functions on columns: WHERE UPPER(name) = 'ALICE' can't use index on name
•Leading wildcard patterns: LIKE '%pattern' can't use B-tree indexes
•NULL comparisons (in some databases): WHERE column IS NULL behavior varies

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.

The Query Optimizer's Perspective

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

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

primary-key-examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- Primary key creates an index automatically
CREATE 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 key
CREATE 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 tables

Unique Indexes:

Unique indexes serve a dual purpose:

Constraint Enforcement: Prevent duplicate values in the indexed column(s)
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.

Natural Keys vs Surrogate Keys

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.

Clustered vs Non-Clustered 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.

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)

Clustered vs Non-Clustered Index Comparison
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:

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:

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

The UUID Fragmentation Problem

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.

Summary: The Foundation of Query Performance

We've established a comprehensive foundation for understanding database indexes. Let's consolidate the essential concepts:

Key Takeaways

•Indexes are separate data structures that store organized copies of column values with pointers to table rows, enabling O(log N) lookups instead of O(N) scans.
•B-tree indexes dominate in practice, offering logarithmic lookup times where even billion-row tables require only 3-4 disk reads per lookup.
•Index maintenance is not free—every index adds overhead to writes, with 5+ indexes potentially reducing write performance by 75% or more.
•Selectivity determines index value—indexes help most when queries are selective (<15% of rows), have high cardinality columns, and benefit read-heavy workloads.
•Clustered indexes determine physical storage order and are ideal for range queries, while non-clustered indexes require additional heap lookups.
•Primary keys automatically create indexes and should use stable, sequential values to minimize fragmentation.
•The query optimizer decides whether to use an index based on cost estimation—trust it, but verify with query plans.

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.

Foundation Complete

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.

1 / 5

Loading learning content...

What Are Indexes - Indexes and Query Performance | OneNoughtOne

System Design (HLD)Indexes and Query Performance

Indexes and Query Performance

LevelIntermediate

Duration90 mins

TopicIndexes and Query Performance

1 / 5

What Are Indexes

The Silent Performance Multiplier

What You Will Master

The Fundamental Problem: Why Indexes Exist

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?"

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

Sequential Scan Cost at Different Scales
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:

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)

The Power of Logarithmic Complexity

What Is an Index, Precisely?

1. Separate Data Structure:

2. Organized Copy:

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:

4. Pointers to Rows:

The Book Index Analogy Made Precise

The Formal Definition:

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

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
Organizes these entries to support efficient lookup operations on the indexed columns
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.

Anatomy of an Index

Index Pages (Blocks):

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-structure-visualization.txt
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 scans

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)

Fan-out:

Why This Matters for Performance

How Index Lookups Work

Step-by-Step Index Lookup Process:

Index Lookup Algorithm

•Query Parsing & Planning: The database parser analyzes the query and the optimizer determines whether an index can be used. It evaluates available indexes and their estimated costs.
•Root Page Access: The database reads the index root page (usually cached in memory). The root contains keys that partition the search space.
•Tree Navigation: Using binary search within each page, the database navigates down the tree, reading one page per level until reaching a leaf node.
•Leaf Node Search: The leaf node is searched for matching entries. For exact matches, this finds the target entry. For range queries, it finds the starting point.
•Row Pointer Extraction: The row pointer (physical address) is extracted from the matching index entry.
•Heap Access: Using the row pointer, the database reads the actual table row from the heap (main table storage).
•Result Return: The complete row data is returned to the query executor.

lookup-example.sql
SQL Query
1
2
3
4
5
6
7
8
9
-- Example query that uses an index
SELECT * 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 data

Index-Only Scans (Covering Indexes):

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:

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

The Heap Access Cost

Index Maintenance: The Hidden Cost

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:

Insert Operations:

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

Update Operations:

Updates are particularly expensive if the updated columns are indexed:

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

Delete Operations:

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

Write Performance Impact by Number of Indexes
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:

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.

The Over-Indexing Anti-Pattern

When Indexes Help (and When They Don't)

Indexes are not universally beneficial. Understanding when they help—and when they hurt—is essential for effective database design.

Indexes Generally Help When

•Queries are selective: Returning a small fraction of total rows (typically <10-15%)
•Columns have high cardinality: Many distinct values (like email, UUID, timestamps)
•Read-heavy workloads: Queries vastly outnumber writes
•Point queries: Exact match lookups (WHERE id = 123)
•Range queries on sorted data: Date ranges, price ranges, etc.
•ORDER BY and GROUP BY: Avoiding expensive sort operations
•Join conditions: Accelerating join operations on foreign keys

Indexes Often Don't Help When

•Queries return most rows: Sequential scan is faster for large result sets
•Low cardinality columns: Few distinct values (like boolean flags, status codes)
•Write-heavy workloads: Index maintenance overhead exceeds read benefits
•Small tables: Sequential scan of 100 rows is often faster than index lookup
•Functions on columns: WHERE UPPER(name) = 'ALICE' can't use index on name
•Leading wildcard patterns: LIKE '%pattern' can't use B-tree indexes
•NULL comparisons (in some databases): WHERE column IS NULL behavior varies

The Selectivity Threshold:

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.

The Query Optimizer's Perspective

Primary Keys and Unique Indexes

Primary keys and unique indexes are special index types that enforce data integrity constraints while also providing performance benefits.

Primary Key Index:

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

primary-key-examples.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- Primary key creates an index automatically
CREATE 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 key
CREATE 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 tables

Unique Indexes:

Unique indexes serve a dual purpose:

Constraint Enforcement: Prevent duplicate values in the indexed column(s)
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:

However, this difference is negligible in practice. The primary reason to create a unique index is data integrity, not performance.

Natural Keys vs Surrogate Keys

Clustered vs Non-Clustered Indexes

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)

Clustered vs Non-Clustered Index Comparison
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:

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:

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

The UUID Fragmentation Problem

Summary: The Foundation of Query Performance

We've established a comprehensive foundation for understanding database indexes. Let's consolidate the essential concepts:

Key Takeaways

•Indexes are separate data structures that store organized copies of column values with pointers to table rows, enabling O(log N) lookups instead of O(N) scans.
•B-tree indexes dominate in practice, offering logarithmic lookup times where even billion-row tables require only 3-4 disk reads per lookup.
•Index maintenance is not free—every index adds overhead to writes, with 5+ indexes potentially reducing write performance by 75% or more.
•Selectivity determines index value—indexes help most when queries are selective (<15% of rows), have high cardinality columns, and benefit read-heavy workloads.
•Clustered indexes determine physical storage order and are ideal for range queries, while non-clustered indexes require additional heap lookups.
•Primary keys automatically create indexes and should use stable, sequential values to minimize fragmentation.
•The query optimizer decides whether to use an index based on cost estimation—trust it, but verify with query plans.

What's Next:

Foundation Complete

1 / 5

Indexes and Query Performance

What Are Indexes

of Indexes

Indexes and Query Performance

What Are Indexes

of Indexes