在 InnoDB 存储引擎中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为 索引组织表。又因为 InnoDB 使用 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。如果表中数据值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，则两棵索引树的示例示意图如下。

根据叶子节点的内容，索引类型分为主键索引（聚簇索引）和非主键索引（二级索引）。

• 主键索引的叶子节点保存的是数据页，包含完整的行记录；非叶子节点保存的仅仅是键值（指向的数据页中的最小索引值）及指向数据页的偏移量。

• 非主键索引的叶子节点内容是主键的值。

基于主键索引和普通索引的查询有什么区别？如果语句是 select from T where ID=500，即主键查询，则只需要搜索 ID 这棵 B+ 树。如果语句是 select from T where k=5，即普通索引查询，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。因此，基于非主键索引的查询需要多扫描一棵索引树。

B+ 树索引结构

B+ 树索引是数据库系统中最为常见的一种索引数据结构，几乎所有的关系型数据库都支持它。因为它是目前为止排序最有效率的数据结构。像二叉树、哈希索引、红黑树、SkipList 等在海量数据基于磁盘存储效率方面远不如 B+ 树索引高效。当数据足够多时，B+ 树的根节点到任意叶子节点的路径是固定的，而像 SkipList 的头节点到目标节点的路径是不固定的，所以 SkipList 的磁盘 IO 次数比 B+ 树要多。

B+ 树由 B 树和索引顺序访问方法演化而来。从 MySQL 获取数据消耗的时间主要是 IO 操作消耗的时间，因此减少 IO 操作次数，才能缩短获取数据需要的时间，而一般获取数据需要操作的 IO 次数等于树的高度，所以减少树的高度，也就是减少了 IO 次数，从而达到减少获取数据消耗的时间。

B+ 树中的 B 不是代表二叉（binary），而是代表平衡（balance），因为 B+ 树是从最早的平衡二叉树演化而来的，但是 B+ 树不是一个二叉树，而是一个多叉树。

在 B+ 树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，同一层的各叶子节点通过双向指针进行连接。每个叶子节点是一个完整的数据页，默认大小为 16 KB。下图是一棵高度为 2 的 B+ 树，每页可存放 4 条记录。所有记录都在叶子节点上且是顺序存放。

其中，各个数据页之间组成一个双向链表，每个数据页中的记录会按照主键顺序组成单向链表；每一个数据页中还有一个页目录，方便按照主键查询记录。数据页的结构如下：

页目录通过槽把记录分成不同的小组，每个小组有若干条记录。如图所示，记录中最前面的小方块中的数字，代表的是当前分组的记录条数，最小和最大的槽指向 2 个特殊的伪记录。有了槽之后，我们按照主键搜索页中记录时，就可以采用二分法快速搜索，无需从最小记录开始遍历整个页中的记录链表。

B+ 树搜索过程：

B+ 树索引并不能直接找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页，然后数据库通过把整个页读入到内存，再在内存中通过类似二分查找的方式进行查找，最后得到要查找的数据。二分查找过程依赖页目录的槽。举个例子，如果要搜索主键（PK）=15 的记录：

• 先二分得出槽中间位是 (0+6)/2=3，看到其指向的记录是 12＜15，所以需要从 #3 槽后继续搜索记录；
• 再使用二分搜索出 #3 槽和 #6 槽的中间位是 (3+6)/2=4.5 取整 4，#4 槽对应的记录是 16＞15，所以记录一定在 #4 槽中；
• 再从 #3 槽指向的 12 号记录开始向下搜索 3 次，定位到 15 号记录。

  1. 插入操作

  B+ 树的插入操作必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到 B+ 树的三种情况，每种情况都可能会导致不同的插入算法。

假设，当前 B+ 树的存储状态如下图所示，暂时忽略叶子节点之间的双向链表：

如果要向图中的 B+ 树插入键值 95，则数据页和索引页都满了，此时需要做两次拆分，如下图所示：

可以看到，不管怎么变化，B+ 树总是会保持平衡。但为了保持平衡对于新插入的键值可能需要做大量的拆分页的操作。因为 B+树结构主要用于磁盘，页的拆分意味者磁盘的操作。此外还影响数据页的利用率。原本放在一个页中的数据现在分到两个页中，整体空间利用率降低一半。所以应该在尽可能的情况下减少页的拆分操作。因此 B+ 树同样提供了类似平衡二叉树的旋转（Rotation）功能。

旋转发生在 Leaf Page 已经满，但其左右兄弟节点没有满的情况下。此时 B+ 树不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。通常左兄弟会被首先检查用来做旋转操作。假设 B+ 树结构如下图所示：

此时，若插入键值 70，B+ 树并不会急于去拆分叶子节点，而是去做旋转操作，得到下图所示的结构

可以看到，采用旋转操作使 B+ 树减少了一次页的拆分操作，同时这棵 B+ 树的高度依然还是 2。

2. 删除操作

B+ 树使用填充因子来控制树的删除变化，50% 是填充因子可设的最小值。B+ 树的删除操作同样必须保证删除后叶子节点中的记录依然排序，同插入一样，B+ 树的删除操作同样需要考虑以下三种情况：

假设当前 B+ 树结构如下图所示：

此时，若删除值为 70 的键则需要进行合并操作，同样在删除 Index Page 中的记录后也需要做 Index Page 的合并操作。合并后的结构如下图所示：

B+ 树索引分类

1. 聚簇索引

上面讲到，InnoDB 存储引擎表是索引组织表，即表中数据按照主键顺序存放，而聚簇索引就是按每张表的主键构造一棵 B+树，叶子节点中存放的即为整张表的行记录数据，也将聚簇索引的叶子节点称为数据页。聚簇索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树一样，每个数据页通过一个双向链表来连接。

由于实际的数据页只能按照一棵 B+ 树进行排序，因此每张表只能拥有一个聚簇索引。在多数情况下，优化器倾向于采用聚簇索引，因为聚簇索引能够在 B+ 树索引的叶子节点上直接找到数据，避免回表。

此外，聚簇索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点：一是前面说过的数据页通过双向链表链接，数据页按照主键的顺序排序；另一点是每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

2. 二级索引

对于二级索引（也称非聚集索引），叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark），该书签用来告诉 InnoDB 存储引擎哪里可以找到与索引相对应的行数据。由于 InnoDB 存储引擎表是索引组织表，因此书签就是相应行数据的聚簇索引键。

回表
二级索引的存在并不影响数据在聚簇索引中的组织，因此每张表上可以有多个二级索引。当通过二级索引来寻找数据时，InnoDB 存储引擎会遍历二级索引并通过叶子节点上的书签指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

举个例子，有个索引是针对用户名字段创建的，索引记录上面方块中的字母是用户名，按照顺序形成链表。如果我们要搜索用户名为 b 的数据，经过两次定位可以得出在 #5 数据页中，查出所有的主键为 7 和 6，再拿着这两个主键继续使用聚簇索引进行两次回表得到完整数据。

3. 组合索引

组合索引（Compound Index）是指由多个列所组合而成的 B+ 树索引，这和我们之前介绍的 B+ 树索引的原理完全一样，只是之前是对一个列排序，现在是对多个列排序。但是你一定要意识到（a,b）和（b,a）这样的组合索引，其排序结果是完全不一样的。

对组合索引（a,b）来说，因为其对列 a、b 做了排序，所以它可以对下面两个查询进行优化：

SELECT * FROM table WHERE a = ?
SELECT * FROM table WHERE a = ？ AND b = ？
SELECT * FROM table WHERE a = ？ ORDER BY b DESC

但是下面的 SQL 无法使用组合索引（a,b），因为（a,b）排序并不能推出（b,a）排序：

SELECT * FROM table WHERE b = ?
SELECT * FROM table WHERE b = ？ ORDER BY a DESC

4. 前缀索引

MySQL 支持前缀索引，你可以定义字符串的一部分作为索引。默认地，如果你创建索引的语句不指定前缀长度，那么索引就会包含整个字符串。

mysql> alter table SUser add index index1(email);
mysql> alter table SUser add index index2(email(6));

第一个语句创建的 index1 索引里面，包含了每个记录的整个字符串；而第二个语句创建的 index2 索引里面，对于每个记录都是只取前 6 个字节。所以 email(6) 这个索引结构占用的空间会更小，这是前缀索引的优势。但同时带来的损失是，可能会增加额外的记录扫描次数。

假设我们要查找 email 字段为 zhangssxyz@xxx.com 的记录，如果使用的是 index1，执行顺序是这样的：

• 从 index1 索引树找到满足索引值是 “zhangssxyz@xxx.com” 的这条记录，取得 ID2 的值。
• 到主键上查到主键值是 ID2 的行，判断 email 的值是正确的，将这行记录加入结果集。
• 取 index1 索引树上刚刚查到的位置的下一条记录，发现已经不满足条件了，循环结束。

整个过程只需要回主键索引取一次数据，所以系统认为只扫描了一行。如果使用的是 index2，执行顺序是这样的：

• 从 index2 索引树找到满足索引值是 “zhangs” 的记录，找到的第一个是 ID1。
• 到主键上查到主键值是 ID1 的行，判断出 email 的值不是 “zhangssxyz@xxx.com”，这行记录丢弃。
• 取 index2 上刚刚查到的位置的下一条记录，发现仍然是 “zhangs”，取出 ID2，再到 ID 索引上取整行然后判断，这次值对了，将这行记录加入结果集
• 重复上一步，直到在 idxe2 上取到的值不是 “zhangs” 时，循环结束。

在这个过程中，要回主键索引取四次数据，也就是扫描了 4 行。通过这个对比可以发现，使用前缀索引后，可能会导致查询语句读数据的次数变多。但对这个查询语句来说，如果你定义的 index2 是 email(7），那满足前缀 “zhangss” 的记录只有一个，也能够直接查到 ID2，只扫描一行就结束了。也就是说使用前缀索引，定义好长度，就可以做到既节省空间，又不用额外增加太多的查询成本。

注意，使用前缀索引就用不上覆盖索引对查询性能的优化了，这也是在选择是否使用前缀索引时需要考虑的一个因素。

覆盖索引

select ID from T where k between 3 and 5

当执行上面这个语句时，只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经覆盖了我们的查询需求，我们称为覆盖索引。

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。需要注意的是，在引擎内部使用覆盖索引在索引 k 上其实读了三个记录，R3~R5（对应的索引 k 上的记录项），但是对于 MySQL 的 Server 层来说，它就是找引擎拿到了两条记录，因此 MySQL 认为扫描行数是 2。

此外，对于联合索引中其实保存了多个索引列的值，如下图所示：

图中，叶子节点每一条记录的第一和第二个方块是索引列的数据，第三个方块是记录的主键。如果我们需要查询的是索引列索引或联合索引能覆盖的数据，那么查询索引本身已经“覆盖”了需要的数据，不再需要回表查询。因此这种情况也叫作索引覆盖。

最左前缀原则

B+ 树这种索引结构，可以利用索引的最左前缀来定位记录。我们用 (name，age) 这个联合索引来进行分析。

可以看到，索引项是按照索引定义里面出现的字段顺序排序的。当查到所有名字是“张三”的人时，可以快速定位到 ID4，然后向后遍历得到所有需要的结果。当查找所有名字第一个字是“张”的人时，也能用上索引，查找到第一个符合条件的记录是 ID3，然后向后遍历，直到不满足条件为止。

在联合索引的情况下，数据是按照索引第一列排序，第一列数据相同时才会按照第二列排序。也就是说，如果我们想使用联合索引中尽可能多的列，查询条件中的各个列必须是联合索引中从最左边开始连续的列。

因此我们可以知道，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

在建立联合索引时，如何安排索引内的字段顺序？
这里我们的评估标准是索引的复用能力。因为可以支持最左前缀，所以当已经有了 (a,b) 这个联合索引后，一般就不需要单独在 a 上建立索引了。因此，第一原则是：如果通过调整顺序可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

怎么选择建联合索引还是多个独立索引？
如果你的搜索条件经常会使用多个字段进行搜索，那么可以考虑针对这几个字段建联合索引；同时，针对多字段建立联合索引，使用索引覆盖的可能更大。如果只会查询单个字段，可以考虑建单独的索引，毕竟联合索引保存了不必要字段也有成本。

索引下推

当满足最左前缀原则的时候，最左前缀可以用于在索引中定位记录。那不符合最左前缀的部分会怎么样呢？我们还以联合索引 (name，age) 为例。如果需要检索出表中 “名字第一个字是张且年龄是 10 岁的所有男孩”。

mysql> select * from tuser where name like '张%' and age=10 and ismale=1;

通过最左前缀原则，这个语句在搜索索引树的时候，直接通过“张”找到了第一个满足条件的记录 ID3。然后再判断其他条件是否满足。在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值。图中特意去掉了 age 的值，因为在这个过程中 InnoDB 并不会去看 age 的值，它只是按顺序地把 “name 第一个字是张” 的记录一条条取出来回表。因此，需要回表 4 次。

而 MySQL 5.6 引入的索引下推优化（Index Condition Pushdown），可以在索引遍历过程中，对索引中包含的字段先做 WHERE 判断，直接过滤掉不满足条件的记录，减少回表次数。

InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。因此这里只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。