Index Maintenance Cost

Every index you create imposes a tax on your database system—a tax that is paid not just in storage space, but in CPU cycles, I/O operations, memory pressure, and lock contention. Understanding these costs is essential because they are often invisible until they accumulate to a crisis point.

The Four Categories of Index Cost:

Index maintenance costs fall into four distinct categories, each with different characteristics and implications:

1. Per-Operation Costs — The immediate overhead added to each INSERT, UPDATE, or DELETE
2. Storage Costs — The disk space consumed by index data structures
3. Memory Costs — The buffer pool space required for efficient index access
4. Periodic Maintenance Costs — The background operations needed to keep indexes healthy

In this page, we will dissect each category with the rigor required to make informed indexing decisions.

Every write operation must maintain every index on the affected table. This fundamental fact has profound implications for system design.

The Anatomy of an INSERT with Indexes:

When you execute INSERT INTO orders VALUES (...) on a table with 6 indexes, here is the complete sequence of operations:

Quantifying the Cost:

The time complexity of a single INSERT scales linearly with the number of indexes:

$$T_{INSERT} = T_{base} + \sum_{i=1}^{n} T_{index_i}$$

Where:

• $T_{base}$ = Time to insert row into base table
• $T_{index_i}$ = Time to update index $i$
• $n$ = Number of indexes

Each $T_{index_i}$ includes:

• B+-tree traversal: O(log n) comparisons and page accesses
• Page lock acquisition: Variable, depends on contention
• Page modification: O(1) if no split, O(log n) if cascading splits
• Log writing: O(1) per log entry

While INSERT is straightforward (add keys to all indexes), UPDATE and DELETE have additional complexity that affects their cost profile.

UPDATE Operation Analysis:

UPDATE only modifies indexes for columns that are actually changed:

-- Only updates indexes containing 'status' or 'updated_at'
UPDATE orders SET status = 'shipped', updated_at = NOW() WHERE id = 12345;

-- Updates ALL indexes containing any of these columns
UPDATE orders
SET customer_id = 999, status = 'cancelled', total = 0, notes = 'Refunded'
WHERE id = 12345;

This creates an important optimization opportunity: design UPDATEs to modify as few indexed columns as possible.

The Deferred Delete Optimization:

Many modern databases use ghost records or delete markers instead of immediately removing index entries:

1. DELETE marks the record as 'deleted' but doesn't physically remove it
2. Index entries remain in place but are marked invalid
3. Background processes later perform physical cleanup

This optimizes DELETE latency but creates storage bloat and cleanup overhead. The trade-off is worthwhile for most workloads because:

• User-facing DELETE operations complete faster
• Cleanup can be batched and scheduled during low-activity periods
• MVCC (Multi-Version Concurrency Control) benefits from retaining old versions temporarily

Index storage costs are often underestimated. A naive assumption is that an index on a small column uses minimal space. In reality, index storage can exceed the base table size.

Anatomy of Index Storage:

Each index consists of:

• Leaf pages — Containing keys and pointers (row locators)
• Internal (branch) pages — Containing separator keys and child pointers
• Root page — Entry point for traversal
• Overflow pages — For handling long keys or page splits
• Free space — Reserved for future insertions (fill factor)

Storage Cost Multipliers:

Several factors can significantly increase actual storage beyond theoretical calculations:

For indexes to deliver their promised performance benefits, they must be cached in the buffer pool. This creates competition with other data structures for limited memory resources.

The Buffer Pool Reality:

Modern database systems cache frequently accessed pages in a buffer pool (also called buffer cache or shared buffers). When an index page is needed:

1. If in buffer pool: Memory access (~100 nanoseconds)
2. If on SSD: SSD read (~100 microseconds) — 1,000× slower
3. If on HDD: Disk read (~10 milliseconds) — 100,000× slower

An index that doesn't fit in the buffer pool loses most of its performance advantage.

Working Set Analysis:

Not all pages in an index are accessed equally. The working set is the subset of pages accessed during normal operation:

• Hot pages: Root and upper-level internal nodes (accessed constantly)
• Warm pages: Frequently-accessed leaf segments (recent data, popular keys)
• Cold pages: Rarely-accessed leaves (old data, uncommon keys)

A well-designed index has a small working set relative to total size. An index on a monotonically increasing key (like auto-increment ID or timestamp) has excellent locality—new inserts always go to the same few pages, keeping the working set small.

Conversely, an index on randomly distributed keys (like UUIDs) has poor locality—inserts scatter across the entire index, requiring the whole index to be cached for good performance.

Index maintenance requires locks, and locks create contention. In high-concurrency systems, this contention can become the limiting factor on throughput.

Index Page Locking:

When modifying an index, the database must acquire locks to prevent concurrent operations from creating inconsistencies:

• Shared locks (S): For read operations on index pages
• Exclusive locks (X): For write operations (insert, delete, modify)
• Update locks (U): Intermediate state to prevent deadlocks

Most databases use fine-grained locking at the page or key level, but contention still occurs when multiple transactions target the same page.

Hot Spots in Indexes:

Certain index patterns create severe lock contention:

1. Sequential Key Insertion (The Right Edge Problem)

When inserting into an index on an auto-increment or timestamp column:

• All inserts target the rightmost leaf page
• All concurrent inserters compete for the same page lock
• Throughput is limited by single-page write speed

2. Popular Key Updates

If many transactions update the same indexed value:

• All updates request exclusive lock on the same leaf page
• Transactions queue behind each other
• Response time degrades linearly with concurrency

3. Index Splits During High Load

When a page split occurs:

• Parent pages must also be modified
• Lock escalation may occur
• Concurrent operations on the same subtree are blocked

Fragmentation is the gradual degradation of index structure over time due to insert, update, and delete operations. There are two types of fragmentation, each with different symptoms and remedies.

Beyond per-operation costs, indexes require periodic maintenance to remain healthy. These maintenance operations consume resources and must be scheduled carefully to avoid impacting production workloads.