MySQL InnoDB B+树索引原理及使用

原理

聚簇索引

结构图如下:

1. 每个页都是一个树节点，页内的记录按照主键的大小顺序组成一个单向链表，同一层的页也是根据页中用户记录的主键大小顺序组成一个双向链表，所有节点都是数据类型的页（在File Header
   中的页面类型都是0x45BF
   ），页的组成结构也一样，都会为主键值生成Page Directory
   （页目录）
   

2. 最上层的那个节点为根节点，除最下层外所有节点为内节点，内节点页中的每条用户记录对应一个下层节点页，存储对应节点页的页号以及该叶子节点的最小主键值
   

3. 最下层的所有节点为叶子节点，存储了所有列的值（包括隐藏列）
   

内节点页与叶子节点页的区别:

• 内节点记录的record_type
  值是1，普通用户记录的record_type
  值是0
  

• 内节点记录只有主键值和页的编号两个列，而普通的用户记录包括所有列（包括隐藏列）
  

• 内节点记录中的主键值最小的记录的min_rec_mask
  值为1
  ，其他别的记录的min_rec_mask
  值都是0
  
  

二级索引
示例图: 

与聚簇索引的区别：

• 使用索引列的大小进行记录和页的排序，而不是主键

• 叶子节点不存储完整的用户记录，而是索引列+主键
  的值

• 内节点记录中不是主键+页号
  ，而是索引列+页号
  

• 根据索引列
  的值查找完整的用户记录，需要先查找二级索引B+树获取到记录的主键值，然后到聚簇索引
  中再查一遍，这个过程也称回表
  
  

联合索引

示例图:

本质上也是一个二级索引，只是索引列
由一个列变为多个列，排序按照联合索引列的顺序多列排序

B+树索引的注意事项

• B+树索引的根节点自诞生起，便不会再移动。只要我们对某个表建立一个索引，它的根节点
  的页号便会被记录到某个地方，以后InnoDB
  存储引擎需要使用这个索引时，都会从那个固定的地方取出根节点
  的页号，从而访问到这个索引。

  B+
  树的形成过程：

  1. 创建B+
  树索引时，为这个索引创建一个根节点
  页面，表中没有数据的时，根节点
  中既没有用户记录，也没有目录项记录

  2. 向表中插入用户记录时，先把用户记录存储到根节点
  中

  3. 当根节点
  中的可用空间用完时，将根节点
  中的所有记录复制到一个新分配的页，然后对新页进行页分裂
  ，得到另一个新页，新插入的记录被分配到页分裂产生的新页中，根节点
  升级为存储目录项记录的页

  
  

• 二级索引内节点的目录项记录的内容实际上是由索引列+主键+页号三个部分构成，从而保证B+
  树每一层节点中各条目录项记录除页号
  这个字段外是唯一的

  
  

• InnoDB
  的一个数据页至少可以存放两条记录
  

MyISAM的索引方案

MyISAM
也使用树形结构，但是将索引和数据分开存储：

• 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件
  。数据文件不划分数据页，有多少记录就往这个文件中塞多少记录。每条记录对应一个行号，通过行号来快速访问到一条记录。

  
  

• 索引信息存储到索引文件
  中，MyISAM
  会单独为表的主键创建一个索引，该索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号
  的组合。也就是先通过索引找到行号，再通过行号去找对应的记录！也就是说MyISAM
  中的索引全部都是二级索引
  ！

  
  

• 对主键之外的列建立索引或者联合索引，原理和InnoDB
  中的索引差不多，不过在叶子节点处存储的是相应的列 + 行号
  。这些索引也全部都是二级索引
  。
  

MyISAM的行格式有定长记录格式（Static）、变长记录格式（Dynamic）、压缩记录格式（Compressed）。

• 对于定长记录格式，一条记录占用存储空间的大小是固定的，根据行号可以轻松算出某条记录在数据文件中的地址偏移量。上面说的就是采用定长记录格式的情况

• 对于变长记录格式，MyISAM会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。因为是拿着地址偏移量直接到文件中取数据，所以MyISAM的回表操作是十分快速的，反观InnoDB是通过获取主键之后再去聚簇索引里边儿找记录，相对就要慢一些

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

建表时指定:

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

添加索引：

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

删除索引：

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

使用

索引的代价

• 空间上: 

  每建立一个索引都要建立一棵B+
  树，每一棵B+
  树的每一个节点都是一个数据页，一个页默认会占用16KB
  的存储空间，一棵很大的B+
  树由许多数据页组成，会占用很大一片存储空间。
  

• 时间上: 

  每次对表中的数据进行增、删、改操作时，都需要修改各个B+
  树索引。不论是叶子节点中的记录(用户记录)，还是内节点中的记录（目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。增、删、改操作可能会对节点和记录的排序造成破坏，存储引擎需要额外的时间进行记录移位、页面分裂、页面回收等操作来维护好节点和记录的排序。

B+树索引的适用条件

• 全值匹配(即等于)

• 匹配左边的列:

  对于联合索引的等值匹配，搜索条件中包含一个或多个联合索引中最左边的列

• 匹配列前缀: 

  对于字符串类型的索引，只匹配它的前缀也可以快速定位记录，如： LIKE 'As%';

• 匹配范围值：

  如大于，小于，between等

  对于联合索引，对多个列都进行范围查找时只能用到最左边那个索引列，但是如果左边的列是精确查找，则右边的列可以使用索引进行范围查找

• 排序

  对于联合索引
  ，ORDER BY
  子句中列的顺序必须按照索引列的顺序，部分联合索引列排序需遵从最左原则，左边列的值为常量，也可以使用后边的列进行排序。

  对于排序列不在同一个索引，使用UPPER
  函数等修饰过排序列以及联合索引中ASC
  、DESC
  混用时，无法使用索引进行排序

• 分组

  对于联合索引
  ，分组列的顺序也需要和索引列的顺序一致，也可以只使用索引列中左边的列进行分组

• 覆盖索引

  只查询索引列，可避免回表查询聚簇索引
  

如何挑选索引

1. 只为用于搜索、排序或分组的列创建索引

2. 考虑列的基数
   （某一列中不重复数据的个数）

3. 索引列类型尽可能小，能用INT
   就不用BIGINT
   

4. 索引字符串前缀，只对字符串的前几个字符进行索引（二级索引的记录中只保留字符串前几个字符）

5. 只有索引列在比较表达式中单独出现才可以适用索引

6. 主键设置AUTO_INCREMENT
   属性，可减少聚簇索引
   发生页面分裂和记录移位的情况

7. 定位并删除表中重复和冗余的索引

8. 尽量使用覆盖索引
   进行查询，避免回表
   的性能损耗