Master MySQL Indexes: Types, Structures, and Optimization Strategies

1. Common Index Types (Implementation)

Indexes aim to achieve fast data lookup, essentially acting as a search algorithm. In MySQL the data volume is typically massive and constantly changing, so the index structure must handle large, dynamic datasets efficiently.

The most common implementation‑level strategies are B‑Tree (actually B+Tree) and Hash indexes.

B‑Tree (B+Tree) Index

MySQL refers to its index type as B‑Tree, but it uses the B+Tree data structure. In a B+Tree, leaf nodes store all index values, internal nodes store navigation pointers, and leaf nodes are linked together to support range scans.

create table User(
  `name` varchar(50) not null,
  `uid` int(4) not null,
  `gender` int(2) not null,
  key(`uid`)
);

When rows with uid values 96‑102 are inserted, the storage engine builds an index tree where:

Leaf nodes contain every index value; non‑leaf nodes help locate the correct leaf.

Leaf nodes are ordered.

Leaf nodes are linked via a doubly‑linked list for efficient range queries.

In InnoDB, the primary key forms a clustered B+Tree; secondary (non‑clustered) indexes store the primary key value in leaf nodes and require an additional lookup to retrieve the full row.

In MyISAM, leaf nodes store a pointer to the row data instead of the primary key.

Hash Index

Hash indexes use a hash table and are only effective for exact‑match queries on all indexed columns.

create table User(
  `name` varchar(50) not null,
  `uid` int(4) not null,
  `gender` int(2) not null,
  key(`name`)
);

Lookup steps for select * from User where name='张三':

Compute the hash value, e.g., hash('张三') = 1287.

Locate the bucket (row number) corresponding to the hash.

Read the row and verify that name equals '张三'.

2. Common Index Types (Application Layer)

Primary Key Index : Unique, usually the table's ID; a table can have only one primary key.

Unique Index : Enforces uniqueness; a table may have multiple unique indexes.

Single‑Column Index : Index on a single field.

create table User(
  `name` varchar(50) not null,
  `uid` int(4) not null,
  `gender` int(2) not null,
  key(`name`)
);

Composite (Multi‑Column) Index : Index on two or more columns; must obey the leftmost‑prefix rule.

create table User(
  `name` varchar(50) not null,
  `uid` int(4) not null,
  `gender` int(2) not null,
  key(`name`,`uid`)
);

3. Clustered vs. Non‑Clustered Indexes

A clustered index stores the row data together with the index key in the leaf nodes of a B+Tree. In InnoDB the primary key is the clustered index; if no primary key exists, the engine chooses a unique non‑null index or creates a hidden one.

create table test(
  col1 int not null,
  col2 int not null,
  primary key(col1),
  key(col2)
);

In the example, col1 forms the clustered index, while col2 creates a secondary (non‑clustered) index.

In a non‑clustered index, leaf nodes store only the indexed column(s) and a pointer (the primary key) to the clustered index row.

Query example: select * from test where col2=93; requires two lookups—first the secondary index to find the primary key, then the clustered index to retrieve the full row.

4. Covering Index

A covering index contains all columns required by a query, eliminating the need to read the table data.

create table User(
  `name` varchar(50) not null,
  `uid` int(4) not null,
  `gender` int(2) not null,
  key(`uid`,`name`)
);

Query:

select name,uid from User where name in ('a','b') and uid >= 98 and uid <= 100;

Because the query accesses only name and uid, the composite index (uid, name) can satisfy the request directly from the index tree, avoiding a table lookup.

Benefits: eliminates the extra lookup on the primary (clustered) index and reduces I/O, greatly improving read performance.

5. Best Index Usage Strategies

Index columns must be independent; they cannot be part of expressions or functions (e.g., col1 + 1 = 100 or ABS(col1) = 100 are invalid).

Observe the leftmost‑prefix rule: for a composite index (col1, col2), queries that filter on col2 alone cannot use the index.

Index values should not be NULL; a single NULL in a column renders the index ineffective.

Prefer clustered and covering indexes whenever possible, as they store the needed data in the index leaf nodes and avoid costly table lookups.

Use short (prefix) indexes for long string columns to save space while still providing selective filtering.