第五章 索引与算法

索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序可能会受到影响。索引太少，对查询性能又会产生影响。要找到一个合适的平衡点，对程序的性能至关重要。

1 InnoDB存储引擎索引概述

InnoDB存储引擎支持以下几种常见的索引：

• B+树索引
• 全文索引
• 哈希索引

前面已经提到，InnoDB存储引擎的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能认为干预是否在一张表内生成哈希索引。

B+树索引就算传统意义上的索引，这是目前关系型数据库中查找最常用和最有效的索引。B+树索引的构造类似于二叉树，根据键值快速找到数据。

注意：B+树中的B不是代表二叉(binary)，而是代表平衡(balance)，因为B+树是从最早的平衡二叉树演化而来，但是B+树不是一个二叉树。

另一个常常被DBA忽视的问题是：B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在页。然后数据库通过把页读入内存，再在内存中进行查找，最后找到要查找的数据。

2 数据结构与算法

B+树索引是最为常见，也是在数据库中使用最为频繁的一种索引。

2.1 二分查找法

二分查找法(binary search)也称为折半查找法，用来查找一组有序的记录数组中的某一记录，其基本思想是：记录有序排列，在查找中采用跳跃式方式查找，即先以有序数列的中点位置作为比较对象，如果要查找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半福分。通过一次比较，将查找区间缩小一半。

如有5、10、19、21、31、37、42、48、50、52这10个数，现要从这10个数中查找48这条记录，则查找方式如下：

如上图所示，用了3次就找到48这个数，如果是顺序查找，则需要8次。因此二分查找法效率相对比顺序查找法好。比如对于如上十个数来说，如果是顺序查找法分别查找的话，分别是1+2+3+4+5+6+7+8+9+10=55次，也就是平均需要(1+2+3+4+5+6+7+8+9+10)\10=5.5次。如果是二分查找法的话，分别是4+3+2+4+3+1+4+3+2+3=29次，也就是平均需要(4+3+2+4+3+1+4+3+2+3)\10=2.9次。所以就平均查找次数来说的话，二分查找法是较优的。而且在最坏的情况下，顺序查找法需要10次，二分查找法仅需要4次。

二分查找法的应用极其广泛，而且它的思想易于理解。第一个二分查找法在1946年就出现了，但是第一个完全正确的二分查找法直到1962年才出现。在数据库InnoDB引擎中，每页Page Directory中的槽是按照主键的顺序存放的，对于一条具体记录的查询是通过对Page Directory进行二分查找得到的。

2.2 二分查找树和平衡二叉树

在介绍B+树前，需要先了解一下二叉查找树。B+树是通过二叉查找树，再由平衡二叉树，B树演化而来。二叉树是一种经典的数据结构。

在二分查找树中，左子树的键值总是小于跟的键值，右子树的键值总是大于跟的键值。

如下图所示，也是二叉树，但是这种二叉树是效率较低的一种。

如果想最大性能的构造一颗二叉树，需要这颗二叉树是平衡的，从而引出新的定义-平衡二叉树，或称为AVL树。

平衡二叉树的定义：

首先二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1

平衡二叉树的查询速度的确很快，但是维护一颗平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋或右旋来得到插入或更新后的平衡性。但是平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。

举例一：

在平衡二叉树基础上，再添加一条数据，为保持二叉树现状，进行一次左旋即可。

举例二：

如下图在平衡二叉树基础上，添加一条数据后，导致需要旋转多次才能达到二叉树平衡。

3 B+树

B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问方法（ISAM，也是MyISAM引擎最初参考的数据结构），但是现实使用过程中几乎没有使用B树得情况了。

B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点，由各叶子节点指针进行连接。先看一个B+树，高度为2，每页存4条记录，扇出为5.

如下图所示，所有记录都在叶子节点上，并且顺序存放的，如果用户从最左边叶子节点开始遍历，那么得到的键值是：5、10、15、20、25、30、50、55、60、65、75、80、85、90。

3.1 B+树的插入操作

B+树的插入必须保证插入后叶子节点的记录依然有序，同时考虑插入到B+树的三种情况，每种情况可能会导致不同的插入算法：

Leaf Page满	Index Page满	操作
No	No	直接将记录插入到叶子节点
Yes	No	1.拆分leafPage 2.将中间的节点放到index page总 3.小于中间节点的记录放左边 4.大于或等于中间节点的记录放右边
Yes	Yes	1.拆分leafPage 2.小于中间节点的记录放左边 3.大于或等于中间节点的记录放右边 4.拆分indexPage 5.小于中间节点的记录放左边 6.大于中间节点的记录放右边 7.中间节点放上一层indexpage

3.2 B+树的删除操作

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

叶子节点小于填充因子	中间节点小于填充因子	操作
No	No	直接将记录从叶子节点删除，如果该节点还是index page节点，用该节点的右节点代替
Yes	No	合并叶子节点和它的兄弟节点，同时更新index page
Yes	Yes	1.合并叶子节点和它的兄弟节点 2.更新index page 3.合并index page和它的兄弟节点

4 B+树索引

B+树索引的本质就是B+树在数据库中的实现，但是B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2-4层，这也就是说查找某一键值的行记录时最多需要2到4次IO。因为一般的机械硬盘每秒至少做100次IO，2-4次的IO意味着查询时间只需要0.02~0.04秒。

数据库中的B+树索引可以分为聚集索引(clustered index)和辅助索引(secondary index)，但是不管是聚集还是辅助的索引，其内部都是B+树，即高度平衡的，叶子节点存放着所有数据。聚集索引与辅助索引不同的是，叶子节点存放的是否一整的信息。

4.1 聚集索引

InnoDB存储索引表是索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。每个数据页都通过一个双向链表来进行链接。

在多数情况下，查询优化器倾向于聚集索引，因为聚集索引能在B+树索引的叶子节点上直接找到数据。

这里人为的方式让其每个页只能存放两个行记录：

mysql> create table cluster_index (
    -> a int not null,
    -> b varchar(8000),
    -> c int not null,
    -> primary key (a),
    -> key cluster_index(c)
    -> ) engine=innodb;
Query OK, 0 rows affected (0.03 sec)

mysql> insert into cluster_index select 1,repeat('a',7000),-1;
Query OK, 1 row affected (0.00 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql> insert into cluster_index select 2,repeat('a',7000),-2;
Query OK, 1 row affected (0.00 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql> insert into cluster_index select 3,repeat('a',7000),-3;
Query OK, 1 row affected (0.00 sec)
Records: 1  Duplicates: 0  Warnings: 0

在上述例子中，插入的列b长度为7000，因此可以人为的方式使目前每个页只能存放两个行记录，接着用py_innodb_page_info工具来分析表空间，可得：

[root@zxy py_innodb_page_type]# python py_innodb_page_info.py -v /var/lib/mysql/zxy/cluster_index.ibd
page offset 00000000, page type <File Space Header>
page offset 00000001, page type <Insert Buffer Bitmap>
page offset 00000002, page type <File Segment inode>
page offset 00000003, page type <B-tree Node>, page level <0001>
page offset 00000004, page type <B-tree Node>, page level <0000>
page offset 00000005, page type <B-tree Node>, page level <0000>
page offset 00000006, page type <B-tree Node>, page level <0000>
Total number of page: 7:
Insert Buffer Bitmap: 1
File Space Header: 1
B-tree Node: 4
File Segment inode: 1

page level为0000的即是数据页，page level为0001的页，是当前聚集索引的B+树高度为2，故该页是B+树的跟。

4.2 辅助索引

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

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

举例来说：如果一颗高度为3的辅助索引树中查找数据，那需要对这颗辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在页。因此一共需要6次逻辑IO访问才能最终得到一个数据页。

4.3 B+树索引的分裂

1.索引管理

索引的创建和删除可以通过两种方法，一种是alter table，另一种是create/drop index。通过alter table创建索引的语法：

alter table table_name
| ADD {index|key} {index_name}
{index_type} {index_col_name,...} {index_option}...

alter table table_name
drop primary key
| drop {index|key} index_name

create/drop index的语法同样很简单：

create [unique] index index_name
[index_type]
on table_name {index_col_name,...}

drop index index_name on table_name

用户可以设置对整个列的数据进行索引，也可也i只索引一个列的开头部分数据，如前面创建的表t,列b为varchar(8000)，但是用户可以只索引前100个字段，如：

mysql> alter table cluster_index add key idx_b (b(100));
Query OK, 0 rows affected (0.03 sec)

若用户想要查看表中索引的信息，可以使用show index。

mysql> show index from cluster_index\G;
*************************** 1. row ***************************
        Table: cluster_index
   Non_unique: 0
     Key_name: PRIMARY
 Seq_in_index: 1
  Column_name: a
    Collation: A
  Cardinality: 2
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
*************************** 2. row ***************************
        Table: cluster_index
   Non_unique: 1
     Key_name: cluster_index
 Seq_in_index: 1
  Column_name: c
    Collation: A
  Cardinality: 2
     Sub_part: NULL
       Packed: NULL
         Null:
   Index_type: BTREE
      Comment:
Index_comment:
*************************** 3. row ***************************
        Table: cluster_index
   Non_unique: 1
     Key_name: idx_b
 Seq_in_index: 1
  Column_name: b
    Collation: A
  Cardinality: 1
     Sub_part: 100
       Packed: NULL
         Null: YES
   Index_type: BTREE
      Comment:
Index_comment:
3 rows in set (0.00 sec)

在查看index信息中有以下参数，分别代表的是：

• Table

  索引所在表名

• Non_unique

  非唯一索引，可以看到primary key是0，因为必须是唯一的

• Key_name

  索引的名字，用户可以通过这个名字执行drop index

• Seq_in_index

  索引中该列的位置，如果看联合索引idx_a_c就比较直观了

• Column_name

  索引列的名称

• Collation

  列以什么方式存储在索引中，可以是A或NULL。B+树索引总是A，即排序的。如果使用Heap存储索引，并且建立Hash索引，则为NULL

• Cardinality

  非常关键的值，表示索引中唯一值的数目的估计值。Cardinality表的行数应尽可能的接近1，如果非常小，那么用户需要考虑是否可以删除此索引。

• Sub_part

  是否是列的部分被索引。例如idx_b只索引前100个字符，那么这里显示100。否则为NULL

• Packed

  关键字是否被压缩，没有为NULL

• Null

  是否索引的列值含有NULL值，可以看到idx_b这里为YES，因为定义的列B允许NULL值。

• Index_type

  索引的类型。InnoDB存储引擎只支持B+树索引，所以显示的都是BTREE

• Comment

  注释

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的。即并非每次索引的更新都会更新该值，因为这也代价太大了。因此这个值不是完全准确的，只是一个大概的值。可以使用alalyze table table_name;更新索引Cardinality信息。

mysql> analyze table cluster_index\G;
*************************** 1. row ***************************
   Table: zxy.cluster_index
      Op: analyze
Msg_type: status
Msg_text: OK
1 row in set (0.01 sec)

2.fast index creation(快速索引创建)

该方法在创建索引的时候对表加上一个S锁。在创建辅助索引的时候，不需要重建表，因此速度较之前提高很多，并且数据库的可用性也得到了提高。删除辅助索引操作就更简单，InnoDB存储引擎只需要更新内部试图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图上对该表的索引定义即可。

但是由于该方法在索引创建过程中，对表加上了S锁，因此在创建过程中只能对该表进行读操作，若有大量的事务需要对目标表进行写操作，那么数据库的服务同样不可用。此外，FIC只限定于辅助索引，对于主键的创建和删除同样需要重建一张表。

3.Online schema change(在线架构改变)

Online Schema Change最早是由facebook实现的一种在线执行DDL的方式，并广泛的应用于Facebook的MySQL数据库。所谓"在线"是指在事务的创建过程中，可以有读写事务对表进行操作，这提高了原有MySQL数据库在DDL操作时的并发性。

4.Online DDL(在线数据定义)

虽然fast index creation可以让InnoDB存储引擎避免创建临时表，从而提高索引创建的效率。但是如上所说，索引创建时会阻塞表上的DML操作。Online schema change虽然解决了上诉的部分问题，但是还有很大的局限性。MySQL5.6版本开始支持Online DDL操作，其允许辅助索引创建的同时，还允许其他诸如insert、update、delete这类DML操作，这极大提高了MySQL数据库在生产环境的可用性。

此外，不仅是辅助索引，以下几类DDL操作还可以通过"在线"的方式进行操作：

• 辅助索引的创建与删除
• 改变自增长值
• 添加或删除外键约束
• 列的重命名

通过新的alter table语法，用户可以选择索引的创建方式：

alter table table_name
| add {index|key} {index_name}
{index_type} {index_col_name,...} {index_option} ...
algorithm [=] {default|inplcae|copy}
lock [=] {default|none|shared|exclusive}

algorithm指定了创建或删除所有的算法，copy表示按照MySQL5.1版本之前的工作模式，即创建临时表的方式。inplace表示索引创建或删除操作不需要创建临时表。default表示根据参数old_alter_table来判断是通过inplace还是copy算法，该参数默认值是off，表示采用inplace方式，如：

mysql> select @@version\G;
*************************** 1. row ***************************
@@version: 5.7.41
1 row in set (0.00 sec)

mysql> show variables like 'old_alter_table'\G;
*************************** 1. row ***************************
Variable_name: old_alter_table
        Value: OFF
1 row in set (0.00 sec)

lock部分为索引创建或删除时对表添加锁的情况，可有的选择为：

• none

  执行索引创建或删除操作时，对目标表不添加任何锁，即事务仍然可以进行读写操作，不会接收到阻塞。因此这种模式可以获得最大的并发度。

• share

  这和fast index creation类似，执行索引创建或删除时，对目标加上一个S锁。对于并发的读事务，依然可以执行，但是遇到写事务，就会发生等待操作。如果存储引擎不支持share模式，会返回一个错误信息。

• exclusive

  在exclusive模式下，执行索引创建或删除操作时，对目标表加一个X锁。读写事务都不能进行，因此会阻塞所有，这和copy方式运行得到的状态类似，但是不需要copy那样创建一张临时表

• default

  default模式首先会判断当前操作是否可以使用NONE模式，若不能，则判断是否可以使用share模式，最后判断是否可以使用exclusive模式。也就是说default会通过判断事务的最大并发性来判断执行DDL的模式

InnoDB存储引擎实现Online DDL的原理是在执行创建或删除操作的同时，将insert、update、delete这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此达到数据一致性。

这个缓存的大小由参数innodb_online_alter_log_max_size控制，默认大小是128MB。

mysql> show variables like 'innodb_online_alter_log_max_size';
+----------------------------------+-----------+
| Variable_name                    | Value     |
+----------------------------------+-----------+
| innodb_online_alter_log_max_size | 134217728 |
+----------------------------------+-----------+

如果用户更新的表比较大，并且在创建过程中有大量的写事务，超出了128MB后，会抛出错误。可以根据需要适当的调整参数innodb_online_alter_log_max_size

需要注意的是，由于Online DDL在创建索引完成后再通过重做日志达到数据库的最终一致性，这意味着在创建索引过程中，SQL优化器不会选择正在创建中的索引。

5 Cardinality值

5.1 什么是Cardinality

并不是在所有的查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引，一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段、类型字段，取值范围很小，称为低选择性这时添加B+树是没有必要的。相反，如果某个字段取值范围很广，几乎没有重复，即属于高选择性。

Cardinality是指一个索引中不同值的数量，越大表示该索引在数据表中能够识别唯一行。在某些情况下，一个高cardinality的索引可以提高查询性能，例如在一个数据表中有一个唯一用户ID的列，那么对该列添加索引可以提高查询性能。但是在其他情况下，一个高Cardinality的索引会导致查询性能下降，例如在一个数据表中存储的列(只有男、女)，对该列添加索引并不会提高查询性能。

因此在决定是否要对一个列建立索引时，需要综合考虑该列的cardinality、查询频率、数据表大小等因素。

5.2 InnoDB存储引擎的Cardinality统计

因为MySQL数据库有各种不同的存储引擎，而每种存储引擎对于B+树索引的实现又各不相同，所以对Cardinality的统计是放在存储引擎层进行的。

此外，在生产环境中，索引的更新操作是非常频繁的。如果每次索引在发生操作时就对其进行Cardinality的统计，那么将会给数据库带来很大的负担。另外需要考虑的是，如果一张表的数据非常大，如一张表有50G的数据，那么统计一次Cardinality信息所需要的时间非常长。在生产环境中，这种肯定是不能被接受的。因此，数据库对于Cardinality的统计都是通过采样的方法完成的。

一般情况下只要insert和update操作发生时，就会触发Cardinality更新，但是当表数据量大的时候，对数据库是有影响的。所以，Innodb存储引擎内部对更新Cardinality信息的策略为：

• 表中1/16的数据已经发生变化
• stat_modifed_counter>2 000 000 000

6 B+树索引的使用

6.1 不同应用中B+树索引的使用

在OLTP中，B+树索引建立后，对该索引的使用应该只是通过该索引取得表中少部分的数据。这时建立B+树索引才是有意义的，否则即使建立了，优化器也可能不选择使用索引。

在OLAP中，如果是复杂的查询，要涉及多张表之间的连接操作，因此添加索引是有意义的。但是如果连接使用的hash join，那么索引可能又变的不那么重要了。不过在OLAP中，通常会需要对时间字段进行索引，这是因为大多数统计需要根据时间维度来进行数据的筛选。

6.2 联合索引

联合索引是指对表上的多个列进行索引。联合索引的创建方法和单个索引的创建方法一样，不同之处仅在于有多个索引列。

比如：对创建索引index_a_b (a,b),那么在查询的时候select * from table where a=xx and b=xx是可以使用(a,b)这个索引的。对于单列的查询select * from table where a=xxx也可以使用这个(a,b)索引。但是select * from table where b=xxx是用不到联合索引的。

联合索引的另一个好处就是已经对第二个键值进行了排序处理。例如：使用(userid,sys_date)联合索引，在查询userid并且要求有序的时候，就会默认使用(userid,sys_date)索引。

1）创建索引

mysql> create table index_test(
    -> userid int unsigned not null,
    -> sys_date date,
    -> key key_u (userid),
    -> key key_u_s (userid,sys_date)
    -> )engine=innodb;
Query OK, 0 rows affected (0.03 sec)

2）插入数据

mysql> insert into index_test values(1,'2020-01-01');
mysql> insert into index_test values(2,'2022-01-01');
mysql> insert into index_test values(3,'2022-05-01');
mysql> insert into index_test values(4,'2021-05-01');

3）查询userid，不要求排序

只查询userid的时候，可以看到在possible_keys中可以有两个索引提供使用，分别是单个userid索引的ley_u和(user_id,sys_date)的联合索引key_u_s。但是最终优化器选择是userid，因为该索引的叶子节点包含单个键值，所以理论上一个页能存放的记录应该更多。

mysql> explain select * from index_test where userid = 2\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: index_test
   partitions: NULL
         type: ref
possible_keys: key_u,key_u_s
          key: key_u
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 row in set, 1 warning (0.00 sec)

4）查询userid，要求排序

当查询userid，并要求排序的时候，possible_keys既可以使用key_u索引，也可以使用key_u_s索引。但是优化器选择了ley_u_s索引，因为这个联合索引中sys_date字段已经排序好了。只需要根据联合索引取出数据，无须再对sys_date做一次额外的排序操作。

mysql> explain select * from index_test where userid = 2 order by sys_date desc limit 3\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: index_test
   partitions: NULL
         type: ref
possible_keys: key_u,key_u_s
          key: key_u_s
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: Using where; Using index
1 row in set, 1 warning (0.00 sec)

5）查询userid，要求排序，并强制使用key_u索引

如果是强制使用key_u索引，可以在Extra中看到有using filesort，即需要额外一次排序才能完成查询，而这次显然需要对列sys_date排序。

mysql> explain select * from index_test force index(key_u) where userid = 2 order by sys_date desc limit 3\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: index_test
   partitions: NULL
         type: ref
possible_keys: key_u
          key: key_u
      key_len: 4
          ref: const
         rows: 1
     filtered: 100.00
        Extra: Using index condition; Using filesort
1 row in set, 1 warning (0.00 sec)

6.3 覆盖索引

InnoDB存储引擎支持覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

例如：当一个表里有聚集索引和辅助索引时，在count数据的时候，innodb会自动优化使用辅助索引，而不是使用聚集索引。

6.4 优化器选择不适应索引的情况

在某些情况下，当执行explain命令进行SQL语句分析时，会发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是直接进行全表扫描来得到数据。这种情况多发生于范围查找、join连接等情况下。

6.5 索引提示

MySQL数据库支持索引提示(index hint)，显式的告诉优化器使用哪个索引。大概两种情况下需要用到索引提示：

• MySQL数据库的优化器错误的选择了某个索引，导致SQL语句运行很慢。对于目前的SQL版本，可能很少会遇见这种问题。如果存在的话，可以强制优化器使用某个索引，以此来提高运行的速度。
• 某SQL语句可以选择的索引非常多，这时优化器选择执行时间的开销可能会大于SQL语句本身。例如，优化器分析range查询本身就是比较耗时的操作。这时可以通过Index Hint来强制优化器不进行各个执行路径的成本分析，直接指定索引完成查询。

使用force index来指定索引是可行的。

6.6 Multi-Range Read优化

MySQL5.6开始支持Multi-Range Read(MRR)优化。其目的就是减少磁盘的随机访问，并且随机访问转化为较为顺序的数据访问，这时对于IO-bound类型的SQL查询可以带来性能极大的提示。Multi-Range Read优化可适用于range，ref，eq_ref类型的查询。

MRR优化的好处：

• MRR使数据访问变得较为顺序。在查询辅助索引时，首先恩据得到得查询结果，按照主键进行排序，并按照主键顺序进行书签查找。
• 减少缓冲池中页被替换的次数
• 批量处理对键值的查询操作

对于InnoDB和MyISAM存储引擎的范围查询和JOIN查询操作，MRR的工作方式如下：

• 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。
• 将缓存中的键值根据RowID进行排序
• 根据RowID的排序顺序来访问实际的数据文件。

此外，若InooDB存储引擎或者MyISAM存储引擎的缓冲池不是足够大，即不能存放下一张表中所有的数据，此时频繁的离散读操作还会导致缓存中的页被替换出缓冲池，然后又不断的被读入缓冲池。若是按照主键顺序进行访问，则可以将此重复行为降为最低。

是否启用Multi-Range Read优化可以通过参数optimizer_switch中的标记来控制。当mrr=on时，表示启用multi-range read优化。mrr_cost_based标记表示是否通过cost based的方式来选择是否启用mrr。

若mrr设为on，mrr_cost_based设为off，则总是启用multi-range read优化。例如可通过如下指令设置multi-range read优化总是处于开启状态：

mysql> set @@optimizer_switch='mrr=on,mrr_cost_based=off';

参数read_rnd_buffer_size用来控制键值的缓冲区大小，当大于该值时，则执行器对已经缓冲的数据根据RowID进行排序，并通过RowID来取得行数据。该值默认为256K。

mysql> select @@read_rnd_buffer_size\G;
*************************** 1. row ***************************
@@read_rnd_buffer_size: 262144
1 row in set (0.00 sec)

6.7 Index Condition Pushdown (ICP)优化

和Multi-Range Read一样，Index COndition Pushdown也是MySQL5.6开始支持的查询优化的方式。之前在进行索引查询的时候，首先根据索引来查找记录，然后根据where条件来过滤记录。在支持Index Condition Pushdown后，MySQL数据库会在去除索引的同时，判断是否可以进行where条件的过滤，也就是将where的部分过滤操作放在存储引擎层。在某些查询下，可以大大减少上层SQL对记录的索取(fetch)，从而提高数据库的整体性能。

Index Condition Pushdown优化支持range、ref、eq_ref、ref_or_null类型的查询，当前支持MyISAM和InnoDB存储引擎。当优化器选择Index Condition Pushdow优化时，可在执行记录的列Extra看到Using index condition的提示。

7 哈希算法

哈希算法是一种常见算法，时间复杂度为O(1)，且不只存在于索引中，每个数据库应用都存在该数据结构。设想一个问题，当前服务器内存为128GB时，用户怎么从内存中得到某一个被缓存的页呢？虽然内存查询速度很快，但是也不可能每次都要遍历所有内存来进行查找，这时对于字典操作只需O(1)的哈希算法就有了用武之地。

7.1 哈希表

哈希表也称散列表，由直接寻址表改进而来。在哈希方式下，该元素处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。哈希函数h必须可以很好的进行散列。最好的情况是能避免碰撞的发生。即使不能避免，也应该使碰撞在最小程度下产生。一般来说，都将关键字换成自然数，然后通过触发散列、乘法散列或全域散列来实现。数据库中一般采用除法散列的方法。

在哈希函数的除法散列法中，通过取k除以m的余数，将关键字k映射到m个槽的某一个去，即哈希函数为：

h(k) = k mod m

7.2 InnoDB存储引擎中的哈希算法

InnoDB存储引擎使用哈希算法来对字典进行查找，其冲突机制采用链表方式，哈希函数采用散列方式。对于缓冲池页的哈希表来说，在缓冲池中的Page页都有一个chain指针，它指向相同哈希函数值的页。而对于除法散列，m的取值为略大于2倍的缓冲池页数量的质数。例如：当前参数innodb_buffer_pool_size的大小为10M，则共有640个16KB的页。对于缓冲池页内存的哈希表来说，需要分配640*2=1280个槽，但是由于1280不是质数，需要取比1280略大的一个质数，应是1399，所以在启动时会分配1399个槽的哈希表，用来哈希查询所在缓冲池中的页。

那么InnoDB存储引擎的缓冲池对于其中的页是怎么进行查找的呢？上面只是给出一般算法，怎么将要查找的页转换成自然数呢？

其实页很简单，InnoDB存储引擎的表空间都有一个space_id，用户所需要查询的应该是某表空间的某个连续16KB的页，即偏移量offset。InnoDB存储引擎将space_id左移20位，然后加上这个space_id和offset，即关键字

K = space_id << 20 + space_id + offset,然后通过除法散列到各个槽中。

7.3 自适应哈希索引

自适应哈希索引采用之前讨论的哈希表的方式实现。不同的是，这仅是数据库自身创建并使用的，DBA本身不能对其干预。自适应哈希索引哈希函数映射到一个哈希表中，因此对于字典类型的查找非常快速，如select * from table where a = xx;。但是对于范围查询不太友好。

由于自适应哈希索引是由InnoDB存储引擎自己控制的，因此这里的这些信息只供参考。不过可以通过参数innodb_adaptive_hash_index来禁用或启动此特性，默认为开启。

mysql> show variables like 'innodb_adaptive_hash_index';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON    |
+----------------------------+-------+
1 row in set (0.00 sec)

8 全文检索

8.1 概述

对于B+树的特点，可以通过索引字段的前缀进行查找。例如如下的查询方式是支持B+树索引的,只要name字段添加了B+树索引，就可以利用索引快速查找以XXX开头的名称。

select * from table where name like 'XXX%';

而如下这种情况不适合私有B+索引，因为即使添加了B+树索引也是需要进行全文扫描。

select * from table where name like '%XXX%';

但是在实际中会遇到很多这样的场景，例如搜索引擎根据用户输入的关键词进行全文检索，这种都不适合使用B+索引。那就需要引出另一个检索方式，叫全文检索。

全文检索是将存储于数据库中的整本书或整篇文章中的任意内容查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。

最开始InnoDB引擎不支持全文检索技术。需要使用全文检索的表，需要使用MyISAM引擎，但是这却丧失了InnoDB存储引擎的事务性。所以在InnoDB 1.2.x版本开始，InnoDB开始支持全文检索。

8.2 倒排索引

全文检索通常使用倒排索引(inverted index)来实现。倒排索引同B+树一样，也是一种索引结构。它在辅助表(auxiliary table)中存储了单词与单词自身在一个或多个文档所在位置之间的映射。通常利用关联数组实现，拥有两种表示形式：

• inverted file index,其表现形式为{单词，单词所在文档的ID}
• full inverted index,其表现形式为{单词，(单词所在文档ID，在具体文档中的位置)}

例如：下面的例子，表中存储的内容如下：

Documentld表示全文检索文档的ID，text表示存储的内容，用户需要对存储的这些文档内容进行全文检索。

对于inverted file index的关键数组，其存储的内容容下：

可以看到单词code存在于1和4中，这样就可以根据1、4来查找对应的存储内容。对于inverted file index，其仅存取文档ID，而full inverted index存储的是对(pair)，即(documentid,position)，因此其存储的倒排索引表如下：

full inverted index还存储了单词所在的位置信息，如code这个单词出现在(1:6)，即文档1的第6个单词为code。相比之下，full inverted index占用更多的空间，但是能更好的定位数据。

8.3 InnoDB全文检索

InnoDB存储引擎从1.2.x版本开始支持全文检索的技术，其采用full inverted index的方式。在InnoDB存储引擎中，将(DocumentId,Position)视为一个"ilist"。因此在全文检索的表中，有两个列，一个是word字段，一个是ilist字段，并且在word字段上设有索引。此外，由于InnoDB存储引擎在ilist字段中存放了Position信息，故可以进行Proximty Search，而MyISAM存储引擎不支持该特性。

正如之前所说，倒排索引需要将word存放到一张表中，这个表称为Auxiliary table(辅助表)。在InnoDB存储引擎中，为了提高全文检索的并行性能，共有6张Auxiliary table，目前每张表根据word的latin编码进行分区。

Auxiliary Table是持久的表，存放于磁盘上。然而在InnoDB存储引擎的全文索引中，还有另外一个重要的概念FTS Index Cache（全文检索索引缓存），其用来提高全文检索的性能。

FTS Index Cache是一个红黑树，其根据（word,ilist）进行排序。这意味着插入的数据已经更新了对应的表，但是对全文索引的更新可能在分词操作后还在FTS Index Cache中，Auxiliary Table可能还没有更新。InnoDB存储引擎会批量对Auxiliary Table进行更新，而不是每次插入都要更新一次Auxiliary Table。当对全文索引进行查询时，Auxiliary Table首先会将FTS Index Cache中对应的word字段合并到Auxiliary Table中，然后再进行查询。这种merge操作非常类似于之前介绍的Insert Buffer的功能，不同的是Insert Buffer是一个持久的对象，并且其是B+树的结构。然而FTS Index Cache的作用又和Insert Buffer是类似的，它提高了InnoDB存储引擎的性能，并且由于其根据红黑树排序后进行批量插入，其产生的Auxiliary Table相对较小。