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

        一些开发人员总是在事后才想起添加索引——我一直认为， 这源于一种错误的开发模式。 如果知道数据的使用， 从一开始就应该在需要处添加索引。 开发人员往往对于数据库的使用停留在应用的层面， 比如编写 SQL 语句、 存储过程之类， 他们甚至可能不知道索引的存在， 或者认为事后让相关OBA加上即可。 OBA往往不够了解业务的数据流，而添加索引需要通过监控大量的 SQL 语句进而从中找到问题， 这个步骤所需的时间肯定是远大于初始添加索引所需要的时间， 并且可能会遗漏一部分的索引。 当然索引也并不是越多越好。

5.1 lnnoDB 存储引擎索引概述

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

1.B+树索引

2.全文索引

3.哈希索引

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

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

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

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

5.2 数据结构与算法

            B+ 树索引是最为常见，也是在数据库中使用最为频繁的一种索引。在介绍该索引之前先介绍与之密切相关的一些算法与数据结构，这有助于读者更好的理解B+ 树索引的工作方式。

5.2.1 二分查找法

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

5.3 B+树

        前面讨论的都是B+树的数据结构及其一般操作，B+树索引的本质就是B+树在数据库中的实现。但是B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2-4 层，这也就是说查找某一键值的行记录时最多只需要2-4次IO, 这倒不错。因为当前一般的机械磁盘每秒至少可以做100 次IO, 2 ~4 次的IO 意味着查询时间只需0.02~0.04 秒。

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

5.4.1 聚集索引

        之前已经介绍过了， InnoDB 存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引(clustered index) 就是按照每张表的主键构造一棵B+ 树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。

        由于实际的数据页只能按照一棵B+ 树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+ 树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

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

        聚集索引的另一个好处是，它对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。如用户需要查询一张注册用户的表，查询最后注册的10 位用户，由于B+树索引是双向链表的，用户可以快速找到最后一个数据页，并取出10条记录

5.4.2 辅助索引

        对于辅助索引(Secondary Index, 也称非聚集索引）， 叶子节点并不包含行记录的全部数据。 叶子节点除了包含键值以外， 每个叶子节点中的索引行中还包含了 个书签(bookmark)。 该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。 由于InnoDB存储引擎表是索引组织表， 因此lnnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。 图5-15显示了InnoDB存储引擎中辅助索引与聚集索引的关系。

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

        当然，在一些情况下，使用堆表的确会比索引组织表更快，但是我觉得大部分原因是由于存在 OLAP(On-Line Analy tical Processing, 在线分析处理）的应用。其次就是前面提到的，表中数据是否需要更新，并且更新是否影响到物理地址的变更。此外另一个不能忽视的是对于排序和范围查找，索引组织表通过B+树的中间节点就可以找到要查找的所有页，然后进行读取，而堆表的特性决定了这对其是不能实现的。最后，非聚集索引的离散读，的确存在上述的情况，但是一般的数据库都通过实现预读(read ahead) 技术来避免多次的离散读操作。因此，具体是建堆表还是索引组织表，这取决于应用， 不存在哪个更优的问题。这和InnoDB存储引擎好还是MyISAM存储引擎好这个问题的答案是一样的，It all depends。

5.4.3 B+ 树索引的分裂

        在5.3节中介绍 B+树的分裂是最为简单的一种情况， 这和数据库中 B+ 树索引的情况可能略有不同。 此外5.3节页没有涉及并发， 而这才是 B+ 树索引实现最为困难的部分。

        B+ 树索引页的分裂并不总是从页的中间记录开始， 这样可能会导致页空间的浪费。例如下面的记录：1、 2 、 3、 4 、 5 、 6、 7 、 8、 9

        插入是根据自增顺序进行的， 若这时插人10这条记录后需要进行页的分裂操作， 那么根据5.3.1节介绍的分裂方法， 会将记录5作为分裂点记录(split record), 分裂后得到下面两个页：Pl: 1、 2 、 3、 4

P2: 5、6、7、8、9、 10

        然而由千插入是顺序的，Pl这个页中将不会再有记录被插人， 从而导致空间的浪费。 而P2又会再次进行分裂。

        InnoDB存储引擎的Page Header中有以下几个部分用来保存插入的顺序信息：

PAGE_LAST_INSERT

PAGE_DIRECTION

PAGE_N_DIRECTION

        通过这些信息， InnoDB 存储引擎可以决定是向左还是向右进行分裂， 同时决定将分裂点记录为哪一个。 若插入是随机的， 则取页的中间记录作为分裂点的记录， 这和之前介绍的相同。 若往同一方向进行插入的记录数量为5, 并且目前已经定位(cursor)到的记录 (InnoDB 存储引擎插入时， 首先需要进行定位， 定位到的记录为待插入记录的前一条记录）之后还有3条记录， 则分裂点的记录为定位到的记录后的第三条记录， 否则分裂点记录就是待插人的记录。

5.4.4 B+树索引的管理

1. 索引管理

        索引的创建和删除可以通过两种方法， 一种是ALTER TABLE, 另一种是CREATE/DROP INDEX。

        用户可以设置对整个列的数据进行索引， 也可以只索引一个列的开头部分数据.若用户想要查看表中索引的信息，可以使用命令SHOW INDEX。

        通过命令SHOWINDEX FROM可以观察到表t上有4个索引，分别为主键索引、c列上的辅助索引、b列的前100字节构成的辅助索引，以及(a、c)的联合辅助索引。接着具体阐述命令SHOWINDEX展现结果中每列的含义。

Table: 索引所在的表名。

Non_unique: 非唯一的索引，可以看到primary key是 o, 因为必须是唯一的。

 Key_name: 索引的名字，用户可以通过这个 名字来执行 DROP INDEX。

Seq_in_index: 索引中该 列的位置，如果看联合索引idx_a_c就比较直观了。 0 Column_name: 索引列的名称。

Collation : 列以什么方式存储在索引中。可以是A或NULL。B+树索引总是A,即排序的。如果使用了Heap 存储引擎，并且建立了Hash索引，这里就会显示NULL了。因为Hash根据Hash桶存放索引数据，而不是对数据进行排序。

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

 Sub_part : 是否是列的部分被索引。如果看idx_b这个索引，这里显示100, 表示只对b列的前100字符进行索引。如果索引整个列，则该 字段为NULL。

 Packed: 关键字如何被压缩。如果没有被压缩，则为NULL。

Null: 是否索引的列含有NULL值。可以看到idx_b这里为Yes, 因为定义的列b允许NULL值。

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

Comment: 注释。

        Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新 的，即并非每次索引的更新都会 更新该值，因为这样代价太大了。因此这个值是不太准确的只是一个大概的值。上面显示的结果主键的Cardinality为2, 但是很显然我们的表中有4条记录，这个值应该 是4。如果需要更新索引Cardinality 的信息，可以使用ANALYZE TABLE命令。

2. Fast Index Creation

       lnnoDB存储引擎从InnoDB 1.0.x版本开始支持一种称为FastIndex Creation (快速索引创建）的索引创建方式——简称FIC。

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

        这里需要特别注意的是， 临时表的创建路径是通过参数tmpdir 进行设置的。用户必须保证tmpdir有足够的空间可以存放临时表，否则会导致创建索引失败。

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

3. Online Schema Change

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

        Facebook采用PHP脚本来现实OSC, 而并不是通过修改InnoDB存储引擎源码的方式。osc 最初由Facebook 的员工VamsiPonnekanti开发。此外， osc 借鉴了开源社区之前的工具The openarkkit toolkit oak-online-alter-table。实现osc 步骤如下：

init, 即初始化阶段，会对创建的表做一些验证工作， 如检查表是否有主键， 是否存在触发器或者外键等。

 createCopyTable, 创建和原始表结构一样的新表。

 alterCopyTable: 对创建的新表进行ALTER TABLE 操作， 如添加索引或列等。

 createDeltasTable, 创建deltas表， 该表的作用是为下一步创建的触发器所使用。之后对原表的所有DML操作会被记录到createDeltasTable 中。

create Triggers, 对原表创建INSERT、UPDATE、DELETE 操作的触发器。触发操作产生的记录被写入到deltas表。

startSnpshotXact, 开始osc 操作的事务。

selectTablelntoOutfile, 将原表中的数据写人到新表。为了减少对原表的锁定时间， 这里通过分片(chunked)将数据输出到多个外部文件， 然后将外部文件的数据导人到copy表中。分片的大小可以指定， 默认值是500 000。

 dropNCindexs, 在导人到新表前， 删除新表中所有的辅助索引。

loadCopyTable, 将导出的分片文件导入到新表。

replayChanges, 将osc 过程中原表DML操作的记录应用到新表中， 这些记录被保存在deltas表中。

recreateNCindexes, 重新创建辅助索引。

replayChanges, 再次进行DML日志的回放操作， 这些日志是在上述创建辅助索引中过程中新产生的日志。

swapTables, 将原表和新表交换名字， 整个操作需要锁定2张表， 不允许新的数据产生。由于改名是一个很快的操作， 因此阻塞的时间非常短。

        上述只是简单介绍了osc 的实现过程， 实际脚本非常复杂， 仅osc 的PHP核心代码就有22 00 多行， 用到的MySQLInnoDB 的知识点非常多， 建议OBA 和数据库开发人员尝试进行阅读， 这有助于更好地理解InnoDB存储引擎的使用。

        由于osc 只是一个PHP脚本， 因此其有一定的局限性。例如其要求进行修改的表一定要有主键， 且表本身不能存在外键和触发器。此外， 在进行osc 过程中， 允许SETsql_b in_l og=O, 因此所做的操作不会同步slave服务器，可能 导致主从不一致的情况。

4. Online DDL

        虽然FIC可以让InnoDB存储引擎避免创建临时表， 从而提高索引创建的效率。但正如前面小节所说的， 索引创建时会阻塞表上的DML操作。osc 虽然解决了上述的部分问题， 但是还是有很大的局限性。MySQL5.6版本开始支持Online DDL (在线数据定义）操作，其允许辅助索引创建的同时，还允许其他诸如INSERT、UPDATE、DELETE这类DML操作，这极大地提高了MySQL数据库在生产环境中的可用性。

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

辅助索引的创建与删除

改变自增长值

添加或删除外键约束

列的重命名

过新的 ALTER TABLE语法，用户可以选择索引的创建方式：

        ALGORITHM指定了创建或删除索引的算法，COPY表示按照MySQL5.l版本之前的工作模式， 即创建临时表的方式。INPLACE表示索引创建或删除操作不需要创建临时表。DEFAULT表示根据参数old_alter_ table来判断是通过INPLACE还是COPY的算法，该参数的默认值为OFF, 表示采用INPLACE的方式

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

(I) NONE

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

(2) SHARE

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

(3) EXCLUSIVE

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

(4) DEFAULT

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

        InnoDB存储引擎实现OnlineDDL的原理是在执行创建或者删除操作的同时，将 INSER T、 UPDATE、DELE TE这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此 达到数据的 一致性。这个缓存的大小由参数innodb_ online _alter_ log_ max_ size控制，默认的大小 为128MB 。

5.5 Cardinality值

5.5.1 什么是Cardinality

        并不是在所有的查询条件中出现的列都需要添加索引。对于什么时候添加B+树索引， 一般的经验是，在访问表中很少一部分时使用B+树索引才有意义。对于性别字段，地区字段、类型字段，它们可取值的范围很小，称为低选择性。

        按性别进行查询时，可取值的范围一般只有'M'、'F'。因此上述SQL语句得到的结果可能是该表50%的数据（假设男女比例1 : 1), 这时添加B+树索引是完全没有必要的。相反，如果某个字段的取值范围很广，几乎没有重复，即属于高选择性，则此时使用B+树索引是最适合的。例如，对于姓名字段，基本上在一个应用中不允许重名的出现。

        怎样查看索引是否是高选择性的呢？可以通过SHOW INDEX结果中的列Cardinality来观察。Cardinality值非常关键，表示索引中不重复记录数扭的预估值。同时需要注意的是Cardinality是一个预估值，而不是一个准确值，基本上用户也不可能得到一个准确的值。在实际应用中，CardinalityIn_ row s_ in_ table应尽可能地接近1。如果非常小，那么用户需要考虑是否还有必要创建这个索引。故在访问高选择性属性的字段并从表中取出很少一部分数据时，对这个字段添加B+树索引是非常有必要的。

5.5.2 lnnoDB存储引擎的Cardinality统计

        因为MySQL数据库中有各种不同的存储引擎， 而每种存储引擎对于B+树索引的实现又各不相同， 所以对Cardinality的统计是放在存储 引擎层进行的。数据库对于 Cardinality的统计都是通过采样(Sample)的方法来完成的。

InnoDB存储引擎内部对更新Cardinality信息的策略为：

表中 1/16 的数据已发生过变化。

stat_modified_counter>2 000 000 000。

        第一种策略为自从上次统计Cardinality信息后， 表中 1/16 的数据已经发生过变化，这时需要更新Cardinality信息。 第二种情况考虑的是， 如果对表中某一行数据频繁地进行更新操作， 这时表中的数据实际并没有增加， 实际发生变化的还是这一行数据， 则第一种更新策略就无法适用这这种情况。 故在InnoDB存储引擎内部有一个计数器stat_ modified_ counter, 用来表示发生变化的次数， 当stat_modified_ counter大于2 000 000 000 时， 则同样需要更新Cardinality信息。

        接着考虑InnoDB存储引擎内部是怎样来进行Cardinality信息的统计和更新操作的 呢？同样是通过采样的方法。 默认InnoDB存储引擎对8个叶子节点(Leaf Page)进行采用。 采样的过程如下：

取得B+树索引中叶子节点的数量， 记为A。

随机取得B+树索引中的8个叶子节点。 统计每个页不同记录的个数， 即为P1,P2, …，P8。

根据采样信息给出Cardinality的预估值：Cardinality= (Pl+ P2+…+P8) *A/8。

        通过上述的说明可以发现，在InnoDB存储引擎中，Cardinality值是通过对8个叶子节点预估而得的，不是一个实际精确的值。再者，每次对Cardinality值的统计，都是通过随机取8个叶子节点得到的，这同时又暗示了另一个Cardinality现象，即每次得到的Cardinality值可能是不同的。

5.6 B+树索引的使用

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

     根据第1章的介绍，用户已经知道数据库中存在两种类型的应用，OLTP和OLAP 应用。在OLTP应用中，查询操作只从数据库中取得一小部分数据，一般可能都在10条  记录以下，甚至在很多时候只取1条记录，如根据主键值来取得用户信息，根据订单号取得订单的详细信息，这都是典型OLTP应用的查询语句。在这种情况下，B+树索引建立后，对该索引的使用应该只是通过该索引取得表中少部分的数据。这时建立索引才有意义。否则优化器可能选择不执行索引。        对于OLAP应用，情况可能就稍显复杂了。不过概括来说，在OLAP应用中，都需要访问表中大批的数据，根据这些数据来产生查询的结果，这些查询多是面向分析的查询，目的是为决策者提供支持。如这个月每个用户的消费情况，销售额同比、环比增长 的情况。因此在OLAP中索引的添加根据的应该是宏观的信息，而不是微观，因为最终要得到的结果是提供给决策者的。例如不需要在OLAP中对姓名字段进行索引，因为很 少需要对单个用户进行查询。但是对于OLAP中的复杂查询，要涉及多张表之间的联接操作，因此索引的添加依然是有意义的。但是，如果联接操作使用的是HashJoin, 那么 索引可能又变得不是非常重要了，所以这需要OBA或开发人员认真并仔细地研究自己 的应用。不过在OLAP应用中，通常需要根据时间维度来进行数据的筛选。

5.6.2 联合索引

        联合索引是指对表上的多个列进行索引。前面讨论的情况都是只对表上的一个列进行索引。联合索引的创建方法与单个索引创建的方法一样，不同之处仅在于有多个索引列。

        从本质上来说，联合索引也是一棵I I LI I _I I B+树，不同的是联合索引的键值的数量不是1,而是大于等于2。接着来讨论两个整型列组成的联合索引，假定两个键值的名称分别为a、b,如图5-22所示。

        联合索引的第二个好处是已经对第二个键值进行了排序处理。例如，在很多情况下 应用程序都需要查询某个用户的购物情况，并按照时间进行排序，最后取出最近三次的购买记录，这时使用联合索引可以避免多一次的排序操作，因为索引本身在叶子节点已 经排序了。

5.6.3 覆盖索引

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

        对于 InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此其叶子节点存放的数据为(primary key I , primary key2, …, keyl, key2, …）。

5.6.4 优化器选择不使用索引的情况

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

5.6.5 索引提示

        MySQL数据库支持索引提示(INDEXHINT), 显式地告诉优化器使用哪个索引。个人总结以下两种情况可能需要用到INDEXHINT:

        MySQL数据库的优化器错误地选择了某个索引， 导致SQL语句运行的很慢。这种情况在最新的MySQL数据库版本中非常非常的少见。优化器在绝大部分情况下工作得都非常有效和正确。这时有经验的OBA或开发人员可以强制优化器使用某个索引， 以此来提高SQL运行的速度。

        某SQL语句可以选择的索引非常多， 这时优化器选择执行计划时间的开销可能会大于SQL语句本身。例如， 优化器分析Range查询本身就是比较耗时的操作。这时DBA或开发人员分析最优的索引选择， 通过Index Hint来强制使优化器不进行各个执行路径的成本分析， 直接选择指定的索引来完成查询。

5.6.6 Multi-Range Read优化

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

 MRR优化有以下几个好处：

1 MRR使数据访问变得较为顺序。 在查询辅助索引时， 首先根据得到的查询结果 ，按照主键进行排序， 并按照主键排序的顺序进行书签查找。

2 减少缓冲池中页被替换的次数。

3 批量处理对键值的查询操作 。

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

1 将查询得到的 辅助索引键值存放于一个缓存中， 这时缓存中的数据是根据辅助索引键值排序的。

2 将缓存中的键值根据RowID进行排序。

3 根据RowID的排序顺序来访问实际的数据文件。

5.6.7 Index Condition Pushdown CICP)优化

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

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

5.7 哈希算法

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

5.7.1  哈希表

        哈希表(HashTable)也称散列表， 由直接寻址表改进而来。 我们先来看直接寻址 表。 当关键字的全域U比较小时， 直接寻址是一种简单而有效的技术。 假设某应用要用到 个动态集合， 其中每个元素都有一个取自全域U={0, 1, …，m-1}关键字。 同时假设没有两个元素具有相同的关键字。

        直接寻址技术存在一个很明显的问题， 如果域U很大， 在一台典型计算机的可用容量的限制下， 要在机器中存储大小为U的一张表T就有点不实际， 甚至是不可能的。 如果实际要存储的关键字集合K相对于U来说很小， 那么分配给T的大部分空间都要浪费掉。

        因此， 哈希表出现了。 在哈希方式下， 该元素处于h(k) 中， 即利用哈希函数h,根据关键字k计算出槽的位置。 函数h将关键字域U映射到哈希表T [O .. m-1]的槽位上， 如图5-39所示。

        哈希表技术很好地解决了直接寻址遇到的问题， 但是这样做有一个小问题， 如图5-39所示的两个关键字可能映射到同一个槽上。 般将这种情况称之为发生了碰撞(collision)。 在数据库中一般采用最简单的碰撞解决技术， 这种技术被称为链接法(chaining)。

       在链接法中， 把散列到同一槽中的所有元素都放在一个链表中， 如图5-40所示。 槽j中有一个指针， 它指向由所有散列到j的元素构成的链表的头；如果不存在这样的元素，则j中为NULL。

        最后要考虑的是哈希函数。 哈希函数h必须可以很好地进行散列。 最好的情况是能避免碰撞的发生。 即使不能避免， 也应该使碰撞在最小程度下产生。 一般来说， 都将关键字转换成自然数， 然后通过除法散列、 乘法散列或全域散列来实现。 数据库中一般采用除法散列的方法。

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

5. 7 .2 lnnoDB 存储引擎中的哈希算法

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

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

        其实也很简单，InnoDB存储引擎的表空间都有一个space_id, 用户所要查询的应该是某个表空间的某个连续16KB的页， 即偏移量offset。lnnoDB存储引擎将space_id左移20位， 然后加上这个space_id和offset, 即关键字K=space_ id<<20+space id+offset,然后通过除法散列到各个槽中去。

5.7.3 自适应哈希索引

        自适应哈希索引采用之前讨论的哈希表的方式实现。不同的是， 这仅是数据库自身创建并使用的， DBA本身并不能对其进行干预。自适应哈希索引经哈希函数映射到一个哈希表中， 因此对于字典类型的查找非常快速，如SELECT * FROM TABLE WHERE index_col='xxx'。但是对于范围查找就无能为力了。。通过命令SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况。

        现在可以看到自适应哈希索引的使用信息了，包括自适应哈希索引的大小，使用情况、每秒使用自适应哈希索引搜索的情况。需要注意的是，哈希索引只能用来搜索等值的查询。

        而对于其他查找类型，如范围查找，是不能使用哈希索引的。因此，这里出现了non-hash searches/s的情况。通过hashsearches:non-hash searches可以大概了解使用哈希索引后的效率。

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

5.8 全文检索

5.8.1 概述

        通过前面章节的介绍，已经知道B+树索引的特点，可以通过索引字段的前缀(prefix)进行查找。例如，对于下面的查询B+树索引是支持的：SELECT* FROM blog WHERE content like'xxx%＇

        上述SQL语句可以查询博客内容以XXX开头的文章，并且只要content添加了B+ 树索引，就能利用索引进行快速查询。然而实际这种查询不符合用户的要求，因为在更多的情况下，用户需要查询的是博客内容包含单词xxx的文章，即：SELECT* FROM blog WHERE content like'%xxx%'

        根据B+树索引的特性，上述SQL语句即便添加了B+树索引也是需要进行索引的扫描来得到结果。类似这样的需求在互联网应用中还有很多。例如，搜索引擎需要根据用户输入的关键字进行全文查找，电子商务网站需要根据用户的查询条件，在可能需要在商品的详细介绍中进行查找，这些都不是B+树索引所能很好地完成的工作。

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

        在之前的MySQL数据库中，InnoDB存储引擎并不支持全文检索技术。大多数的用户转向MyISAM存储引擎，这可能需要进行表的拆分，并将需要进行全文检索的数据存储为 MyISAM 表。这样的确能够解决逻辑业务的需求，但是却丧失了 InnoDB 存储引擎的事务性，而这在生产环境应用中同样是非常关键的。

        从 InnoDB 1.2.x 版本开始，InnoDB 存储引擎开始支持全文检索，其支持 MyISAM存储引擎的全部功能，并且还支持其他的一些特性，这些将在后面的小节中进行介绍。

5.8.2 倒排索引

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

inverted file index, 其表现形式为｛单词，单词所在文档的 ID}

 full inverted index, 其表现形式为｛单词，（单词所在文档的ID, 在具体文档中的位置）｝

5.8.3 InnoDB全文检索

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

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

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

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

        InnoDB存储引擎允许用户查看指定倒排索引的Auxiliary Table中分词的信息， 可以通过设置参数innodb_ft_aux_table来观察倒排索引的Auxiliary Table。

        当数据库关闭时，在FTSIndex Cache中的数据库会同步到磁盘上的Auxiliary Table中。然而 ，如果当数据库 发生右机时， 些FTSIndex Cache中的数据库 可能未被同步到磁盘上。那么下次重启数据库 时，当用户对表进行全文检索（查询或者插入操作）时，

        lnnoDB存储引擎会自动读取未完成的文档，然后进行分词操作， 再将分词的结果放入到FTS Index Cache中。

        参数innodb_ft_ cache_ size 用来控制FTSIndex Cache的大小 ，默认值为32M。当该缓存满时，会将其中的(word, ilist)分词信息同步到磁盘的Auxiliary Table中。增大该参数可以提高全文检索的性能，但是在者机时，未同步到磁盘中的索引信息可能需要更长的时间进行恢复。

        FTS Document ID是另外一个重要的概念。在lnnoDB存储引擎中，为了支持全文检索，必须有一个列与word进行映射，在InnoDB中这个列被命名为FTS_DOC_ID,其类型必须是BIGINTUNSIGNED NOT NULL, 并且InnoDB存储引擎自动会在该列上加入一个名为FTS_DOC_ID_INDEX的UniqueIndex。上述这些操作都由lnnoDB存储引擎自已完成，用户也可以在建表时自动添加FTS_DOC _ID, 以及相应的UniqueIndex。由千列名为FTS_DOC_ID的列具有特殊意义，因此创建时必须注意相应的类型，否则MySQL数据库会抛出错误。

        文档中分词的插入操作是在事务提交时完成，然而对于删除操作，其在事务提交时，不删除磁盘Auxiliary Table中的记录，而只是删除 FTS Cache Index中的记录。 对 于Auxiliary Table中被删除的记录，InnoDB存储引擎 会记录 其FTS Document ID, 并将其保存在DELETED auxiliary table中 。 在设置参数innodb_ft_ aux_ table后， 用户同样可以访问information_schema架构下的表 INNODB_FT_DELETED来观察删除的FTS Document ID。

由于文档的DML操作实际并不删除索引中的数据，相反还会在对应的DELETED表中 插入 记录，因此随着应 用程序的允许，索引 会变得非常大，即使索引中的有些数据 已经被删除，查询也不会选择这类记录。 为此，InnoDB存储引擎提供了一种方式， 允许用户手工地将已经删除的记录从索引中彻底删除， 该命令就是OPTIMIZE TABLE。 

当前lnnoDB存储引擎的全文检索还存在以下的限制：

1每张表只能有一个全文检索的索引 。

2由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则。

3不支持没有单词界定符(delimiter)的语言， 如中文、 日语、 韩语等。

5.8.4 全文检索

        MySQL数据库支持全文检索(Full-Text Search)的查询,MySQL数据库通过MATCH()…AGAINST()语法支持全文检索的查询， MATCH指定了需要被查询的列， AGAINST指定了使用何种方法去进行查询。 下面将对各种查询模式进行详细的介绍。

1. Natural Language

        全文检索通过MATCH函数进行查询， 默认采用Natural Language 模式， 其表示查询带有指定word 的文档。

        在WHERE条件中使用MATCH函数，查询返回的结果是根据相关性(Relevance)进行降序排序的，即相关性最高的结果放在第一位。相关性的值是一个非负的浮点数字，0表示没有任何的相关性。根据MySQL官方的文档可知，其相关性的计算依据以下四个条件：

1 word是否在文档中出现。

2 word在文档中出现的次数。

3 word在索引列中的数量。

4 多少个文档包含该word。

2.Boolean

        MySQL数据库允许使用IN BOOLEAN MODE修饰符来进行全文检索。 当使用该修饰符时， 查询字符串的前后字符会有特殊的含义.

+表示该word必须存在。

-表示该word必须被排除。

(no operator)表示该word是可选的，但是如果出现，其相关性会更高

@distance表示查询的多个单词之间的距离是否在distance之内，distance的单位是字节。这种全文检索的查询也称为ProximitySearch。如MATCH(body) AGAINST ("'Pease pot"@30'IN BOOLEAN MODE)表示字符串Pease和pot之间的距离需在30字节内。

>表示出现该单词时增加相关性。

<表示出现该单词时降低相关性。

~ 表示允许出现该单词，但是出现时相关性为负（全文检索查询允许负相关性）。

*表示以该单词开头的单词，如lik*,表示可以是lik、like,又或者likes。

"表示短语。

3. Query Expansion

        MySQL数据库还支持全文检索的扩展查询。 这种查询通常在查询的关键词太短， 用户需要implied knowledge (隐含知识）时进行。 例如， 对于单词database的查询， 用户可能希望查询的不仅仅是包含database的文档， 可能还指那些包含MySQL、 Oracle、 D82、 RDBMS的单词。 而这时可以使用Query Expansion模式来开启全文检索的 implied knowledge。

        通过在查询短语中添加WITH QUERY EXPANSION或IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION可以开启 blind query expansion (又称为automatic relevance feedback)。 该查询分为两个阶段。

第一阶段：根据搜索的单词进行全文索引查询。

第二阶段：根据第一阶段产生的分词再进行 次全文检索的查询。