Understanding MySQL Index Structures and Optimization

Index Structure

MySQL defines an index as a data structure used by the storage engine to quickly locate records. Indexes require additional space and maintenance overhead.

  • Indexes are stored as physical data pages in data files (e.g., .ibd files for InnoDB), utilizing data pages for storage.
  • Indexes speed up retrieval but slow down insert, update, and delete operations due to maintenance costs.

Ordered Array

Ordered arrays are efficient for both equality and range queries but are very inefficient for insert, update, and delete operations. They are only suitable for static data, such as historical population data by city for a given year.

Binary Search

Binary search, or half-interval search, finds a target value within a sorted array. It offers excellent performance for equality and range searches but has high maintenance costs for updates, inserts, and deletions.

Hash Index

A hash index is a key-value store that maps keys to values. Collisions are inevitable, where multiple keys map to the same hash bucket, resulting in a linked list.

Hash tables are only suitable for equality queries; range queries require a full table scan. They are commonly used in NoSQL databases.

InnoDB's Adaptive Hash Index

InnoDB's adaptive hash index is designed to improve query performance. The InnoDB storage engine monitors index page accesses. When it notices that certain index values are accessed very frequently, it builds a hash index in memory on top of the existing B+Tree index. This gives the in-memory B+Tree index hash-like capabilities for fast equality lookups of frequently accessed index pages. The reason for building a hash index on top of the B+Tree in memory is that hash indexes are more efficient for equality lookups than B+Trees.

The adaptive hash index is built automatically based on access patterns and frequency. Users can only enable or disable this feature; they cannot manually control which indexes become hash indexes.

Binary Search Tree

  • The left child is smaller than the parent, and the right child is larger.
  • A major drawback is that with monotonically increasing values, the tree degenerates into a linked list, resulting in O(n) time complexity (n being the tree depth).

Balanced Binary Tree (AVL)

  • The depth difference between left and right subtrees cannot exceed 1. For example, if the left subtree depth is 2, the right subtree depth must be 1 or 3.
  • When inserting values like 1, 2, 3, the tree performs self-balancing (rotations) to maintain the balance condition, even if values are inserted in order.
  • Drawbacks include frequent rotations, which add overhead, especially with many deletes and inserts. With large datasets, the tree height becomes very high (since each node holds only one key and data), leading to numerous disk I/O operations and slower queries.

B-Tree

  • A self-balancing tree where each node can store multiple keys and data. Each node is called a page.
  • B-Trees compress the tree height by storing multiple keys per node, reducing I/O and improving query speed.
  • An m-order B-Tree has a maximum of m children per node. For example, a 3rd order B-Tree has at most three children per node.

Searching for primary key value 49:

  1. Disk I/O to read the root node page (usually cached in memory).
  2. In-memory comparison: 49 > 15 and < 56, so follow the corresponding pointer.
  3. Disk I/O to read the target node.
  4. In-memory comparison: 49 > 20, equal to 40? No, then continue. Finally equal to 49, retrieve the record.

B+Tree

  • Non-leaf nodes store only key values and pointers.
  • All leaf nodes are linked together via pointers.
  • All actual data records are stored in leaf nodes.
  • Leaf nodes are sorted in ascending order from left to right.
  • Better full scan capability: the linked list of leaf nodes allows traversing all data without restarting from the root.
  • Better disk I/O: all data is in leaf nodes, reducing tree depth and I/O.
  • Better sorting and range queries: a range like value > 10 can leverage the leaf node linked list instead of traversing from the root.
  • In InnoDB, the default page size is 16KB. Assuming a BIGINT index (8 bytes) and a pointer (6 bytes), a non-leaf node can store roughly 16KB / (8+6) ≈ 1170 keys. With a record size of 1KB, a 3-level B+Tree can store approximately 1170 * 1170 * (16KB / 1KB) ≈ 21 million records.
  • For non-primary key indexes (secondary indexes), the leaf nodes store the primary key value instead of the full row data.

Index Types

Indexes improve query efficiency and affect WHERE and ORDER BY clauses.

  • By storage structure: B-Tree, Hash, Full-Text, R-Tree.
  • By application level: Normal, Unique, Primary Key, Composite.
  • By key-value type: Primary Key, Secondary Index.
  • By data storage logic: Clustered, Non-Clustered.

Normal Index

Columns can have NULL values and duplicates. Created using INDEX or KEY.

CREATE INDEX idx_name ON tablename(column_name);
ALTER TABLE tablename ADD INDEX idx_name(column_name);
CREATE TABLE tablename (..., INDEX idx_name(column_name));

Unique Index

Column values must be unique but can be NULL. Created using UNIQUE.

CREATE UNIQUE INDEX idx_name ON tablename(column_name);
ALTER TABLE tablename ADD UNIQUE INDEX idx_name(column_name);
CREATE TABLE tablename (..., UNIQUE INDEX idx_name(column_name));

Primary Key Index

A unique index where column values cannot be NULL. Usually created automatically when a primary key is defined.

ALTER TABLE tablename ADD PRIMARY KEY (column_name);
CREATE TABLE tablename (..., PRIMARY KEY (column_name));

Composite Index

An index on two or more columns. The sorting order follows the leftmost prefix principle: first column is sorted, then the second for equal values, and so on.

Narrow indexes have 1-2 columns; wide indexes have more than 2. It's often preferable to use narrow indexes.

CREATE INDEX idx_col1_col2 ON tablename(col1, col2);
ALTER TABLE tablename ADD INDEX idx_col1_col2(col1, col2);

Full-Text Index

Only created on VARCHAR or TEXT columns. It enables efficient full-text searches. Before MySQL 5.6, only MyISAM supported full-text indexes; from 5.6 onwards, InnoDB also supports them.

CREATE FULLTEXT INDEX idx_fulltext ON tablename(column_name);
ALTER TABLE tablename ADD FULLTEXT INDEX idx_fulltext(column_name);
CREATE TABLE tablename (..., FULLTEXT INDEX idx_fulltext(column_name));

-- Querying with MATCH and AGAINST
SELECT * FROM user WHERE MATCH(name) AGAINST('aaa');

Clustered and Non-Clustered (Secondary) Indexes

Clustered Index

  • If a primary key is defined, it becomes the clustered index. Otherwise, the first NOT NULL UNIQUE column is used. If none exists, InnoDB creates a hidden row_id.
  • A table can have only one clustered index.
  • The logical order of the index key determines the physical order of rows on disk.
  • The clustered index is a B+Tree where leaf nodes hold the full row data. This is like the pinyin index of a Chinese dictionary; the order of entries matches the physical order of words.

Non-Clustered Index

  • A table can have multiple non-clustered indexes.
  • The logical order of the index differs from the physical row order.
  • Non-clustered indexes include normal, unique, and full-text indexes. Leaf nodes store only the index column(s) and the primary key, acting as pointers to the actual data.
  • They require less storage space than the clustered index.

Index Analysis and Optimization

EXPLAIN

EXPLAIN provides query execution plans. SHOW WARNINGS can reveal the optimized SQL after an EXPLAIN.

Key fields:

  • id: Select identifier. Higher values indicate earlier execution in subqueries.
  • select_type: Type of SELECT (SIMPLE, PRIMARY, UNION, SUBQUERY, etc.).
  • table: Table name or alias.
  • type: Join type, from worst to best: ALL, index, range, ref, eq_ref, const, system, NULL.
    • ALL: Full table scan.
    • index: Full index scan (usually uses a secondary index).
    • range: Index range scan (e.g., >, <, IN).
    • ref: Non-unique index lookup.
    • eq_ref: Unique index lookup for each row from previous table.
    • const/system: Primary key or unique index equality lookup.
    • NULL: No table or index access needed.
  • possible_keys: Indexes that could be used.
  • key: The actual index used.
  • key_len: Length of the used index (in bytes).
  • ref: Columns or constants used with the index.
  • rows: Estimated number of rows to scan.
  • Extra: Additional information (e.g., Using where, Using index, Using filesort, Using temporary).

key_len calculation examples:

  • CHAR(n): 3n bytes for UTF-8.
  • VARCHAR(n): 3n + 2 bytes for UTF-8 (2 bytes for length).
  • INT: 4 bytes.
  • BIGINT: 8 bytes.
  • Add 1 byte if the column allows NULL.

Common Extra values:

  • Using where: Filtering after reading rows.
  • Using index: Covering index; only the index is needed.
  • Using index condition: Range scan on the first column of a composite index.
  • Using temporary: Temporary table for GROUP BY, ORDER BY, etc.
  • Using filesort: Sort operation requiring additional passes.
  • Using join buffer: No index used for join; buffer needed.
  • Impossible WHERE: No matching rows.

Back to Table (回表)

When using a non-clustered index, the query first finds the primary key from the index tree, then uses the primary key (clustered index) to locate the full row. This requires scanning two index trees.

Covering Index

If all required columns are in the index, MySQL can satisfy the query without accessing the table. This is a covering index.

Leftmost Prefix Matching

For a composite index (name, age), queries can use the index if they match the leftmost columns: name, or name AND age. A query on age alone cannot use this index.

Index Condition Pushdown (ICP)

Introduced in MySQL 5.6 for secondary indexes. ICP allows filtering using index columns before accessing the table. For example, with (username, age) index and WHERE username LIKE '张%' AND age > 10, the age condition is evaluated on the index before fetching rows.

Index Creation Guidelines

  1. Follow leftmost prefix matching.
  2. Index columns used frequently in WHERE clauses.
  3. Avoid indexing columns that are updated frequently.
  4. Do not use functions or calculations on indexed columns.
  5. Extend existing indexes rather than adding new ones.
  6. Use prefix indexes for long strings.
  7. Prioritize WHERE conditions over ORDER BY when choosing indexes.
  8. Consider index order for GROUP BY and ORDER BY.
  9. Prefer WHERE over HAVING for filtering.
  10. Low-cardinality columns (e.g., gender) are poor index candidates.
  11. Index foreign key columns.
  12. Avoid indexing TEXT or BLOB columns directly.
  13. Remove unused or rarely used indexes.

Cases Where Indexes May Not Be Used

  1. OR or IN conditions may cause a full table scan if the optimizer estimates it's faster.
  2. Mismatched data types (e.g., comparing a string column with a number).
  3. Skipping the leftmost column in a composite index.
  4. Using functions on indexed columns.
  5. Arithmetic operations on indexed columns.
  6. != or NOT IN may cause index bypass.
  7. IS NULL or IS NOT NULL may cause index bypass.
  8. Different character encodings in joined columns.
  9. Optimizer estimates a full scan is faster.
  10. LIKE '%pattern' (leading wildcard).

Common Optimization Issues

Slow Query Optimization

  • Add appropriate indexes.
  • Avoid returning unnecessary columns.
  • Write efficient SQL (e.g., matching composite index order).
  • Use EXISTS for large outer tables and IN for large inner tables.

LIKE Queries

Indexes are used for LIKE 'pattern%' (suffix wildcard) but not for LIKE '%pattern%' or LIKE '%pattern'.

NULL Values and Indexes

Indexes can contain NULL values, but it's generally recommended to define columns as NOT NULL with a default value.

Index and Sorting

MySQL can sort using an index (Using index) or by filesort (Using filesort). Filesort is less efficient.

Filesort algorithms:

  • Two-pass (original): Reads sort columns, sorts, then reads other columns.
  • Single-pass (optimized): Reads all columns at once. May cause multiple I/Os if the sort buffer is too small.

When index sorting is used:

  • ORDER BY matches the leftmost prefix of an index.
  • WHERE + ORDER BY together match the leftmost prefix.

When filesort is used:

  • Mixing ASC and DESC on index columns.
  • WHERE with a range condition before ORDER BY.
  • ORDER BY columns not matching the index leftmost prefix.
  • Using different indexes for ORDER BY and WHERE.
  • Using expressions on index columns.

Large Offset Pagination

As offset increases, performance degrades. Solutions:

  • Use covering indexes: SELECT id FROM ... LIMIT 100000, 10 is faster if only id is needed.
  • Use subquery with index: SELECT * FROM t WHERE id >= (SELECT id FROM t LIMIT 100000, 1) LIMIT 10; (works well for auto-increment primary keys without gaps).

Best Practices Example

CREATE TABLE `employees` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(24) NOT NULL DEFAULT '',
  `age` int(11) NOT NULL DEFAULT '0',
  `position` varchar(20) NOT NULL DEFAULT '',
  `hire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO employees(name,age,position) VALUES('LiLei',22,'manager');
INSERT INTO employees(name,age,position) VALUES('HanMeimei',23,'dev');
INSERT INTO employees(name,age,position) VALUES('Lucy',23,'dev');

-- Insert more test data
DELIMITER $$
CREATE PROCEDURE insert_emp()
BEGIN
  DECLARE i INT DEFAULT 1;
  WHILE i <= 100000 DO
    INSERT INTO employees(name,age,position) VALUES(CONCAT('zhuge',i), i, 'dev');
    SET i = i + 1;
  END WHILE;
END$$
DELIMITER ;
CALL insert_emp();

Full Value Match

EXPLAIN SELECT * FROM employees WHERE name= 'LiLei' AND age = 22 AND position ='manager';

Leftmost Prefix

Queries must start from the leftmost column of the index.

No Operations on Index Columns

-- Index is used
EXPLAIN SELECT * FROM employees WHERE name = 'LiLei';
-- Index is NOT used
EXPLAIN SELECT * FROM employees WHERE LEFT(name,3) = 'LiLei';

Range Condition Breaks Rightmost Columns

-- Both age and position use index
EXPLAIN SELECT * FROM employees WHERE name= 'LiLei' AND age = 22 AND position ='manager';
-- position does NOT use index because age is a range
EXPLAIN SELECT * FROM employees WHERE name= 'LiLei' AND age > 22 AND position ='manager';

Use Covering Indexes

-- Extra: Using index
EXPLAIN SELECT name,age FROM employees WHERE name= 'LiLei' AND age = 23;

!=, NOT IN May Skip Index

EXPLAIN SELECT * FROM employees WHERE name != 'LiLei';

IS NULL, IS NOT NULL May Skip Index

EXPLAIN SELECT * FROM employees WHERE name IS NULL;

LIKE Leading Wildcard Skips Index

-- NOT using index
EXPLAIN SELECT * FROM employees WHERE name LIKE '%Lei';
-- Using index
EXPLAIN SELECT * FROM employees WHERE name LIKE 'Lei%';
-- Can use covering index
EXPLAIN SELECT name,age,position FROM employees WHERE name LIKE '%Lei%';

Type Mismatch

-- Using index
EXPLAIN SELECT * FROM employees WHERE name = '1000';
-- NOT using index (implicit conversion)
EXPLAIN SELECT * FROM employees WHERE name = 1000;

OR / IN May Skip Index

Depending on the number of rows and optimizer estimates, OR and IN may not use indexes.

Range Query Optimization

Large ranges may cause a full table scan. Breaking them into smaller ranges can help.

Composite Index First Column Range

If the first column of a composite index is used with a range condition, the index might not be used. You can force index usage, but it may not improve performance.

COUNT Optimization

  • COUNT(*): Optimized by MySQL to count rows; very efficient.
  • COUNT(1): Similar to COUNT(*).
  • COUNT(id): Usually uses a secondary index if available.
  • COUNT(column): Does not count NULL values.

Summary

Indexes are critical for query performance. Understanding their structure, types, and optimization techniques helps write efficient queries and design better database schemas.

Tags: MySQL Index B+Tree performance optimization EXPLAIN

Posted on Sat, 19 Sep 2026 16:11:00 +0000 by markhard

Hot Tags

©2026 Freaks City