B+树索引的由来

从前面讲的InnoDB数据页结构，特别是页目录，我们可以了解到，记录在页里面是以单链表的形式存在，而页与页之间构成了双向链表。

那么我们应该采取什么样的方式来更高效查询数据呢？

1.我们先来假设不了解什么是索引，我们会怎么查找？

比如根据主键条件搜索，可以再页目录中用二分查找查到属于那条记录

如果是非主键列呢，因为在数据页中并没有对非主键列建立所谓的 页目录，可能要一个一个按顺序找，知道找到匹配的记录

2.如果在很多页中查找？

大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

1. 定位到记录所在的页。

2. 从所在的页内中查找相应的记录。

   在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果。所以祖国和人民都在期盼一种能高效完成搜索的方法， 索引同志就要亮相登台了。

B+树索引

我们现在就遇到了个难题，在一个数据页里面根据主键查询记录，可以很快的查询出来，但是数据库的数据会越来越多，数据页也会越来越多，页与页之间现在没有办法根据主键查到记录属于哪个页？

要是能像一个数据页里面根据二分法查记录就好，咦！没错，就是这个思路！

设计InnoDB的大叔，给多个数据页分配了各自的目录，方便查找到某个数据页，比如下面

就像一本字典，大部分装着对单词的解释（数据页），前面一部分是目录（存放目录项记录的数据页），都占据着书本的空间，但是起到方便查找的作用

从图中可以看出来，我们新分配了一个编号为 30 的页来专门存储 目录项记录 。这里再次强调一遍 目录项记录和普通的 用户记录 的不同点：

• 目录项记录 的 record_type 值是1，而普通用户记录的 record_type 值是0。
• 目录项记录 只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列。
• 还记得我们之前在唠叨记录头信息的时候说过一个叫 min_rec_mask 的属性么，只有在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。

除了上述几点外，这两者就没啥差别了，它们用的是一样的数据页（页面类型都是 0x45BF ，这个属性在 File Header 中，忘了的话可以翻到前边的文章看），页的组成结构也是一样一样的（就是我们前边介绍过的7个部分），都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。现在以查找主键为 20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储 目录项记录 的页，也就是页 30 中通过二分法快速定位到对应目录项，因为 12 < 20 < 209 ，所 以定位到对应的记录所在的页就是 页9。
2. 再到存储用户记录的 页9 中根据二分法快速定位到主键值为 20 的用户记录。

虽然说 目录项记录 中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有 16KB 大小，能存放的 目录项记录 也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的 目录项记录，该咋办呢？

当然是再多整一个存储 目录项记录 的页喽～ 为了大家更好的理解新分配一个 目录项记录 页的过程，我们假设一个存储 目录项记录 的页最多只能存放4条 目录项记录 （请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为 320 的用户记录的话，那就需要分配一个新的存储 目录项记录的页喽：

更多记录的话，或者变成这种：

注意：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

实际上这种树状结构的数据，或者说一种数据结构，这就是B+树

不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到 B+ 树这个数据结构中了，所以我们也称这些数据页为 节点 。从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为 叶子节点 或 叶节点 ，其余用来存放 目录项 的节点称为 非叶子节点 或者 内节点 ，其中 B+ 树最上边的那个节点也称为 根节点 。

索引分类

按照不同的排序规则分索引类型

聚簇索引

1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

• 页内的记录是按照主键的大小顺序排成一个单向链表。
• 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
• 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

2. B+ 树的叶子节点存储的是完整的用户记录。

   所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

   我们把具有这两种特性的 B+ 树称为 聚簇索引 ，所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处。这种 聚簇索引 并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建（后边会介绍索引相关的语句），InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在 InnoDB 存储引擎中， 聚簇索引 就是数据的存储方式（所有的用户记录都存储在了 叶子节点 ），也就是所谓的索引即数据，数据即索引。

总的说，聚簇索引就是保存了主键和其他列的完整的记录，实质上就是b+树的叶子结点。

二级索引

比方说我们用 c2 列（非主键列）的大小作为数据页、页中记录的排序规则，再建一棵 B+ 树。

这个 B+ 树与上边介绍的聚簇索引有几处不同：

1. 使用记录 c2 列的大小进行记录和页的排序，这包括三个方面的含义：

• 页内的记录是按照 c2 列的大小顺序排成一个单向链表。
• 各个存放用户记录的页也是根据页中记录的 c2 列大小顺序排成一个双向链表。
• 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的 c2 列大小顺序排成一个双向链表。

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

查询逻辑也有不同，需要先根据c2列的值，去有关c2列建的二级索引里面查所在记录的主键的值，然后再去聚簇索引查询主键所在记录，这个过程叫做回表

联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让 B+ 树按照 c2和 c3 列的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照 c2 列进行排序。
• 在记录的 c2 列相同的情况下，采用 c3 列进行排序

如图所示，我们需要注意一下几点：

• 每条 目录项记录 都由 c2 、 c3 、 页号 这三个部分组成，各条记录先按照 c2 列的值进行排序，如果记录的 c2 列相同，则按照 c3 列的值进行排序。
• B+ 树叶子节点处的用户记录由 c2 、 c3 和主键 c1 列组成。
• 千万要注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
• 建立 联合索引 只会建立如上图一样的1棵 B+ 树。
• 为c2和c3列分别建立索引会分别以 c2 和 c3 列的大小为排序规则建立2棵 B+ 树。

MySQL中创建和删除索引的语句

我们可以在创建表的时候指定需要建立索引的单个列或者建立联合索引的多个列：

CREATE TALBE 表名 ( 
   各种列的信息 ··· ,  
   [KEY|INDEX] 索引名 (需要被索引的单个列或多个列) 
)

其中的 KEY 和 INDEX 是同义词，任意选用一个就可以。我们也可以在修改表结构的时候添加索引：

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);

也可以在修改表结构的时候删除索引：

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

比方说我们想在创建 index_demo 表的时候就为 c2 和 c3 列添加一个 联合索引 ，可以这么写建表语句：

CREATE TABLE index_demo( 
   c1 INT, 
   c2 INT, 
   c3 CHAR(1), 
   PRIMARY KEY(c1), 
   INDEX idx_c2_c3 (c2, c3) 
);

在这个建表语句中我们创建的索引名是 idx_c2_c3 ，这个名称可以随便起，不过我们还是建议以 idx_ 为前缀，后边跟着需要建立索引的列名，多个列名之间用下划线 _ 分隔开。如果我们想删除这个索引，可以这么写：

ALTER TABLE index_demo DROP INDEX idx_c2_c3;

总结：就是套中套，数据页根据页目录来二分查找记录，然后再给页建个目录，好听点叫索引，这样查找的顺序就是先去装有目录项的数据页查询到哪个数据页，然后数据页中，根据页目录查询记录，注意非主键条件，存在回表操作！