Master MySQL Indexes: Types, Structures, and Performance Trade‑offs

1. Index Basics

1.1 What is an Index

An index is a data structure used to speed up query and retrieval, such as B‑tree, B+‑tree, or hash table. It works like a directory, allowing fast location of records.

Advantages : ① Significantly accelerates query speed; ② Uniqueness ensures each row is distinct. Disadvantages : ① Index creation and maintenance consume time and can slow down write operations; ② Indexes occupy physical storage space.

1.2 Underlying Data Structures

1.2.1 Hash Table

Hash tables use a hash function to map a key to a value quickly.

hash = hashfunc(key)
index = hash % array_size

Hash collisions occur when different keys produce the same index. Common resolutions include open addressing, rehashing, and chaining. In JDK 1.8 HashMap, when a bucket’s chain exceeds a threshold (default 8), it is converted to a red‑black tree.

1.2.2 B‑Tree and B+‑Tree

B‑Tree is a multi‑way balanced search tree; B+‑Tree is a variant used by MyISAM and InnoDB engines. From the primary‑key perspective, indexes are divided into primary (clustered) and secondary (non‑clustered) indexes.

InnoDB stores both index and data together in the .ibd file; leaf nodes contain both index keys and the corresponding row data. MyISAM stores index in .MYI and data in .MYD files; secondary indexes point to primary keys.

2. Index Types and Principles

2.1 Classification by Data Separation

2.1.1 Clustered Index

A clustered index stores the index structure together with the table data. Primary keys are clustered indexes.

2.1.2 Non‑Clustered Index

A non‑clustered index stores the index structure separately from the data.

2.2 Classification by Primary Key

2.2.1 Primary Key Index

The table’s primary key uses a clustered index.

2.3 Secondary Indexes

Secondary indexes are non‑clustered; their leaf nodes store the primary key, enabling lookup of the row.

Unique Index : Enforces uniqueness, allows NULL, often used for constraints.

Normal Index : Improves query speed; duplicates and NULLs are allowed.

Prefix Index : Applies to string columns, indexes only the leading characters to save space.

Full‑Text Index : Designed for keyword search in large text fields.

// Example range query
SELECT * FROM tb1 WHERE id < 500;

SELECT id, plname, ranking FROM pl_ranking WHERE plname='Java';