Index Types & When to Use Each

Before examining specific index types, let's understand the fundamentals of how database indexes work and why they're so critical for performance.

What Is a Database Index?

A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional storage space and slower writes. In essence, an index is a copy of selected data from a table, organized in a way that makes lookups extremely efficient.

The Indexing Analogy

Think of a database table without indexes like a book without an index or a table of contents. To find specific information, you'd need to scan through every page of the book—a sequential scan. With an index, you can quickly locate the pages containing relevant information, just as a database index helps the query engine find rows without scanning the entire table.

Core Index Mechanics

Database indexes typically work on these principles:

1. Sorted Storage: Most index types maintain data in a sorted order, making range searches efficient
2. Tree Structures: Many use tree-like structures where each node points to more specific information
3. Direct Pointers: Index entries usually point directly to the table rows containing the indexed values
4. Selectivity: Indexes work best when they help the database eliminate a large percentage of rows quickly

Key Index Properties

When discussing indexes, several properties matter:

• Cardinality: The number of unique values in the indexed column(s)
• Selectivity: The ratio of unique values to total rows (higher is better)
• Clustering Factor: How well-ordered the data is on disk relative to the index
• Size: How much storage the index consumes
• Maintenance Overhead: Cost of keeping the index updated during writes

The Cost of Indexes

While indexes dramatically improve read performance, they come with costs:

1. Storage Space: Each index requires additional storage—sometimes as much as the table itself
2. Write Performance: Every INSERT, UPDATE, or DELETE must also update affected indexes
3. Maintenance Operations: Indexes can become fragmented and require rebuilding/reorganizing
4. Query Planner Overhead: Having many indexes increases planning time as the optimizer evaluates more options

Index Storage Structure

Indexes are typically stored separately from the table data:

1TABLE DATA                    INDEX
2┌────────────────┐           ┌────────────────┐
3│ Row 1          │           │ Value -> Row 5 │
4│ Row 2          │ ◄─────────│ Value -> Row 2 │
5│ Row 3          │           │ Value -> Row 9 │
6│ Row 4          │           │ Value -> Row 1 │
7│ Row 5          │ ◄─────────│ Value -> Row 8 │
8└────────────────┘           └────────────────┘

When Should Indexes Be Created?

Indexes are typically beneficial on:

• Primary key columns (created automatically in most RDBMS)
• Foreign key columns (for efficient joins)
• Columns frequently used in WHERE clauses
• Columns used in ORDER BY or GROUP BY operations
• Columns used in aggregate functions like MIN() or MAX()

Basic Index Types Across RDBMS

Most relational databases support these fundamental index types:

1. B-tree (Balanced Tree): The default, general-purpose index type in most RDBMS
2. Hash: Optimized for equality comparisons but not range queries
3. Bitmap: Efficient for low-cardinality data (few unique values)
4. Specialized Types: Database-specific indexes for special data types or access patterns

Let's examine each of these index types in detail to understand their strengths, limitations, and ideal use cases.

table with 1 million rows:

1SELECT * FROM orders WHERE customer_id = 12345;

Without index:

• Full table scan examining 1,000,000 rows
• Might take 1-2 seconds to execute

With B-tree index on customer_id:

• Log₂(1,000,000) ≈ 20 page reads
• Execution time: ~5ms (200-400x faster)

B-tree indexes are the default choice for most indexing needs due to their versatility and consistent performance. However, for specific workloads, other index types might provide better performance or space efficiency, which we'll explore next.