Master MySQL Indexes, Execution Plans, and Transaction Isolation: A Deep Dive

1. MySQL Index Data Structures and Algorithms

Indexes help MySQL retrieve data efficiently and store it in sorted order. MySQL mainly uses B+ trees and hash structures; hash is fast for lookups but unsuitable for sorting.

Tree structures rely on binary search, giving low time complexity, but can suffer from degeneration and increased height as data grows, leading to more disk I/O.

Tree Types

Binary tree : can degenerate into a linked list, increasing query cost.

Red‑Black tree : a balanced binary tree that mitigates degeneration but still faces height growth.

B‑tree : multi‑way tree that stores more rows per node, reducing height, but each node stores full row data, increasing memory usage.

B+‑tree : only leaf nodes store row data and are linked, allowing efficient range scans and ordered retrieval.

MySQL stores index nodes in 16 KB pages (a disk block), which are read into memory as needed.

2. SQL Execution Plan Analysis

The execution plan can be obtained with EXPLAIN. Important columns include:

id : execution order of SELECT statements.

table : the table being accessed.

type : optimization level (system > const > eq_ref > ref > range > index > ALL).

key : the actual index used.

rows : estimated number of rows examined.

Extra : additional info such as Using index, Using where, Using temporary, Using filesort.

3. How MySQL Executes a SQL Statement

Client maintains a TCP connection to the MySQL server.

MySQL checks the query cache (LRU) for a hit.

The SQL is parsed by the built‑in parser.

The optimizer generates an execution plan, possibly applying cost‑based decisions.

The executor invokes the appropriate storage engine (InnoDB, MyISAM, Memory, …).

The engine uses the chosen index to locate rows and may maintain the index.

4. Locks and Transaction Isolation Levels

Concurrent transactions can cause dirty writes, dirty reads, non‑repeatable reads, and phantom reads. MySQL solves these with transaction isolation, locks, and MVCC.

Isolation levels:

Read Uncommitted : allows reading uncommitted changes.

Read Committed : sees only committed data.

Repeatable Read (default): each SELECT sees a consistent snapshot.

Serializable : highest isolation, uses locking to serialize access.

Lock types include optimistic vs. pessimistic, shared (read) vs. exclusive (write), and table vs. row locks. Row locks are most common in InnoDB.

InnoDB uses gap locks in repeatable‑read mode to prevent phantom reads.

5. Deep Dive into MVCC

Multi‑Version Concurrency Control allows reads without locking. It relies on a ReadView and an undo_log version chain .

Each row modification creates an undo log entry linked by hidden trx_id and roll_pointer fields, forming a singly linked list from newest to oldest.

Read‑committed transactions generate a new ReadView for each SELECT; repeatable‑read transactions generate it once per transaction, guaranteeing repeatable results.

6. InnoDB Buffer Pool Mechanism

MySQL updates data in memory first. The workflow is:

Read the required page from disk into the Buffer Pool.

Write the original row to the undo log.

Modify the row in the Buffer Pool.

Write the new version to the redo log buffer.

On commit, flush the redo log buffer to the redo log file.

Asynchronously write the binary log.

Mark the redo log entry as committed.

This design avoids random disk writes, improves throughput, and ensures durability.