乐趣区

关于mysql:超级干货为什么MySQL能够支撑千万数据规模的快速查询

jiezi

此文来自课程《MySQL 外围问题 32 讲》，聚焦 MySQL 面试过程中的常见问题，由阿里资深 P7 工程师倾情研发。

导读

首先，在设计用户核心零碎的数据库时，我先创立一张用户根底表 user，如下：

`CREATE TABLE user (id int(11) unsigned NOT NULL AUTO_INCREMENT,
 user_id int(8) DEFAULT NULL COMMENT '用户 id',
 user_name varchar(29) DEFAULT NULL COMMENT '用户名',
 user_introduction varchar(498) DEFAULT NULL COMMENT '用户介绍',
 sex tinyint(1) DEFAULT NULL COMMENT '性别',
 age int(3) DEFAULT NULL COMMENT '年龄',
 birthday date DEFAULT NULL COMMENT '生日',
 PRIMARY KEY (id)
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8;`

该表所有字段都加了备注阐明，大家应该能够分明地明确每个字段的含意。同时，我再插入 8 条记录，如下：

INSERT INTO `user` (`id`, `user_id`, `user_name`, `user_introduction`, `sex`, `age`, `birthday`)
VALUES
 (1, 10001, 'Jack', 'I'm Jack', 1, 25,'1998-01-02'),
 (2, 10002, 'Nancy', 'I'm Nancy', 0, 15,'2008-02-03'),
 (3, 10003, 'Bruce', 'I'm Bruce', 1, 17,'2006-03-03'),
 (4, 10004, 'John', 'I'm John', 1, 18,'2005-03-05'),
 (5, 10005, 'Amy', 'I'm Amy', 0, 15,'2008-02-06'),
 (6, 10006, 'Lucy', 'I'm Lucy', 0, 16,'2007-06-06'),
 (7, 10007, 'Mike', 'I'm Mike', 1, 17,'2006-07-01'),
 (8, 10008, 'Henry', 'I'm Henry', 1, 16,'2007-06-07');

而后，我创立一个联结索引 index_age_birth，如下：


ALTER TABLE `user` ADD INDEX `index_age_birth` (`age`, `birthday`);

当初，咱们开始剖析一下，为什么 MySQL 可能撑持千万数据规模的疾速查问？影响 MySQL 查问性能的因素十分多，比方，索引、optimizer、query cache、lock、各种 buffer 等等，这些都会影响到 MySQL 查问的性能，而在这一章节，我次要解说一下索引这个玩意儿，因为它在咱们日常的工作中用到的最多。

其实，网上有很多解说 MySQL 索引构造的常识，然而，大多内容解说不够粗疏，所以，我这边次要针对网上可能漠视的局部，更具体地解说 MySQL 的索引构造。咱们都晓得 MySQL 的索引构造和它的存储引擎密不可分。日常工作中，咱们用的最多的存储引擎就是 MyISAM 和 InnoDB，比拟少用的还有 Memory、Federated、Merge 等等。其中，最支流的存储引擎还是 InnoDB，所以，我就来具体解说一下InnoDB 引擎在 MySQL 中的索引构造是什么样的？

索引构造

InnoDB 引擎的索引构造次要分为两种：聚簇索引和辅助索引。它们长什么样儿呢？上面我就以下面那张用户表为例，来看看这两种索引的样子：

  1. 聚簇索引

    聚簇索引在 InnoDB 中的存储构造是一颗 B -Tree。

    (1) 非叶节点 ：其中， 最上层的节点称为根节点，其余节点中，发动指针指向的节点称为父节点，指针指向的节点称为孩子节点。该节点蕴含多个 < 主键 id，page_no> 元组组成的记录，同时，它本身也有个页号，其中 page_no 元素有个指针，指向了上面的一个非叶节点或叶子节点，多个元组之间组成一个单向链表，每个非叶节点之间组成了一个双向链表。

    例子 1：如上图，根节点页 1 蕴含两条元组记录 <1, 2> 和 <5, 3>，本身页号为 1，第一个元组记录中的 page_no 元素 2 指向页 2 这个节点，第二个元组记录中的 page_no 元素 3 指向页 3 这个节点。

    例子 2：如上图，页 2 节点蕴含两条元组记录 <1, 4> 和 <3, 5>，第一个元组记录中的 page_no 元素 4 指向页 4 这个节点，第二个元组记录中的 page_no 元素 5 指向页 5 这个节点，两个元组之间通过单向指针连贯，组成一个单向链表。

    例子 3：页 2 节点和页 3 节点组成了一个双向链表。

    (2) 叶子节点：该节点蕴含多个 < 主键 id，非主键字段值 > 元组组成的记录，同时，它本身也有个页号，多个元组之间组成一个单向链表，每个叶子节点之间组成了一个双向链表。

    例子 1：如上图，图中，非主键字段值我只列了两个字段：user_id 和 user_name，其余用 …… 省略了，省略字段参见本章《导读》局部创立用户表的 SQL，以页 7 节点为例，该节点蕴含两条元组记录 <7，10007，Mike，I’m Mike，1，17，2006-07-01> 和 <8，10008，Henry，I’m Henry，1，16，2007-06-07>，这两个元组组成了一个单向链表。

    例子 3：页 6 和页 7 两个节点组成一个双向链表。

    聚簇索引有个特点：所有节点内的记录依照主键 id 升序排列。

  2. 辅助索引

    辅助索引在 InnoDB 中的存储构造也是一颗 B -Tree。

    (1) 非叶节点 ：其中， 最上层的节点称为根节点，其余节点中，发动指针指向的节点称为父节点，指针指向的节点称为孩子节点。该节点蕴含多个 < 索引列值，page_no> 元组组成的记录，同时，它本身也有个页号，其中 page_no 元素有个指针，指向了上面的一个非叶节点或叶子节点，多个元组之间组成一个单向链表，每个非叶节点之间组成了一个双向链表。

    因为本文结尾，我建了一个联结索引 index_age_birth，索引列为(age，birthday)，所以，上图 B -Tree 非叶节点中的元组构造为 <age，birthday，page_no>。

    例子 1：如上图，根节点页 1 中蕴含两条元组记录 <15, 2008-02-03, 2> 和 <17, 2006-03-03, 3>，本身页号为 1，第一个元组记录中的 page_no 元素 2 指向页 2 节点，第二个元组记录中的 page_no 元素 3 指向页 3 节点。

    例子 2：如上图，页 2 节点蕴含两条元组记录 <15, 2008-02-03, 4> 和 <16, 2007-06-06, 5>，第一个元组记录中的 page_no 元素 4 指向页 4 节点，第二个元组记录中的 page_no 元素 5 指向页 5 节点，两个元组之间通过单向指针连贯，组成一个单向链表。

    例子 3：页 2 节点和页 3 节点组成了一个双向链表。

    (2) 叶子节 点：该节点蕴含多个 < 索引列值，主键 id> 元组组成的记录，同时，它本身也有个页号，多个元组之间组成一个单向链表，每个叶子节点之间组成了一个双向链表。

    同样，因为索引 index_age_birth 的索引列为(age，birthday)，所以，上图 B -Tree 叶子节点中的元组构造为 <age，birthday，id>。

    例子 1：如上图，页 7 节点蕴含两条元组记录 <18，2005-03-05，4> 和 <25，1998-01-02，1>，这两个元组组成了一个单向链表。

    例子 3：页 6 和页 7 两个节点组成一个双向链表。

    辅助索引有个特点：所有节点内的记录依照索引列值升序排列。比方：index_age_birth 索引，首先，记录依照 age 升序排列，如果 age 雷同，再依照 birthday 升序排列。

查找算法

讲完 InnoDB 的索引构造，咱们通过下面的构造，大略能够推断出为什么 MySQL 查问一条或多条记录那么快了。

  1. 无论是聚簇索引，还是辅助索引，都是一颗 B -Tree，所以，通过 二分查找，咱们能够疾速定位到所要查问的记录。

    (1) 主键查问：依据主键 id 二分搜寻聚簇索引，能够疾速定位到叶子节点上的记录。这部分内容网上材料很多，我就不具体举例解说了。

(2) 辅助索引列查问：参照本章《索引构造》中辅助索引 B -Tree 的图，我以查找 age=25 的记录为例，对该图新增了查问过程的箭头走向，见上图，咱们先看下红色箭头：

之前我讲过了这颗 B -Tree 的节点内元组记录的构造，在这里，我从新明确一下，不便大家疾速了解上面的流程，这个 B -Tree 的非叶节点内记录的构造为 <age，birthday，page_no>，叶子节点内记录的构造为 <age，birthday，id>。

a. 页 1 -> 页 3：因为页 1 内第二条记录的 age 元素为 17，查问条件 age=25，25 > 17，走右分支，所以，沿着页 1 指向页 3 的指针，定位到页 3 节点。

b. 页 3 -> 页 7：因为页 3 内第二条记录的 age 元素为 18，查问条件 age=25，25 > 18，走右分支，所以，沿着页 3 指向页 7 的指针，定位到叶子节点页 7。

c. 在页 7 节点中，第二条元组记录中的 age 元素值为 25，满足 age=25 的查问条件，所以，定位到记录 <25，1998-01-02，1> 为辅助索引中所要查找的记录。

d. 最初，拿主键 id= 1 到聚簇索引进行二分查找，定位到叶子节点上主键 id= 1 的残缺记录。之前说了，网上对于聚簇索引查找过程的材料很多，所以，这里就不具体阐明了。

  1. 因为辅助索引 B -Tree 上的节点外部的记录升序排列，记录与记录之间组成单向链表，节点之间组成双向链表，所以，我能够通过线性查找(即按列值程序查找)，疾速实现一个范畴查问。比方，我当初要执行上面这条 SQL：
 SELECT * FROM user WHERE age >= 15

见上图绿色箭头：

(1) 页 1 -> 页 2：因为页 1 节点中第一个元组记录的 age 元素为 15，查问条件 age>=15，15 >= 15，所以，沿着页 1 指向页 2 的指针，定位到页 2 节点。

(2) 页 2 -> 页 4：因为页 2 节点中第一个元组记录的 age 元素为 15，查问条件 age>=15，同样 15 >= 15，所以，沿着页 2 指向页 4 的指针，定位到页 4 节点。

(3) 页 4 -> 页 5 -> 页 6 -> 页 7：页 4、页 5、页 6 和页 7 节点之间通过双向指针 (正向和逆向) 连贯组成双向链表，每个节点外部所有记录通过一个单向指针 (正向) 连贯组成单向链表，且所有记录依照索引 index_age_birth 内列值升序排列，即页 4 ~ 页 7 节点内所有记录的 age 元素肯定都大于等于 15 且升序排列，所以，咱们只需从页 4 内的第一条记录开始遍历其指针连贯的所有后续记录，找到这些 age >= 15 的记录的主键 id，即 1 ~ 8，最初，依据这些主键 id 去聚簇索引查找相应记录就行了。

综上所述，咱们得出了为什么 MySQL 查问一条或多条记录那么快的起因：

  1. 二分查找：过滤了搜寻过程中无需遍历的节点。
  2. 线性查找：无需重复从根节点搜寻满足条件的节点记录，而是间接遍历满足叶子节点中满足查问条件的第一条记录的所有后继节点。

总结

上文次要解说了 InnoDB 的索引构造，蕴含聚簇索引和辅助索引，两者的共同点都是 B -Tree 构造

两者的区别是：

非叶节点 叶子节点
聚簇索引 存储主键记录 + 孩子节点页指针 存储残缺一条行记录
辅助索引 存储索引列值 + 孩子节点页指针 存储索引列值 + 主键

同时，基于 B -Tree 构造，得出了两种晋升查问索引构造性能的算法：二分查找和线性查找。

上文来自课程《MySQL 外围问题 32 讲》，聚焦 MySQL 面试过程中的常见问题，由阿里资深 P7 工程师倾情研发，如有趣味请扫描下方二维码理解详情，欢送一起交流学习，独特攻克 MySQL。

退出移动版