5. 索引与算法—B+树的操作、辅助索引与聚集索引、Cardinality、联合索引、覆盖索引、MRR/ICP、哈希算法、全文索引

B+ 树是为磁盘或其他直接存储辅助设备设计的一种平衡查找树。在B+树中，所有记录都是按照键值大小顺序存放在同一层的叶子节点上，由叶子节点指针进行连接，双向链表连接。

5.3.1 B+ 树的插入操作

考虑一下三种情况：

Leaf Page满	Index Page 满	操作
No	No	直接插入到叶子节点
Yes	No	1. 拆分 Leaf Page 将中间节点放入 Index Page 小于中间节点的记录放左边 大于或等于中间记录的放右边
Yes	Yes	拆分 Leaf Page 小于中间节点的记录放左边 大于或等于中间记录的放右边 拆分 IndexPage  小于中间节点的记录放左边 大于或等于中间记录的放右边 中间节点放入上一层Index Page

可以看到，为了保持平衡对于新插入的键值可能需要做大量的拆分页操作。因为 B+ 树主要用于磁盘，页的拆分意味着磁盘的操作，所以，应该在可能的情况下尽量减少页的拆分。因此，B+ 树提供了类似平衡二叉树的旋转功能（Rotation）。

旋转发生在Leaf Page满，但其左右兄弟节点没有满的情况下，这时B+树不是先拆页，而是将记录移到所在页的兄弟节点上。通常情况下，左兄弟会首先被用来检查做旋转操作，采用旋转操作会使B+ 树减少一次页的拆分，同时有利于减少B+树的高度。

5.3.2 B+ 树的删除操作

B+树的删除操作同样必须保证删除后叶子界点依然有序，同时 B+ 树使用填充因子（fill factor）来控制树的删除变化，50%是可控制的最小值。与插入不同的是，删除根据填充因子的变化来衡量。

Leaf Page满	Index Page 满	操作
No	No	直接将记录从叶子节点删除，如果该节点还是 Index Page节点，则用该节点的右节点代替
Yes	No	合并叶子节点和它的兄弟节点，同时更新 Index Page
Yes	Yes	合并叶子节点和她的兄弟节点 更新 index page 合并 index Page 和她的兄弟节点

B+ 树的特点就是高扇出性，因此，在数据库中，B+ 树的高度一般在 2~4 层，也就是说查找某一键值的行记录时最多只需要2到4次的IO，大概耗时在 0.02~0.04秒。

5.4.1 聚集索引

聚集索引就是按照每张表的主键构造一棵  B+树，同时叶子节点存放的是整张表的行记录数据，也将聚集索引的叶子节点称为数据页，每个数据页之间通过一个双向链表进行连接。

数据页上存放的是完整的每行的记录，而非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量，而不是完整的行记录。

聚集索引并不是物理上连续的，而是逻辑连续。即 页通过双向链表连接，页按照主键的顺序排序。另一点是每个页中的记录也是通过双向链表韦华的，物理存储上可以同样不按照主键存储。

聚集索引对于主键的排序查找和范围查找速度很快。

5.4.2 辅助索引

 辅助索引的叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签。该书签用来告诉 InnoDB哪里可以找到与索引相对应的行数据。

非聚集索引存在离散读问题，但一般的数据库都通过实现预读（read ahead）技术来避免多次离散读的问题。

5.4.3 B+ 树索引的分裂

3 中B+树的分裂是最简单的一种情况，这和数据库中B+ 树索引的情况略有不同。而且5.3中没有涉及并发，这才是B+树索引实现最困难的地方。

B+ 树索引页的分裂并不总是从页的中间记录开始，这样可能会导致页空间的浪费，例如自增主键的插入。

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

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通过这些信息，InnoDB决定是向左还是向右分裂，同时决定分裂点记录是哪一个。

若插入是随机的，则取页的中间记录为分裂点

若往同一个方向进行插入的记录是5，且目前已定位到的记录之后还有3条记录，则分裂点为定位到的记录后的第三条记录，否则分裂点记录就是待插入的记录。

InnoDB 存储引擎插入时，首先需要进行定位，定位到记录为待插入记录的前一条记录

自增插入时，分裂点就是插入记录本身，向右分裂。

5.4.4 B+树索引的管理

1. 索引管理

索引的创建和删除可以通过两种方法，alter table 或 create/ drop index

通过 show index from 可以观察到表的索引。接着阐述 show index结果中每列的含义。

• table ：索引所在的表名
• Non_unique：非唯一的索引，0标识唯一索引，1标识非唯一索引。
• Key_name：索引的名字，用户可以根据这个名字执行 drop index
• Seq_in_index：索引中该列的位置，一般为联合索引中列的位置
• Column_name：索引列的名称
• Collation：列以什么方式存储在索引汇总，A或者NULL，B+ 树索引总是A，标识排序的。
• Cardinality：索引中唯一值的数目的估计值。值越大区分度越大。
• Sub_part：是否是列的部分被索引，例如 add key idx_b(b(100)) ,只对b字段的前100个字符索引。如果索引整个列，该字段为NULL
• Packed：关键字如何被压缩，没有压缩，为NULL
• Null：索引列是否含有空值
• Index_type：索引类型，InnoDB 只支持B+ Tree，所以这里都显示BTREE
• Comment：注释

2. Fast Index Creation

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

4. Online DDL

虽然FIC可以让InnoDB存储引擎避免创建临时表，从而提高索引创建的效率，但会阻塞表上的DML 操作。MySQL 5.6 开始支持 Online DDL操作,允许辅助索引创建的同时，还允许其他DML 操作。

此外，不仅是辅助索引，以下几类操作都是通过”在线“的方式进行操作：辅助索引的创建和删除；改变自增长值；添加或删除外键约束；列的重命名；

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

alter table tbl_name

| ADD {INDEX | KEY} [index_name]

[index_type] (index_col_name……)[index_option]……

ALGORITHM[=]{DEFAULT | INPLACE | COPY}

LOCK[=]{DEFAULT | NONE | SHARED |EXCLUSIVE}

　　ALGORITHM指定了创建或删除索引的算法，COPY标识MySQL 5.1 版本之前的工作模式，即创建临时表的方式。INPLACE 标识索引创建或删除操作不需要创建临时表。DEFAULT 标识根据参数 old_alter_table 来判断是通过 INPLACE 还是 COPY 算法，该参数的默认值是 OFF，标识采用 INPLACE 的方式。

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

1. NONE：执行索引创建或删除操作时，对目标表不添加任何的锁，即事务可以进行读写操作，不会收到阻塞。因此，这种模式可以获得最大的并发度。
2. SHARE：类似FIC，对目标表加S锁，阻塞写。如果不支持SHARE模式，会返回一个错误的信息。
3. EXCLUSIVE：加X锁，读写事务都不能进行，会阻塞所有的线程，但不需要像COPY那样创建临时表
4. DEFAULT：default 模式会首先判断当前操作是否可以使用NONE模式。若不能，降级到SHARE模式，最后看是否可以使用 EXCLUSIVE模式。也就是说DEFAULT会通过判断失误的最大并发度来执行DDL 的模式

InnoDB 存储引擎实现 Online DDL 的原理是在执行创建或删除操作的同时，将INSERT、UPDATE、DELETE 这类DML 操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此达到数据的一致性。这意味着在索引创建的过程中，SQL优化器不会选择正在创建中的索引。

5.6.2 联合索引

从本质来看，联合索引也是一棵B+树。联合索引是最左前缀匹配。

联合索引（a,b）其实是根据列a，b进行排序的，因此下列语句可以直接使用联合索引查询结果

select * from table where a= xxx order by b

　　然而对于联合索引（a,b,c）下列语句同样可以直接使用索引得到结果

select * from table where a = xxx order by b
select * from table where a = xx and b = xx order by c

　　但是下面的语句不能直接使用联合索引（a,b,c），因为索引（a,c）并未排序

select * from table where a = xx order by c

5.6.3 覆盖索引

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

覆盖索引的另一个好处是对于某些统计问题而言，

通常情况下，诸如（a,b）的联合索引，一般是不可以选择列b中所谓的查询条件，但如果是统计，并且是覆盖索引的，则优化器会进行选择

select count(*) from  table where b < xxx and b > yyy

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

某些情况下，当执行 explain 命令进行sql语句分析时，发现优化器并没有选择索引去查找数据，而是通过扫描聚集索引，也就是全表扫描。这种情况多发生与范围查找、JOIN 操作等情况。

即explain分析得到key使用的是 PRIMARY。

因为，用户要选取的数据是整行信息，即 select * ，而索引并不能覆盖我们要查询的信息，因此在对辅助索引查询到指定数据后，还需要进行一次书签访问来查找整行数据的信息。虽然辅助索引中数据是顺序排放的，但再一次书签查找是无序的，因此变为了磁盘的离散读操作。如果要访问的数据量小，则优化器会选择辅助索引，但当访问的数据量大（一般为20%左右），优化器会选择聚集索引来查找数据，因为顺序读要远远快于离散读。这是由当前传统机械硬盘的特性决定的，即利用顺序读代替随机读的查找。如果用户使用的是固态硬盘，随机读很快，同时可以确认使用辅助索引可以带来更好的性能，可以使用 force index 强制使用某个索引

5.6.5 索引提示

MySQL支持索引提示（INDEX HINT），显示的告诉优化器使用哪个索引。个人总结两种情况可能使用索引提示：

• MySQL优化器错误的选择某个索引，导致SQL运行慢，较少见
• 某SQL可以选择的索引非常多，这时优化器选择执行计划时间的开销可能大于SQL本身

5.6.6 Multi—Range READ 优化

MySQL 5.6 开始支持 Multi-Range READ（MRR） 优化，目的是为了减少磁盘的随机访问，并将随机访问转化为较为顺序的数据访问，适用于 range、ref、eq_ref类型的查询。

MRR有以下几个好处：

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

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

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

此外，若InnoDB的缓冲池不是很大，不能放下一张表中的所有数据，此时频繁的离散读还会导致缓存中的页被替换出缓冲池，然后又不断的读入缓冲池。若是按照主键顺序的访问，则可以将此重复行为将至最低。如下面的SQL:

select * from table where salary > 10000 and salary < 44000;

　　salary 有一个辅助索引idx_s，因此除了通过辅助索引查找键值外，还需要通过书签查找来进行对整行的查询，当不启用MRR时，执行计划中的 Extra 显示 Using index condition，启用MRR后，Extra 除了有 Using Index Condition 还有 Using MRR，执行时间相差10倍之多。注意：该测试都是在MySQL数据库刚刚启动时执行的，确保缓冲池中没有预热。

此外，MRR 还可以将某些范围查询拆分为键值对，以此来进行批量的数据查询。这样做的好处是在拆分过程中，可以过滤一些不符合查询条件的数据。

select * from t 
where key_part1 >= 1000 and key_part1 < 2000 
and key_part2 = 1000

　　表t有（key_part1, key_part2）的联合索引，如果没有MRR，则查询类型为 Range，SQL 优化器会先将key_part1 符合范围的数据都取出来，即使 key_part2 不等于1000，然后再对数据进行过滤。这就导致无用的数据被取出，如果有大量数据且 key_part2 != 1000,则 MRR 会使性能提升很快。

　　启用MRR之后，优化器会先对查询条件进行拆分。就上述语句，会拆分为（1000，1000），（1001， 1000），（1002，1000）……（1999，1000），最后再根据这些拆分出来的条件进行查询。

    实际例子如下：

select *  from salaries 
where （from_date between "1986-01-01" and "1995-01-01"）
and  (salary between 38000 and 40000)

5.6.7 Index Condition Pushdown (ICP)优化

当进行索引查询时，首先根据索引来查找记录，然后再根据where过滤。在支持 ICP后，MySQL会在取出索引的同时，判断是否可以进行where条件的过滤，也就是将where的部分过滤操作放在了存储引擎层。

ICP 优化支持 range、ref、eq_ref、ref_or_null类型的查询。若使用了ICP，可以在执行计划的Extra列看到 Using Index condition。当然 where 可以过滤的条件是要该索引可以覆盖到的范围。

5.7.1 哈希表

哈希表也叫散列表，由直接寻址表改进而来。哈希表，在哈希方式下，该元素处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。哈希表存在碰撞问题，在数据库中一般采用链接法解决碰撞。

5.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 ,然后通过除法散列。

5.7.3 自适应哈希索引

AHI 是数据库自身创建并使用的，DBA不能进行干预。哈希索引只能用于等值查询，不能用于范围查找。

5.8.1 概述

B+树索引对 where a like "%abc%"无能为力，即使对a 添加索引，也是需要进行全表扫描的。

全文检索（Ful-Text Search）是将存储于数据库中的整本书或整个文章中的任意内容信息查找出来的技术，可以根据需要获取全文中的有关章、节、段、句、词等信息，也可以用于统计和分析。

从InnoDB 1.2.x开始，InnoDB开始支持全文检索，其支持 MyISAM存储引擎的全部功能，并且还支持其他的一些特性。

5.8.2 倒排索引（Inverted index）

全文索引通常使用倒排索引来实现，倒排索引也是一种索引结构，它在辅助表中存储了单词与单词自身在一个或多个文档中所在位置键的映射，通常这利用关联数组来实现，其拥有两种表现形式：

• inverted File index：表现形式为{单词，单词所在的文档id}
• full inverted index：表现形式为 {单词，（单词所在的文档id， 在具体文档中的位置）}

5.8.3 InnoDB全文索引

InnoDB 从1.2.x 开始支持全文索引的技术，并采用 full inverted index 的方式。在 InnoDB 存储引擎中，将 （单词所在的文档id/doucumentId, 在文档中的具体位置/Position） 视为一个ilist。

在全文检索的辅助表中，有两列，分别是 word 列 和 ilist 列。

正如之前所说的，倒排索引需要将word 存放在一张表中，这个表称为 Auxiliary table（辅助表）。在InnoDB中，为了提高性能，共有6张辅助表，目前每张表根据 word 的Latin 编码进行分区。

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

FTS Index Cache 是一个红黑树结构，根据（word，ilist）进行排序，这意味着插入的数据已经更新了对应的表，但对全文索引的更新可能在分词操作后，还在FTS Index cache中，Auxiliary table 可能还没更新。InnoDB对 Auxiliary 的更新是批量的，当全文检索时，Auxiliary table 首先会将在 FTS Index Cache中对应的 word 字段合并到 Auxiliary table 中，然后再查询。这种merge操作类似 Insert Buffer。

FTS Document ID 是另一个重要概念，InnoDB中，为了支持全文检索，必须有一个列与 word 进行映射，在 InnoDB中这个列被称为 FTS_DOC_ID，其类型必须是 BIGINT UNSIGNED NOT NULL，并且InnoDB会自动在该列上加入一个名为 FTS_DOC_ID_INDEX 的 Unsigned Index。这些操作都是InnoDB自动完成的。

stopword 列表（stopword list）是本节最后一个概念，标识该列表中的word不需要对其进行索引分词操作，例如 the 。InnoDB有一张默认的 stopword list 表，表名为 INNODB_FT_DEFAULT_STOPWORD，默认有36个stopword，用户可自定义。

当前InnoDB的全文检索还存在以下问题：

1. 每张表只能有一个全文检索的索引
2. 由多列组成的全文检索的索引列必修使用相同的字符集与排列规则
3. 不支持没有单词界定次的语言，如中文、日语、韩语等

5.8.4 全文检索（待续……）