我们知道一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，所以查询语句的优化显然是重中之重。

一、平衡多路查找树（B-Tree）

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。因此在讲 B-Tree之前先了解下磁盘的相关知识。系统从磁盘读取数据到内存时是以磁盘块block为基本单位，大小为4K，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

InnoDB存储引擎中有页Page的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在 MySQL中可通过如下命令查看页的大小：

mysql> show variables like 'innodb_page_size';

系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key,data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。

一棵m阶的B-Tree有如下特性：
【1】每个节点最多有m个孩子；
【2】除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子；
【3】若根节点不是叶子节点，则至少有2个孩子；
【4】所有叶子节点都在同一层，且不包含其它关键字信息；
【5】每个非终端节点包含n个关键字信息P0,P1,…Pn, k1,…kn；
【6】关键字的个数n满足：ceil(m/2)-1 <= n <= m-1；
【7】ki(i=1,…n)为关键字，且关键字升序排序；
【8】Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)；

B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支，如下图所示为一个3阶的B-Tree：

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：
【1】根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
【2】比较关键字29在区间（17,35），找到磁盘块1的指针P2。
【3】根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
【4】比较关键字29在区间（26,30），找到磁盘块3的指针P2。
【5】根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
【6】在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

二、B+Tree

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现索引结构。

从B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的 key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在 B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：
【1】非叶子节点只存储键值信息；
【2】所有叶子节点之间都有一个链指针；
【3】数据记录都存放在叶子节点中；

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），内部索引指针大小在 InnoDB源码中设置为 6个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+6B)=1170行数据。因为深度为3，表示此时一张表最多存储（这里假设叶子节点一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）16[叶子节点只能存16行数据] * 1170 * 1170 = 21902400行数据。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引clustered index和辅助索引secondary index。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

通过上面的分析，我们知道IO次数取决于b+数的高度h，假设当前数据表的数据为N，每个磁盘块的数据项的数量是m，则有h=㏒(m+1)N，当数据量N一定的情况下，m越大，h越小；而m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1时将会退化成线性表。

三、B+树索引

InnoDB数据页的主要组成部分。各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录。再通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽。

在一个页中的查找：
【1】以主键为搜索条件： 这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
【2】以其他列作为搜索条件：
对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。

在很多页中查找：
【1】定位到记录所在的页。
【2】从所在的页内中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。

四、索引（页分裂+页目录）

先建一个 index_demo表：

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)

简化index_demo表的行格式后的示意图：

【1】record_type： 这个属性表示当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。
【2】next_record： 记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量。

把一些记录放到页里边的示意图就是：

一个简单的索引方案： 我们为根据主键值快速定位一条记录在页中的位置而设立的页目录，目录中记录的数据页必须下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

我们这里需要做一个假设：假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向index_demo表插入3条记录：

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

从图中可以看出来，index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入一条记录：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：页的双向链表也进行了重新的定义。这个过程叫做页分裂。

由于数据页的编号可能并不是连续的，所以在向 index_demo表中插入许多条记录后，可能是这样的效果：

因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：
【1】页的用户记录中最小的主键值，我们用 key来表示。
【2】页号，我们用page_no表示。
所以我们为上边几个页做好的目录就像这样子：

​ 比方说我们想找主键值为20的记录，具体查找过程分两步：
【1】先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12 < 20 < 209），它对应的页是页9。
【2】再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

这个目录有一个别名，称为索引。

五、InnoDB中的索引方案

在InnoDB中复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。用record_type来区分普通的用户记录还是目录项记录。

一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，会再多整一个存储目录项记录的页。

假设一个存储目录项记录的页最多只能存放4条目录项记录（请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为320的用户记录的话：

在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

从图中可以看出来，我们的实际用户记录其实都存放在 B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点。

聚簇索引： 我们上边介绍的 B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：
【1】使用记录主键值的大小进行记录和页的排序；
【2】B+树的叶子节点存储的是完整的用户记录。
我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建（后边会介绍索引相关的语句），InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

六、二级索引

这个B+树与上边介绍的聚簇索引有几处不同：
【1】使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
 ● 页内的记录是按照c2列的大小顺序排成一个单向链表。
 ● 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
 ● 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。

【2】B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
【3】目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

以查找 c2列的值为4的记录为例：
【1】确定目录项记录页，也就是页44；
【2】通过目录项记录页确定用户记录真实所在的页：在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。
【3】在真实存储用户记录的页中定位到具体的记录。
【4】但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。这个过程被称为回表。

如果把完整的用户记录放到叶子节点是可以不用回表，但是太占地方了呀～相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

七、联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让 B+树按照c2和c3列的大小进行排序：
【1】先把各个记录和页按照c2列进行排序。
【2】在记录的c2列相同的情况下，采用c3列进行排序

如图所示，我们需要注意一下几点：
【1】每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
【2】B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

八、覆盖索引

为了彻底告别回表操作带来的性能损耗，我们建议：最好在查询列表里只包含索引列。

SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'

因为我们只查询name, birthday, phone_number这三个索引列的值，所以在通过idx_name_birthday_phone_number索引得到结果后就不必到聚簇索引中再查找记录的剩余列，也就是country列的值了，这样就省去了回表操作带来的性能损耗。我们把这种只需要用到索引的查询方式称为索引覆盖。我们很不鼓励用*号作为查询列表，最好把我们需要查询的列依次标明。

(adsbygoogle = window.adsbygoogle || []).push({});