MySQL Index Overview

Database indexes are sorted data structures in DBMS that help in quickly querying and updating data in a database. Generally, data structures used for building indexes include B-trees, B+ trees, hash tables, etc.

MySQL uses B+ trees to build indexes. The reason for this choice is that a B+ tree node can store more data, and in a B+ tree, only leaf nodes store data, while non-leaf nodes store only indexes. This allows the index to be stored in memory as much as possible, reducing tree height, minimizing disk I/O when querying indexes, and greatly improving query efficiency.

Indexes in InnoDB

Clustered Index and Non-Clustered Index

Indexes can be divided into clustered and non-clustered indexes based on the data stored in the leaf nodes.

• Clustered Index: The leaf nodes store the data rows directly, allowing direct access to user data.
• Non-Clustered Index: The leaf nodes store the primary key value, and data must be fetched by traversing back to the primary key index (a process known as index backtracking).

In the InnoDB engine, the table’s data is organized using the primary key index. Each table must have a primary key, which constructs the B+ tree, resulting in a primary key index. The primary key index is a clustered index, and all other secondary indexes are non-clustered indexes.

Composite Index

A composite index is an index composed of multiple fields.

create index index_name on table_name (col_1, col_2...)

Compared to a single-field index, the main difference is that it follows the leftmost prefix matching principle.

Leftmost Prefix Matching Principle: When using a composite index, the index values are sorted according to the fields in the index from left to right.

Using Indexes to Optimize Query Performance

Since indexes are ordered, they can significantly improve query efficiency. When using indexes for query optimization, some principles must be followed.

Leftmost Prefix Matching Principle

When using a composite index, the index values are sorted from left to right based on the indexed fields. We need to follow the leftmost prefix matching rule in our queries; otherwise, the data arrangement becomes unordered, resulting in a full table scan.

Suppose you create an index on col1, col2, col3. Following the leftmost prefix matching principle, the query conditions should be designed in the order col1 -> col2 -> col3.

Example:

select * from table_name where col1 = 1 and col2 = 2; This will use the index.

select * from table_name where col2 = 1 and col3 = 2; This will not use the index.

Note: MySQL will continue matching the columns until it encounters a range query (>, <, between, like), after which it stops matching.

Index Coverage Principle

Index coverage refers to querying values directly from the index without needing to traverse back to the table. Well-designed indexes can reduce the number of backtracking operations.

For a composite index (col1, col2, col3):

A query like select col1, col2, col3 from test where col1=1 and col2=2 can directly retrieve values for col1, col2, and col3 without needing to traverse back to the table, as their values are already stored in the secondary index.