B+Tree

B+Tree在InnoDB中的应用

上一篇文章分析了数据页结构，通过文件头部信息也只知道数据页之间是通过双向链表的形式组织起来的，而数据页内的记录是按照主键大小通过单向链表的形式组织起来的。看起来像这样：

先抛出一个问题：假如我们想查找主键为X值的记录，怎么查找？在哪个数据页上？ 只要我们知道哪个数据页就好办了，找到对应数据页在页目录上通过二分查找就知道在哪个槽slot上，然后通过遍历找到对应的记录。

在哪个数据页上？虽然数据页之间通过双向链表的形式组织起来，但是我们不能通过遍历的方式查找，对于庞大的数据效率很低。InnoDB的做法是将每个页的最小主键值和页号提取出来，放入另外一个数据页，做法类似数据页内的页目录，我们可以称为目录项数据页，目录项数据页里存储的记录record_type=1；当目录项数据页超过16k，则再申请一个目录项数据页，同样目录项数据页之间以双向链表形式组织起来，当目录项数据页很多时那么再从目录项数据页提取最小主键值和页号，放入另外一个数据页。看起来像这样：

目录项数据页里的记录与用户数据页里的记录有这几点区别：
- 目录项记录的record_type值是1，而普通用户记录的record_type值是0
- 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列
- 记录头信息里的min_rec_mask的属性只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0
存放目录项的数据页与存放用户数据的数据页没什么区别，数据页结构也一样，数据页里面都有页目录，同样可以使用二分查找法进行查找。现在根据主键查找用户数据可以分为以下步骤，例如根据上图的B+Tree查找主键值为2的用户数据：
1. 从根节点（最上层数据页）通过二分查找确定主键值为2的数据页编号是4
2. 到编号为4的数据页查找主键值为2的数据页，同样二分查找确定存放主键值为2的用户数据在编号为7的数据页
3. 同样到编号为7的数据页查找用户数据，具体方法不再说明
以上图3层B+Tree为例计算一下我们能够存放多少数据，当叶子结点可以存放100条用户数据，非叶子结点可以存放1000条目录项数据，那么整颗树可以存放1000 X 1000 X 100=100000000，那么4层会更多。同时查找很快，只能说设计很精妙

聚簇索引

上面介绍的B+树是以主键值大小做索引，它有两个特点：
1. 使用记录主键值的大小进行记录和页的排序
  - 页内的记录是按照主键的大小顺序排成一个单向链表
  - 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
  - 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表
2. B+树的叶子节点存储的是完整的用户记录（完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列））
具有这两种特性的B+树称为聚簇索引，聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引

二级索引

上面所介绍的是以主键值做索引，实际使用时经常有其他列做索引，例如使用用户id做索引等，如下表：
```
  CREATE TABLE `t_award` (
    `Id` INT UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '记录ID',
    `gid` INT NOT NULL DEFAULT '0' COMMENT '用户GID',
    `begin_time` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '活动起始时间',
    `end_time` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '活动结束时间',
    `total` INT NOT NULL DEFAULT '0' COMMENT '总奖励金额',
    `earn` INT NOT NULL DEFAULT '0' COMMENT '获得奖励金额',
    `rank` SMALLINT NOT NULL DEFAULT '0' COMMENT '排名',
    `status` TINYINT NOT NULL DEFAULT '0' COMMENT '领取状态',
    `get_time` INT NOT NULL DEFAULT '0' COMMENT '获奖时间',
    `create_time` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `update_time` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
    PRIMARY KEY (`Id`),
    KEY `idx_gid` (`gid`)
  ) ENGINE=INNODB DEFAULT CHARSET=utf8mb4;
```
上表的索引idx_gid就是一个二级索引，InnoDB的做法是在创建一颗B+树，这颗B+树与上面提到的聚簇索引有些不同：
1. 使用记录gid列的大小进行记录和页的排序，这包括三个方面的含义：
  - 页内的记录是按照gid列的大小顺序排成一个单向链表
  - 各个存放用户记录的页也是根据页中记录的gid列大小顺序排成一个双向链表
  - 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的gid列大小顺序排成一个双向链表
2. B+树的叶子节点存储的并不是完整的用户记录，而只是gid列+主键这两个列的值
3. 目录项记录中不再是主键+页号的搭配，而变成了gid列+页号的搭配
以gid为查找条件那么查找过程会是这样：
1. 从这颗B+树的根节点确定下一个目录项
2. 直到找到叶子结点，从叶子节点找到对应用户记录
3. 上面提到这样的B+树的叶子结点只是存储了gid列+主键这两个列的值，找到具体的用户记录后根据主键值到聚簇索引中再查找一遍完整的用户记录
上面第3步到聚簇索引中查找一遍完整的用户记录这个过程称为回表

在查找过程中是从目录项记录开始的，对于二级索引目录项记录存储的是索引列的值、页号，当匹配到索引列的值便找到了页号，有一个问题：如果索引列的值都相等怎么确定叶子结点页号？所以需要保证在B+树的同一层非叶子节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的非叶子节点的目录项记录的内容实际上是由三个部分构成的：
1. 索引列的值
2. 主键值
3. 页号
就是我们把主键值也添加到二级索引非叶子节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的

联合索引

把上面数据表创建语句修改一下：
```
  CREATE TABLE `t_award` (
    `Id` INT UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '记录ID',
    `gid` INT NOT NULL DEFAULT '0' COMMENT '用户GID',
    `begin_time` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '活动起始时间',
    `end_time` VARCHAR(32) NOT NULL DEFAULT '' COMMENT '活动结束时间',
    `total` INT NOT NULL DEFAULT '0' COMMENT '总奖励金额',
    `earn` INT NOT NULL DEFAULT '0' COMMENT '获得奖励金额',
    `rank` SMALLINT NOT NULL DEFAULT '0' COMMENT '排名',
    `status` TINYINT NOT NULL DEFAULT '0' COMMENT '领取状态',
    `get_time` INT NOT NULL DEFAULT '0' COMMENT '获奖时间',
    `create_time` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `update_time` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
    PRIMARY KEY (`Id`),
    KEY `idx_gid_status` (`gid,status`)
  ) ENGINE=INNODB DEFAULT CHARSET=utf8mb4;
```
此时索引idx_gid_status的意思是：
1. 先把各个记录和页按照gid列进行排序
2. 在记录的gid列相同的情况下，采用status列进行排序
此时树节点的特点：
- 每条目录项记录都由gid、status、页号这三个部分组成，各条记录先按照gid列的值进行排序，如果记录的gid列相同，则按照status列的值进行排序
- B+树叶子节点处的用户记录由gid、status和主键Id列组成
上表以gid、status的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引，这个表述和 “以gid、status列的大小分别建立索引” 的意义是完全不同的，不同点如下：
1. 以gid、status的大小为排序规则建立的索引（即联合索引）会创建一颗B+Tree
2. 以gid、status列的大小分别建立索引会创建两颗B+Tree，分别是以gid列的大小的B+Tree和以status列的大小的B+Tree

B+Tree的创建

B+Tree的创建过程：
1. 创建表时，会创建以主键大小为排序规则的B+Tree(即聚簇索引)，同时还会创建指定的二级索引和联合索引对应的B+Tree，会为这些索引分别创建一个根节点页面，最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录
2. 随后向表中插入用户记录时，先把用户记录存储到这个根节点中
3. 当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页
一个B+树索引的根节点自诞生之日起，就不会再移动。这样只要对某个表建立一个索引，那么它的根节点的页号便会被记录到数据字典，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从数据字典取出根节点的页号，从而来访问这个索引

索引的创建和删除

索引的创建可以通过创建表的语句指定，例如上表，同时InnoDB和MyISAM会自动为主键或者声明为UNIQUE的列去自动建立B+树索引，创建完表也可以通过语句创建：
```
  ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);
```
删除索引：
```
  ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;
```
索引名可以随便命名，但是到生成环境要按照规范命名，例如以idx_为前缀，后接索引列名称，多个索引列以_连接，类似idx_gid_status这样

王仕柱

B+Tree

B+Tree在InnoDB中的应用

聚簇索引

二级索引

联合索引

B+Tree的创建

索引的创建和删除