MySQL

on May 1, 2015, tagged translations, introductions, mysql, databases, link-lists (share this post, e.g., on Mastodon or on Bluesky)

This article’s content comes from books and online sources.

I. Indexes

B+ Tree Principle

1. Data Structure

“B tree” refers to a balanced tree. A balanced tree is a search tree, and all leaf nodes reside on the same level.

B+ tree is implemented based on B tree with additional sequential access pointers between leaf nodes. It possesses B tree’s balanced properties while improving range query performance through sequential access pointers.

In a B+ tree, keys within a node are arranged non-descendingly from left to right. If two adjacent keys around a pointer are key_i and key_i+1, neither null, then all keys in the node pointed to by this pointer are greater than or equal to key_i and less than or equal to key_i+1.

2. Operations

During lookup operations, binary search is first performed on the root node to find a pointer associated with the target key, then recursively searched on the node pointed to by this pointer. This continues until reaching a leaf node, where binary search is performed on the leaf node to locate the data corresponding to the key.

Insertion and deletion operations can disrupt the balanced tree’s equilibrium; therefore, after insertion or deletion operations, split, merge, rotate, and other operations must be performed on the tree to maintain balance.

3. Comparison With Red-Black Trees

Balanced trees such as red-black trees can also implement indexing, but filesystems and database systems universally adopt B+ tree as the index structure, primarily for two reasons:

Fewer Lookup Operations

The time complexity of balanced tree lookup operations correlates with tree height h, O(h) = O(log_dN), where d represents each node’s out-degree.

Red-black trees have an out-degree of 2, whereas B+ tree nodes typically have very large out-degrees. Therefore, red-black tree height h is significantly larger than B+ tree height, resulting in many more lookups.

Leveraging Disk Pre-Fetch Characteristics

To reduce disk I/O operations, disks don’t read strictly on-demand; instead, they pre-fetch. During pre-fetching, disks perform sequential reads, which don’t require disk seeking and only need very short disk rotation time, making them quite fast.

Operating systems generally divide memory and disk into fixed-size blocks called pages; memory and disk exchange data in page units. Database systems set the size of an index node to match page size, allowing one I/O operation to completely load a node. Furthermore, pre-fetch characteristics allow neighboring nodes to be loaded in advance.

MySQL Indexes

Indexes are implemented at the storage engine layer rather than the server layer, so different storage engines offer different index types and implementations.

1. B+ Tree Index

This is the default index type for most MySQL storage engines.

Since full table scans are no longer necessary—only tree searches are required—lookup speed improves considerably.

Due to B+ tree’s ordered nature, it supports not only lookups but also sorting and grouping operations.

Multiple columns can be specified as index columns, forming a composite key together.

Suitable for full-key, key-value range, and key prefix lookups. Note that key prefix lookups apply only to leftmost prefix lookups. If lookups aren’t performed in index column order, indexes cannot be utilized.

In InnoDB, B+ tree indexes are divided into primary indexes and auxiliary indexes. Primary index leaf nodes record complete data records in the data field, known as clustered indexes. Because data rows cannot be stored in two different places, a table can have only one clustered index.

Auxiliary index leaf nodes record primary key values in the data field. Therefore, when using auxiliary indexes for lookups, you must first find the primary key value, then look up in the primary index.

2. Hash Index

Hash indexes enable O(1) time lookups but lose ordering:

• Cannot be used for sorting and grouping
• Support only exact matching, not partial or range lookups

InnoDB storage engine has a special feature called “adaptive hash index.” When certain indexed values are used very frequently, a hash index is created atop the B+ tree index, giving the B+ tree index some hash index advantages like fast hash lookups.

3. Full-Text Index

MyISAM storage engine supports full-text indexing, used for finding keywords within text rather than direct equality comparisons.

Query conditions use MATCH AGAINST rather than standard WHERE clauses.

Full-text indexing is implemented using inverted indexes, recording keyword-to-document mappings.

InnoDB storage engine also began supporting full-text indexing in MySQL version 5.6.4.

4. Spatial Data Index

MyISAM storage engine supports spatial data indexing (R-tree), usable for geographic data storage. Spatial data indexes index data across all dimensions, enabling effective combination queries using any dimension.

GIS-related functions must be used to maintain data.

Index Optimization

1. Independent Columns

When performing queries, index columns cannot be part of expressions or function parameters; otherwise, indexes cannot be used.

For example, the following query cannot use the actor_id column index:

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;

2. Multi-Column Indexes

When multiple columns need to be used as query conditions, multi-column indexes provide better performance than multiple single-column indexes. For example, in the statement below, actor_id and film_id should preferably be set as multi-column indexes.

SELECT film_id, actor_id FROM sakila.film_actor WHERE actor_id = 1 AND film_id = 1;

3. Index Column Order

Place the most selective index column first.

Index selectivity refers to the ratio of distinct index values to total records. Maximum value is 1, occurring when each record has a unique corresponding index. Higher selectivity means higher distinction per record and more efficient queries.

For example, in the results shown below, customer_id has higher selectivity than staff_id, so the customer_id column should preferably be placed before staff_id in multi-column indexes.

SELECT COUNT(DISTINCT staff_id)/COUNT(*) AS staff_id_selectivity, COUNT(DISTINCT customer_id)/COUNT(*) AS customer_id_selectivity, COUNT(*) FROM payment;

staff_id_selectivity: 0.0001
customer_id_selectivity: 0.0373
COUNT(*): 16049

4. Prefix Indexes

For BLOB, TEXT, and VARCHAR type columns, prefix indexes are required; only the initial portion of characters is indexed.

Prefix length selection depends on index selectivity requirements.

5. Covering Index

An index containing all fields needed for the query.

Benefits include:

• Indexes are typically far smaller than data rows; reading only indexes greatly reduces data access volume.
• Some storage engines (such as MyISAM) cache only indexes in memory, relying on operating system caching for data. Therefore, accessing only indexes avoids system calls (typically more costly).
• For InnoDB engine, if an auxiliary index can cover the query, accessing the primary index becomes unnecessary.

Advantages of Indexes

• Drastically reduces the number of data rows the server needs to scan.
• Helps servers avoid sorting and grouping operations, preventing creation of temporary tables (B+ tree indexes are ordered, suitable for ORDER BY and GROUP BY operations; temporary tables are mainly created during sorting and grouping processes; eliminating sorting and grouping eliminates temporary table creation).
• Converts random I/O into sequential I/O (B+ tree indexes are ordered, storing adjacent data together).

Conditions for Using Indexes

• For very small tables, simple full-table scans are more efficient than creating indexes in most cases;
• For medium to large tables, indexes are highly effective;
• However, for extremely large tables, the cost of creating and maintaining indexes increases accordingly. In such cases, technologies that can directly distinguish a group of data needing query without matching record-by-record are required—for example, partitioning techniques can be used.

II. Query Performance Optimization

Using Explain for Analysis

Explain analyzes SELECT query statements; developers can optimize query statements by analyzing Explain results.

Important fields include:

• select_type: Query type—simple queries, join queries, subqueries, etc.
• key: Index used
• rows: Number of rows scanned

Optimizing Data Access

1. Reduce Requested Data Volume

• Return only necessary columns: Preferably avoid using SELECT * statements.
• Return only necessary rows: Use LIMIT statements to constrain returned data.
• Cache repeatedly queried data: Using caches avoids querying in the database; particularly when data is frequently queried repeatedly, caching can deliver noticeable query performance improvements.

2. Reduce Rows Scanned on Server Side

The most effective method is using indexes to cover queries.

Restructuring Query Methods

1. Split Large Queries

A large query executed all at once may lock many data records simultaneously, fill entire transaction logs, exhaust system resources, and block many small but important queries.

DELETE FROM messages WHERE create < DATE_SUB(NOW(), INTERVAL 3 MONTH);

rows_affected = 0
do {
  rows_affected = do_query(
  "DELETE FROM messages WHERE create < DATE_SUB(NOW(), INTERVAL 3 MONTH) LIMIT 10000")
} while rows_affected > 0

2. Decompose Large Join Queries

Decompose large join queries into single-table queries for each table, then associate results in the application layer. Benefits include:

• More efficient caching. For join queries, if one table changes, the entire query cache becomes unusable. For decomposed multiple queries, even if one table changes, query caches for other tables remain usable.
• Decomposed single-table queries have cached results more likely to be reused by other queries, reducing redundant record queries.
• Reduced lock contention;
• Application-layer joins make database splitting easier, facilitating better performance and scalability.
• Query efficiency itself may improve. For example, in the example below, using IN() instead of join queries allows MySQL to query in ID order, potentially more efficient than random joins.

SELECT * FROM tag
JOIN tag_post ON tag_post.tag_id=tag.id
JOIN post ON tag_post.post_id=post.id
WHERE tag.tag='mysql';

SELECT * FROM tag WHERE tag='mysql';
SELECT * FROM tag_post WHERE tag_id=1234;
SELECT * FROM post WHERE post.id IN (123,456,567,9098,8904);

III. Storage Engines

InnoDB

This is MySQL’s default transactional storage engine. Consider other storage engines only when needing features it doesn’t support.

Implements four standard isolation levels, with REPEATABLE READ as the default level. At REPEATABLE READ isolation level, phantom reads are prevented through multi-version concurrency control (MVCC) plus Next-Key Locking.

Primary index is a clustered index, saving data within the index, thereby avoiding direct disk reads and delivering significant query performance improvements.

Internal optimizations include predictive reads when retrieving data from disk, adaptive hash indexes that accelerate read operations and are automatically created, and insert buffers that accelerate insertion operations.

Supports true online hot backups. Other storage engines don’t support online hot backups; obtaining consistent views requires stopping writes to all tables, and in mixed read-write scenarios, stopping writes may also mean stopping reads.

MyISAM

Simple design, tightly formatted data storage. Suitable for read-only data, small tables, or when repair operations can be tolerated.

Provides numerous features including compressed tables, spatial data indexes, etc.

Does not support transactions.

Does not support row-level locks—only table-level locking. Reads apply shared locks to all tables needing to be read; writes apply exclusive locks on the table. Concurrent inserts are supported, allowing new records to be inserted into tables while read operations occur.

Check and repair operations can be executed manually or automatically, though unlike transaction recovery and crash recovery, this may cause some data loss, and repair operations are very slow.

If DELAY_KEY_WRITE option is specified, modified index data won’t immediately write to disk upon completing each modification but will instead write to in-memory key buffers, with corresponding index blocks writing to disk only during key buffer cleanup or table closure. This significantly improves write performance but can cause index corruption during database or host crashes requiring repair operations.

Comparison

IV. Data Types

Integer Types

TINYINT, SMALLINT, MEDIUMINT, INT, BIGINT respectively use 8, 16, 24, 32, 64 bits of storage space. Generally speaking, smaller columns are better.

The number in INT(11) only specifies how many characters interactive tools display; it has no meaning for storage and computation purposes.

Floating-Point Numbers

FLOAT and DOUBLE are floating-point types; DECIMAL is a high-precision decimal type. CPUs natively support floating-point arithmetic but do not support DECIMAL type calculations; therefore, DECIMAL calculations require higher computational costs than floating-point types.

FLOAT, DOUBLE, and DECIMAL can all specify column widths, for example DECIMAL(18,9) indicates 18 total digits, with 9 digits storing the decimal portion and remaining 9 digits storing the integer portion.

Strings

CHAR and VARCHAR are the two main types—one fixed-length, one variable-length.

VARCHAR, as a variable-length type, saves space because it stores only necessary content. However, during UPDATE execution, rows may become longer than originally; when exceeding page capacity, additional operations are required. MyISAM will split rows into different fragments for storage, while InnoDB needs to split pages to fit rows within them.

During storage and retrieval, trailing spaces are retained for VARCHAR but removed for CHAR.

Time and Date

MySQL provides two similar date-time types: DATETIME and TIMESTAMP.

1. DATETIME

Can store dates and times from year 1000 to year 9999, with second precision, using 8 bytes of storage space.

It is timezone-independent.

By default, MySQL displays DATETIME values in a sortable, unambiguous format (e.g., “2008-01-16 22:37:08”), conforming to ANSI standard date and time representation methods.

2. TIMESTAMP

Similar to Unix timestamps, storing seconds elapsed since midnight January 1, 1970 (Greenwich Mean Time), using 4 bytes, capable of representing years 1970 to 2038.

It is timezone-dependent, meaning the same timestamp represents different specific times in different timezones.

MySQL provides FROM_UNIXTIME() function to convert Unix timestamps to dates, and UNIX_TIMESTAMP() function to convert dates to Unix timestamps.

By default, if no TIMESTAMP column value is specified during insertion, the current time will be assigned.

Timestamps should be used preferentially, as they offer better space efficiency than DATETIME.

V. Sharding

Horizontal Sharding

Horizontal sharding, also known as Sharding, splits records from the same table into multiple identically structured tables.

As a table’s data continuously grows, Sharding becomes inevitable—it distributes data across different cluster nodes, alleviating pressure on single databases.

Vertical Sharding

Vertical sharding splits a table by columns into multiple tables, typically based on column relationship density. It can also leverage vertical sharding to separate frequently-used columns from infrequently-used columns into different tables.

At the database level, vertical sharding deploys frequently dense tables to different databases—for example, vertically splitting an e-commerce database into product databases, user databases, etc.

Sharding Strategies

• Hash modulo: hash(key) % N
• Range: Can be ID-based ranges or time-based ranges
• Mapping tables: Uses a separate database to store mapping relationships

Issues With Sharding

1. Transaction Issues

Distributed transactions resolve this, for example via XA interfaces.

2. Joins

Original joins can be decomposed into multiple single-table queries, then connected in user programs.

3. ID Uniqueness

• Use globally unique IDs (GUID)
• Assign ID ranges to each shard
• Distributed ID generators (such as Twitter’s Snowflake algorithm)

VI. Replication

Master-Slave Replication

Involves three main threads: binlog thread, I/O thread, and SQL thread.

• Binlog thread: Responsible for writing data changes on the master server into binary logs
• I/O thread: Responsible for reading binary logs from the master server and writing them to relay logs on slave servers
• SQL thread: Responsible for reading relay logs, parsing data changes already executed by the master server, and replaying them on the slave server

Read-Write Separation

Master servers handle write operations and real-time-sensitive read operations, while slave servers handle read operations.

Read-write separation improves performance because:

• Master and slave servers handle respective reads and writes, substantially alleviating lock contention
• Slave servers can use MyISAM, improving query performance and reducing system overhead
• Increased redundancy improves availability

Read-write separation commonly uses proxy implementations. Proxy servers receive read-write requests from the application layer, then decide which server to forward to.

VII. Locking Mechanisms

Database Locks

Databases are shared resources used by multiple users concurrently. When multiple users concurrently access and modify data, multiple transactions may operate on the same data simultaneously. Without concurrency control, incorrect data may be read and stored, destroying database consistency.

Locking is a crucial technology implementing database concurrency control. Before operating on a data object, a transaction requests the system to lock it. After locking, the transaction gains certain control over the data object; before releasing the lock, other transactions cannot perform update operations on that data object.

Basic Lock Types

Locks include row-level locks and table-level locks.

• Row-level lock: An exclusive lock preventing other transactions from modifying that row;
  • Oracle automatically applies row-level locks when using: INSERT, UPDATE, DELETE, SELECT … FOR UPDATE [OF columns] [WAIT n | NOWAIT];
  • SELECT … FOR UPDATE statements allow users to lock multiple records for update at once
  • COMMIT or ROLLBACK statements release locks
• Table-level lock: Divided into 5 categories:
  • ROW SHARE: Prevents exclusive table locking
  • ROW EXCLUSIVE: Prevents exclusive and shared locks
  • SHARE: Locks the table for read-only access; multiple users can apply this lock on the same table simultaneously
  • SHARE ROW EXCLUSIVE: Greater restrictions than SHARE; prevents shared locks and higher
  • EXCLUSIVE: Strongest table lock; permits only other users to query table rows, prohibiting modifications and table locking

Optimistic and Pessimistic Locks

• Pessimistic lock: Based on database mechanisms. For example, adding FOR UPDATE to SELECT clause prevents any applications from modifying selected records until that statement’s transaction ends.
• Optimistic lock: Based on application-level versioning mechanisms. Generally, a version field v is designed in tables (often set as timestamp).

Typical update scenarios are as follows:

1 select a, v from tb where id=1;

// Each update operation must change the version field, otherwise inter-process data will still be mutually overwritten. Note that “v” generally won’t be modified during business operations.
2 update tb set a='yyyy', v=systimestamp where v=11111;

VIII. MySQL Installation and Configuration

1. Docker Deployment of MySQL

// a. Pull MySQL image
docker pull mysql:8.4

// b. Create local mapped directories
cd /Users/admin/program/docker/instance/mysql
mkdir -p ./data ./logs ./conf

/*
“data” directory will be mapped as MySQL container configuration data file storage path
“logs” directory will be mapped as MySQL container’s log directory
“conf” directory’s configuration files will be mapped as MySQL container’s configuration files
*/

// c. Start container (Reference document: https://www.cnblogs.com/zqifa/p/mysql-6.html)
docker run -p 3306:3306 --name mysql \
-v $PWD/conf:/etc/mysql/conf.d \
-v $PWD/logs:/var/log/mysql \
-v $PWD/data:/var/lib/mysql \
-e MYSQL_ROOT_PASSWORD=root_pwd \
-e TZ=Asia/Shanghai \
-d mysql:8.4 \
--character-set-server=utf8mb4 \
--collation-server=utf8mb4_unicode_ci

/*
-p 3306:3306: Maps container’s 3306 port to host’s 3306 port
-v $PWD/conf:/etc/mysql/conf.d: Mounts conf/my.cnf from host’s current directory to container’s /etc/mysql/my.cnf
-v $PWD/logs:/var/log/mysql: Mounts logs directory from host’s current directory to container’s /logs
-v $PWD/data:/var/lib/mysql: Mounts data directory from host’s current directory to container’s /mysql_data
-e MYSQL_ROOT_PASSWORD=123456: Initializes root user password
*/

// d. Set timezone (optional)
// Sync timezone method 1:
docker cp /etc/localtime mysql:/etc/localtime

// Sync timezone method 2: Confirm after restart, reference: https://blog.csdn.net/zhangchao19890805/article/details/52690473
docker exec -it <image-id> /bin/bash
cp /usr/share/zoneinfo/PRC /etc/localtime
date -R

References

1. Baron Schwartz, Peter Zaitsev, Vadim Tkachenko, et al. High Performance MySQL [M]. Publishing House of Electronics Industry, 2013.
2. Jiang Chengyao. MySQL Technology Insider: InnoDB Storage Engine [M]. Mechanical Industry Press, 2011.
3. 20+ Best Practices for MySQL Performance Optimization
4. Server Guide Data Storage Section | MySQL (09) Distributed Dilemmas and Countermeasures From Database Partitioning and Table Splitting
5. How to Create Unique Row ID in Sharded Databases?
6. SQL Azure Federation—Introduction
7. Data Structures and Algorithm Principles Behind MySQL Indexes
8. Explain Tool Usage Analysis for MySQL Performance Optimization
9. How Sharding Works
10. Didian Dianping Order System Database Partition and Table Splitting Practice
11. B+ Tree
12. Database Locking Mechanisms

(This post is a machine-made, human-reviewed, and authorized translation of xuxueli.com/­blog/­?blog=db/­mysql.)