为什么MySQL能够支撑千万数据规模的快速查询？

谦虚的小K 07-01 513

前言：

当前你们对“mysql查询效率影响因素”大体比较注意，咱们都想要剖析一些“mysql查询效率影响因素”的相关知识。那么小编同时在网摘上收集了一些关于“mysql查询效率影响因素””的相关内容，希望朋友们能喜欢，咱们一起来了解一下吧！

导读

本文我们以设计一个用户中心的表结构开始，我先创建一张用户表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引擎的索引结构主要分为两种：聚簇索引和辅助索引。它们长什么样儿呢？下面我就以上面那张用户表为例，来看看这两种索引的样子：

聚簇索引

上图是user表的聚簇索引，它在InnoDB中的存储结构是一颗B+Tree。(1) 非叶节点：其中，最上层的节点称为根节点，其他节点中，发起指针的节点称为父节点，指针指向的节点称为孩子节点，它们都是非叶节点。该节点包含多个<主键id，page_no>元组组成的记录，同时，它自身也有个页号，其中page_no元素有个指针，指向了下面的一个非叶节点或叶子节点，多个元组之间通过一个单向链表指针相连，每个非叶节点之间通过两个双向链表指针相连。如上图，根据节点页1包含两条元组记录<1, 2>和<5, 3>，自身页号为1，第一个元组记录中的page_no元素2指向页2这个节点，第二个元组记录中的page_no元素3指向页3这个节点。如上图，页2节点包含两条元组记录<1, 4>和<3, 5>，第一个元组记录中的page_no元素4指向页4这个节点，第二个元组记录中的page_no元素5指向页5这个节点，两个元组之间通过单向指针连接，组成一个单向链表。页2和页3节点通过两个个双向链表指针相连(2) 叶子节点：该节点包含多个<主键id，非主键字段值>元组组成的记录，同时，它自身也有个页号，多个元组之间通过一个单向链表指针相连，每个叶子节点之间通过两个双向链表指针相连。如上图，图中，非主键字段值我只列了两个字段：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>，这两个元组通过一个单向链表指针相连。页6和页7两个节点通过两个双向链表指针相连。

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

辅助索引上图是索引index_age_birthday这个索引的结构，这个索引也叫辅助索引，辅助索引在InnoDB中的存储结构也是一颗B+Tree。(1) 非叶节点：其中，最上层的节点称为根节点，其他节点中，发起指针的节点称为父节点，指针指向的节点称为孩子节点，它们都是非叶节点，该节点包含多个<索引列值，page_no>元组组成的记录，同时，它自身也有个页号，其中page_no元素有个指针，指向了下面的一个非叶节点或叶子节点，多个元组之间通过一个单向链表指针相连，每个非叶节点之间通过两个双向链表指针相连。因此，上图B+Tree非叶节点中的元组结构为<age，birthday，page_no>。如上图，根据节点页1中包含两条元组记录<15, 2008-02-03, 2>和<17, 2006-03-03, 3>，自身页号为1，第一个元组记录中的page_no元素2指向页2节点，第二个元组记录中的page_no元素3指向页3节点。如上图，页2节点包含两条元组记录<15, 2008-02-03, 4>和<16, 2007-06-06, 5>，第一个元组记录中的page_no元素4指向页4节点，第二个元组记录中的page_no元素5指向页5节点，两个元组之间通过单向指针连接。页2节点和页3节点通过两个双向链表指针相连。(2) 叶子节点：该节点包含多个<索引列值，主键id>元组组成的记录，同时，它自身也有个页号，多个元组之间通过一个单向链表指针相连，每个叶子节点之间通过两个双向链表指针相连。同样，由于索引index_age_birth的索引列为(age，birthday)，所以，上图B+Tree叶子节点中的元组结构为<age，birthday，id>。如上图，页7节点包含两条元组记录<18，2005-03-05，4>和<25，1998-01-02，1>，这两个元组通过一个单向链表指针相连。页6和页7两个节点通过两个双向链表指针相连。

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

查找算法

讲完InnoDB的索引结构，我们通过上面的结构，大概可以推断出为什么MySQL查询一条或多条记录那么快了。

无论是聚簇索引，还是辅助索引，都是一颗B+Tree，所以，通过二分查找，我们可以快速定位到所要查询的记录。

主键查询：根据主键id二分搜索聚簇索引树，可以快速定位到叶子节点上的记录。这部分内容网上资料很多，我就不详细讲解了。辅助索引列查询：我以查找age=25的记录为例，见下图红色箭头，看下辅助索引树的搜索过程：页1 -> 页3：遍历页1中的元组记录，由于页1内第二条记录的age元素为17，查询条件age=25，25 > 17，走右分支，所以，沿着页1指向页3的指针，定位到页3节点。页3 -> 页7：遍历页3中的元组记录，由于页3内第二条记录的age元素为18，查询条件age=25，25 > 18，走右分支，所以，沿着页3指向页7的指针，定位到叶子节点页7。在页7节点中，遍历页7中的元组记录，第二条元组记录中的age元素值为25，满足age=25的查询条件，所以，定位到记录<25，1998-01-02，1>为辅助索引中所要查找的记录。最后，拿主键id=1到聚簇索引叶子节点遍历查找，定位到叶子节点上主键id=1的完整记录。具体查找方法，我会在《InnoDB是顺序查找B-Tree叶子节点的吗？》详细讲解。由于辅助索引B+Tree上的节点内部的记录升序排列，记录与记录之间组成单向链表，节点之间组成双向链表，所以，我可以通过线性查找(即按列值顺序查找)，快速完成一个范围查询。比如，我现在要执行下面这条SQL：SELECT * FROM user WHERE age >= 15见上图绿色箭头：页1 -> 页2：遍历页1中的元组记录，由于页1节点中第一个元组记录的age元素为15，查询条件age>=15，15 >= 15，所以，沿着页1指向页2的指针，定位到页2节点。页2 -> 页4：遍历页2中的元组记录，由于页2节点中第一个元组记录的age元素为15，查询条件age>=15，同样15 >= 15，所以，沿着页2指向页4的指针，定位到页4的节点。页4 -> 页5 -> 页6 -> 页7：页4、页5、页6和页7节点之间通过双向指针(正向和逆向)连接组成双向链表，每个节点内部所有记录通过一个单向指针(正向)连接组成单向链表，且所有记录按照索引index_age_birth内列值升序排列，即页4 ~ 页7节点内所有记录的age元素一定都大于等于15且升序排列，所以，我们只需从页4内的第一条记录开始遍历其指针连接的所有后续记录，找到这些age >= 15的记录的主键id，即2、5、6、8、3、7、4、1，最后，根据这些主键id去聚簇索引查找相应记录就行了，同样，查找方法我会在《InnoDB是顺序查找B-Tree叶子节点的吗？》中详细讲解。