Deep Dive into MySQL Index Working Principles: From Basic Concepts to Performance Optimization

Fundamental Concepts and Working Principles of Indexes

In database systems, the core function of indexes is analogous to a book's index. Suppose we need to find content related to "storage" in a book about databases. Without an index, we would have to scan through the entire book page by page, equivalent to a full table scan in databases. With an index, we can directly locate the specific pages where the keyword "storage" appears (e.g., pages 113-120, 231, and 354) and quickly access the required information, significantly improving query efficiency.

Index Selectivity and Applicable Scenarios

The effectiveness of an index heavily depends on its selectivity. Using the book analogy, if we create an index for the high-frequency word "database," we might find it appears on pages 1-59, 61-290, and 292-400. In this case, the index covers almost the entire book, and using it might be slower than directly scanning page by page. This situation is known as "poor selectivity" in databases, meaning the index cannot effectively narrow down the query range.

For small data tables (like a 10-page book), creating an index might be counterproductive. The index itself consumes storage space—a 5-page index plus 10 pages of content results in a 15-page "book," which is clearly less efficient than directly scanning 10 pages. Similarly, creating indexes with no practical query value (such as counting the frequency of the letter "L" per page) only increases system overhead without any benefit.

B+Tree Index Implementation in MySQL

In MySQL's InnoDB storage engine, the most commonly used index type is the B+Tree-based index. This index stores data in sorted order, enabling efficient range and equality queries. More importantly, query results can be retrieved directly through the index without accessing the actual data rows, a feature known as "covering index," which significantly enhances query performance.

Consider the following table structure definition:

CREATE TABLE person (
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    INDEX (last_name, first_name)
);

For the composite index (last_name, first_name), query conditions must adhere to the "leftmost prefix principle" to fully utilize the index. For example, the following query can efficiently use the index:

SELECT last_name, first_name FROM person
WHERE last_name = "John" AND first_name LIKE "J%"

However, the following query cannot effectively leverage this composite index:

SELECT last_name, first_name FROM person WHERE first_name = "Constantine"

This is because the query condition starts with first_name, skipping the leftmost column last_name of the index. The situation worsens with LIKE queries using leading wildcards:

SELECT last_name, first_name FROM person WHERE first_name LIKE "%Constantine"

This pattern matching cannot utilize the index's sorting特性, forcing the database to perform a full table scan.

Hash Indexes and Their Application Scenarios

Besides B+Tree indexes, MySQL also supports hash indexes, though currently limited to the MEMORY storage engine. Hash indexes offer extremely high performance for equality queries but do not support range queries (e.g., >, <) or pattern matching (e.g., LIKE).

In practical applications, hash indexes can be simulated on B+Tree indexes to optimize queries on large fields. For instance, when storing URLs, an additional hash value field can be created:

CREATE TABLE url_table (
    url VARCHAR(255) NOT NULL,
    url_hash INT UNSIGNED NOT NULL,
    INDEX (url_hash)
);

During queries, quickly locate via the hash value first, then verify the actual value:

SELECT url FROM url_table 
WHERE url_hash=CRC32("http://gnu.org") AND url="http://gnu.org";

Although this method requires two comparisons, since integer comparisons are much faster than string comparisons, overall performance is significantly improved.

Key Points for Index Optimization Practices

Based on the above analysis, the following key principles for index optimization can be summarized:

First, understanding the impact of data types on comparison performance is crucial. Integer comparisons are typically orders of magnitude faster than string comparisons, explaining why hash simulation techniques can effectively enhance performance.

Second, complex query optimizations often require step-by-step processing. By creating in-memory temporary tables and establishing appropriate indexes, heavy queries can be broken down into multiple lightweight operations, thereby improving overall performance.

Finally, index usage must comprehensively consider query patterns, data distribution, and system resources. Highly selective indexes can greatly improve query efficiency, while low-selectivity indexes or improper index designs can become performance bottlenecks.

Summary and Best Practices

MySQL indexes establish efficient data access paths, avoiding costly full table scans. B+Tree indexes, with their excellent support for range queries and sorting特性, are the most commonly used index type. The leftmost prefix principle of composite indexes requires that query conditions must start from the leftmost column of the index; otherwise, the index's advantages cannot be fully utilized.

In actual database design and optimization, appropriate index strategies should be selected based on specific query requirements, balancing query performance with maintenance costs. For frequent equality queries, consider hash indexes or simulation techniques; for complex multi-condition queries, carefully design the column order of composite indexes; and for scenarios where full table scans are more optimal (e.g., querying most data rows), avoid unnecessary index usage.