Understanding MySQL Indexes: B+Tree Structure, Engine Implementations, and Optimization Techniques

MySQL supports various storage engines, each providing different index types. The article concentrates on B+Tree indexes, the most commonly used structure, and defines an index as a data structure that helps MySQL retrieve rows efficiently.

Index purpose and principle – indexes act like a dictionary, narrowing the search range and converting random access into sequential access. By repeatedly reducing the data range, B+Tree indexes achieve logarithmic search complexity while minimizing disk I/O.

B+Tree structure – a disk block (blue) contains several data items (dark blue) and pointers (yellow). Leaf nodes store the actual row data, while internal nodes store only key values that guide the search.

MyISAM implementation – uses a B+Tree where leaf nodes store the physical address of the row. Both primary and secondary indexes have the same structure; the primary key must be unique, while secondary keys can repeat.

InnoDB implementation – also uses a B+Tree, but the table data itself is the primary index (clustered index). Leaf nodes contain the full row, and secondary indexes store the primary key value instead of a row address.

How to build appropriate indexes – follow the left‑most prefix rule for composite indexes. The article lists several practical tips, such as ordering columns by selectivity, avoiding functions on indexed columns, and extending existing indexes instead of creating new ones.

Configuration optimization – key MySQL variables that affect performance are highlighted, including innodb_buffer_pool_size, innodb_log_file_size, max_connections, innodb_file_per_table, innodb_flush_log_at_trx_commit, and query_cache_size. Proper tuning of these settings reduces I/O and improves concurrency.

SQL tuning and EXPLAIN – the article demonstrates how to use EXPLAIN to inspect execution plans, interpret fields such as type, possible_keys, and rows, and understand its limitations.

Practical example – a table circlemessage_idx_0 with a composite primary key (msg_id, to_id) and a secondary index (from_id, circle_id) is examined. Two EXPLAIN outputs show that adding a range condition on msg_id forces MySQL to scan hundreds of thousands of rows, indicating a sub‑optimal index order.

Optimization analysis – because msg_id is the first column of the primary key, MySQL prefers that index, preventing the use of to_id. The recommendation is to create a new composite index (to_id, circle_id, msg_id) so that the most selective columns are used first, reducing row scans.

Conclusion – understanding index principles, engine differences, and query patterns is essential for designing efficient indexes. Indexes should be added judiciously, considering selectivity, query frequency, and write overhead.