Understanding Database Indexes

There is no free lunch in computer science, and indexing is no exception. Every index that accelerates reads imposes costs elsewhere—storage space, write overhead, memory pressure, and maintenance complexity. The goal is not to create as many indexes as possible but to create the right indexes that maximize benefit while minimizing cost.

Many production database problems stem from misunderstanding these trade-offs: over-indexed tables that grind to a halt on writes, under-indexed tables with queries that timeout, or poorly-designed indexes that consume resources without providing value. Mastering index trade-offs separates database administrators from database experts.

Every index occupies disk space. For small tables, this is inconsequential. For large tables with multiple indexes, storage overhead can exceed the table itself.

Index Size Calculation:

The size of a B+-tree index depends on:

1. Entry count: N entries (one per row, or one per unique key for clustered)
2. Entry size: Key size + RID size (or full row for clustered)
3. Fill factor: Percentage of each page actually used (typically 70-90%)
4. Overhead: Internal nodes, page headers, free space management

Approximate Formula:

Index Size ≈ (N × Entry Size) / Fill Factor × 1.2 (for internal nodes)

Example:

• Table: 10 million rows
• Index on VARCHAR(50) column: Average key = 25 bytes
• RID: 8 bytes
• Entry size ≈ 33 bytes + overhead ≈ 40 bytes
• Fill factor: 80%
• Index size ≈ (10M × 40) / 0.8 × 1.2 = 600 MB

Storage Implications:

1. Disk Cost: Raw storage expense scales with index size
2. Backup Size: Backups include all indexes, increasing time and storage
3. Replication Overhead: Replicas must store and sync all indexes
4. Cloud Cost: Pay-per-GB storage charges add up across environments

Storage Optimization Strategies:

• Consolidate indexes: One composite index may replace multiple simple indexes
• Remove unused indexes: Audit index usage; drop those never accessed
• Partial indexes: Index only rows that matter (e.g., active users only)
• Index compression: Some databases support compressed indexes

Every data modification must update all relevant indexes. This is the most significant trade-off of indexing and the primary reason not to over-index.

What Happens on INSERT:

1. Insert record into base table
2. For EACH index on the table:
   • Traverse tree to correct leaf
   • Insert new entry
   • If leaf is full: split page, update parent (may cascade)
   • Write dirty pages (or log for WAL)

The Multiplication Factor:

A table with 5 indexes means each INSERT does essentially 6 separate inserts (1 table + 5 indexes). The overhead is not merely additive—it includes:

• Additional I/O (random for each index traversal)
• Additional lock contention (each index entry is a lockable resource)
• Additional logging (each index change is logged separately)
• Additional CPU (tree traversal, page management)

UPDATE Overhead:

Updates involving indexed columns are particularly expensive:

1. Find the record (may use index)
2. Update the table record (in place or move)
3. For EACH index containing updated columns:
   • Delete old index entry (tree traversal + deletion)
   • Insert new index entry (tree traversal + insertion)

A column that changes frequently should rarely be indexed.

DELETE Overhead:

1. Find the record to delete
2. Mark record as deleted in table (or remove)
3. For EACH index:
   • Traverse to the entry
   • Delete or mark as deleted
   • Handle underflow (merge nodes if necessary)

Indexes must be loaded into memory (the buffer pool) to be traversed. Index pages compete with data pages for limited memory. Too many indexes can degrade overall performance by evicting useful data or other index pages.

The Buffer Pool Economy:

A database buffer pool is a fixed-size cache holding frequently-accessed pages. When full, loading a new page evicts an old one. Consider a scenario:

• Buffer pool: 8 GB
• Table data: 50 GB
• Index A: 5 GB (frequently used)
• Index B: 3 GB (occasionally used)
• Index C: 4 GB (rarely used)
• Index D: 2 GB (almost never used)
• Total index: 14 GB

Without indexes C and D (6 GB), more table data stays cached, improving both indexed and non-indexed queries.

Index Working Set:

Not all index pages are equally important. The working set is the portion actively used:

• Root node: Always hot (loaded once, stays cached)
• Upper internal levels: Usually cached (small, frequently accessed)
• Lower internal levels: Partially cached (depends on access patterns)
• Leaf nodes: Rarely all cached (too large, accessed by specific queries)

For a well-designed index, the upper levels fit entirely in memory. Only leaf page access causes I/O. This is why fanout matters—higher fanout means shallower trees, more levels cached.

Memory Pressure Symptoms:

• Increased I/O on queries that were previously fast
• Buffer pool hit ratio dropping over time
• Query performance varying with workload mix
• Periodic performance degradation as cache churns

Indexes require ongoing maintenance beyond their creation. This operational overhead is often underestimated but can consume significant DBA time and system resources.

Fragmentation:

Over time, insert and delete operations fragment indexes:

• Internal fragmentation: Pages become partially filled as entries are deleted or scattered by splits
• External fragmentation: Logical page sequence diverges from physical disk sequence
• Free space accumulation: Dead entries and free space reduce effective page utilization

Impact of Fragmentation:

• Larger index size on disk than necessary
• More pages to read for range scans
• Reduced buffer pool efficiency
• Slower sequential scan patterns

Rebuilding and Reorganizing:

To combat fragmentation, indexes need periodic maintenance:

REBUILD (Offline or Online):

• Creates entirely new index structure
• Eliminates all fragmentation
• Expensive: May lock table (offline) or consume significant I/O (online)
• Frequency: Monthly to yearly depending on churn rate

REORGANIZE (Online):

• Compacts leaf pages in place
• Less disruptive than rebuild
• Doesn't address internal node fragmentation
• Frequency: Weekly to monthly

Statistics Updates:

Query optimizers depend on accurate statistics about indexes:

• Row counts, distinct values, value distribution histograms
• Stale statistics lead to poor query plans
• Statistics must be refreshed as data changes
• Frequency: Daily to weekly, or after significant data changes

Indexes introduce additional lockable resources. Each index page, and potentially each index entry, can be locked. With more indexes, there are more locks, and therefore more opportunities for contention.

Index Lock Types:

1. Page-Level Locks: Entire index page locked during modification

   • Insert into page = shared lock for traversal + exclusive for modification
   • Higher contention on 'hot' pages (recent inserts in sequential indexes)

2. Key-Level Locks: Individual index entries locked

   • Finer granularity reduces contention
   • Higher overhead (more locks to manage)
   • Used by most modern databases for row-level locking

3. Gap Locks: Lock ranges between keys (in some databases)

   • Prevents phantom reads in serializable isolation
   • Can cause unexpected blocking

Hot Spot Problem:

Sequential indexes (auto-increment IDs, timestamps) create hot spots:

• All inserts go to the same leaf page (the rightmost one)
• Multiple transactions compete for that page's lock
• Throughput limited by page lock serialization

Mitigation Strategies:

• Use random IDs: UUIDs scatter inserts across pages (but hurt range queries)
• Reverse-key indexes: Oracle feature that reverses key bytes
• Partitioned indexes: Spread inserts across partitions
• Reduce index count: Fewer indexes = fewer locks per insert

Deadlocks:

Multiple indexes increase deadlock risk:

• Transaction A: Update row via Index 1, then Index 2
• Transaction B: Update same row via Index 2, then Index 1
• Result: Deadlock if they interleave

Databases detect and resolve deadlocks, but at the cost of rolling back transactions.

More indexes give the query optimizer more choices—which is both good and bad. Good because more paths may exist to answer queries efficiently. Bad because:

1. Planning time increases: Optimizer must evaluate more alternatives
2. Suboptimal choices risk: Wrong index selection can be worse than table scan
3. Plan instability: Subtle data changes may cause plan flips

The Combinatorial Explosion:

For a query touching 3 tables with 5 indexes each:

• Each table has 6 access methods (5 indexes + table scan)
• Join order permutations: 3! = 6
• Access method combinations: 6³ = 216
• Total plan space: Potentially thousands of plans to consider

Plan Regression Risk:

The optimizer chooses plans based on statistics. With many indexes, the chosen plan is more sensitive to:

• Statistics accuracy (stale stats → wrong plan)
• Data distribution changes (skew changes → different best index)
• Parameter values (different predicate value → different selectivity)

A query that performed well for months suddenly slows down—not because anything changed, but because the optimizer now chooses a different index due to subtle statistical shifts.

Managing Optimizer Complexity:

1. Keep statistics fresh: Regular updates reduce bad decisions
2. Use plan guides/hints: Lock critical queries to specific indexes when needed
3. Remove unused indexes: Fewer choices = simpler optimization
4. Monitor plan changes: Alert on execution plan shifts for important queries
5. Test index additions: Measure impact before production deployment

Effective indexing requires balancing competing concerns. There is no formula—each system has unique workload characteristics. But there are principles that guide good decisions.

Principle 1: Workload-Driven Design

Indexes should reflect actual query patterns, not theoretical completeness:

• Analyze query logs to identify high-frequency, high-cost queries
• Design indexes to accelerate specific bottleneck queries
• Resist creating indexes "just in case" they might help

Principle 2: Consolidation Over Proliferation

One well-designed composite index often serves multiple query patterns:

• Index (A, B, C) supports: A, A+B, A+B+C
• This replaces: Index (A), Index (A, B), Index (A, B, C)
• Fewer indexes = less write overhead, less maintenance

Principle 3: Read/Write Ratio Awareness

Principle 4: Lifecycle Management

Indexes should not be permanent fixtures:

• Audit usage quarterly: identify unused indexes
• Remove indexes for deprecated features
• Re-evaluate when query patterns change
• Document why each index exists (naming convention helps)

Index trade-offs are not obstacles to avoid but realities to manage. Expert database professionals don't minimize or maximize indexes—they optimize, balancing costs against benefits for their specific workload. Let's consolidate the key concepts:

Module Complete:

With this page, we have completed Module 1: Index Concept. You now have a comprehensive understanding of what indexes are, how they are organized, how they accelerate queries, and what trade-offs they entail. This foundation prepares you for deeper exploration of specific index types, operations, and optimization techniques in subsequent modules.