Master MySQL Indexes: B+Tree Deep Dive & Optimization Tips

MySQL Indexes

MySQL supports many storage engines and index types; this article focuses on B‑Tree indexes, the most commonly used structure.

Index Principle

An index is a data structure that speeds up data retrieval by narrowing the search range, similar to looking up a word in a dictionary.

B+Tree Structure

B+Tree stores data in leaf nodes and pointers in internal nodes, allowing logarithmic search with few disk I/O operations.

The search process loads a disk block, performs a binary search, follows the pointer to the next block, and repeats until the target is found, typically requiring only a few I/O operations.

B+Tree Properties

Smaller fan‑out yields more data items per node and lower tree height.

Composite keys are compared left‑to‑right; the leftmost prefix must be used.

Non‑monotonic primary keys cause frequent page splits and fragmentation.

MySQL Index Implementations

MyISAM

MyISAM uses a non‑clustered B+Tree where leaf nodes store the address of the data record.

Both primary and secondary indexes have the same structure; the primary key must be unique.

InnoDB

InnoDB stores the table data itself as a clustered B+Tree indexed by the primary key; leaf nodes contain the full row.

Secondary indexes store the primary key value as the pointer, so every secondary lookup requires an additional primary‑key lookup.

How to Build Effective Indexes

The leftmost‑prefix rule means a composite index (A,B,C) can be used for queries on A, A‑B, or A‑B‑C, but not for B alone or A‑C.

Indexes improve read speed but increase storage and write overhead; use them judiciously.

For InnoDB, prefer an auto‑increment integer primary key to keep the clustered index compact.

Common Index Tips

Follow the leftmost‑prefix principle; range queries stop further column usage.

Equality and IN conditions can be reordered.

Choose high‑cardinality columns.

Avoid functions on indexed columns.

Extend existing indexes instead of creating new ones when possible.

MySQL Configuration Optimization

Key InnoDB settings include: innodb_buffer_pool_size Controls the memory used for data and index caching. innodb_log_file_size Size of the redo log. max_connections Maximum concurrent connections. innodb_file_per_table Stores each table in its own .ibd file. innodb_flush_log_at_trx_commit Controls durability vs performance. innodb_flush_method Determines how data is flushed to disk. innodb_log_buffer_size Buffer for unflushed transaction logs.

Other settings such as query_cache_size, log_bin, and skip_name_resolve affect performance and should be tuned according to workload.

SQL Tuning

Enable the slow‑query log, then use EXPLAIN to analyze execution plans, checking which indexes are used and the estimated row count.

Typical steps:

Verify the query is slow.

Apply the most selective WHERE conditions first.

Inspect the EXPLAIN output.

Adjust indexes according to the leftmost‑prefix rule.

Iterate until the plan matches expectations.

Summary

Indexes are not always beneficial; use them wisely.

Distinguish between primary keys and secondary indexes.

Understand B+Tree structure and how MySQL implements it.

Apply the leftmost‑prefix rule when designing composite indexes.