第5章 索引与算法
1 InnoDB存储引擎索引概述
InnoDB存在B+Tree索引、Hash索引、全文索引
InnoDB会在频繁查询的B+Tree上建立Hash索引
2 数据结构与算法
2.1 二分查找法
略
2.2 二叉查找树和平衡二叉树
二叉查找树是一颗可以进行二分查找的树，左节点值<根节点<右节点
但有时二叉查找树“歪了”的话，查询效率就会变得很低，所以需要在插入时将其变为平衡二叉树
3 B+树
3.1B+树插入
1>B+树一个节点的大小等于一页(默认16KB)
2>当叶子点满了，会将叶子节点分裂，将小于中间值的放在左节点，大于等于的放在右节点，然后将中间值插入至上级父索引节点中
3>B+树的叶子节点有双向链表
4>旋转，B+树在插入时节点满了，而兄弟节点没满，则会平移记录
3.2 B+树的删除操作
删除节点时，一般直接删除，若该值为索引值，那么索引节点中的该值也会删除掉，若删完后节点中值还很多那么会将兄弟节点左移，少的话会合并节点。
【es的删除时假删除，会在查询结果中过滤掉删除数据，从而避免对索引做耗时较大的删除重排操作】
4 B+树索引
4.1 聚集索引
1>B+树索引是高扇出的，高度一般为2-4，所以查询时的磁盘IO次数也为2-4，所以查询时的磁盘IO次数也为2-4次。
2>因为B+树索引的叶子节点上存在双向链表，所以对于排序查找与范围查找是非常快的(同时利用上层索引节点值确定需查询范围)
4.2 辅助索引
与聚集索引的区别主要为辅助索引叶子节点中键值存放了指向聚集索引的指针，而聚集索引的叶子节点放了具体的数据
在使用辅助索引时，会先查询辅助索引，在拿到聚集索引的值去查询聚集索引
4.3 B+树的分裂
1>随机插入就是普通的B+树分裂
2>若顺序插入，则将插入点右边第三个记录视为分裂记录
4.4 B+树索引的管理
1>索引管理
索引可以只建立一列前N个数据的索引，若索引下的数据太少可以考虑删除该索引，可通过analyze table手动刷新该值，确保优化器可以正常的使用索引。
2>Fast Index Creation
MySQL5.4及之前，对于索引创建会先创建一张新表，加索引，然后将原表数据导入，这个时候会加排它锁。
InnoDB1.0.x之后可对辅助索引快速建表，此过程只会加共享锁。
3>Online Schema Change
P207
4>Online DDL
可以在创建时选择是否创建临时表
可以设置不适用锁，使用S锁，使用X锁，自适应是否加锁
不必加锁的原因是可以通过事务缓存来记录复制期间的事务，达到最终一致性
5 Cardinality值
5.1 什么是Cardinality
不重复的估计值，是预估值，而不是一个准确值，这个值除以数据行数，如果太小的话，不建议使用索引，因为即使在索引中查到了，也需要在相同值中扫描相关数据，从而使索引失去意义。
5.2 InnoDB存储引擎的cardinality统计
更新策略：
1>表中1/16的数据已发生变化
2>表变化操作次数大于2000 000 000次
更新方法：
随机取8个叶子节点计算
6 B+树索引的使用
6.1 不同应用中B+树索引的使用
在OLTP应用中，由于每次只查询少量数据，故使用索引是很有必要的。
而OLAP应用因为每次需要拉取大量的数据，不太适合索引，但应在时间字段加上索引以及考虑分区。如果有大量的表间链接，也推荐使用索引。
6.2 联合索引
对两列进行B+树索引创建，如(a,b)。底层形成的时一颗B+树，先由a排序，再由B排序
与不适用联合索引，使用两个单独的索引比较：
1>占用空间少
2>对a查询，对b排序场景下，可以省区排序操作
3>对a查询，对a AND b查询，不能支持只查询b
6.3 覆盖索引
因为辅助索引中存在辅助索引列的值，所以使用辅助索引查询时可以直接取到辅助索引的值，而不用回表。
在查询count()时，即使没有查询辅助索引，也会使用辅助索引，因为辅助索引比聚簇索引小。
在查询count()时，若按联合索引的非首列查询，甚至可以走联合索引确定count()的值
6.4 优化器选择不使用索引的情况
当某些范围查询或表间链接查询发生时，即使可以使用辅助索引，但是在辅助索引查询完后，还是需要再去聚集索引，这之间是有IO操作开销的，所以在大范围查询(20%左右)时，会不走查询的索引，而是用聚集索引顺序读取
如果使用固态硬盘并且确定走索引快，可以通过修改SQL语句使用索引
【通过辅助索引查询，辅助索引列式连续的，但是通过辅助索引查询到的聚集索引是离散的，这种离散有时不如直接全表扫描来的快(一般为20%)】
6.5 索引提示
为查询指定使用的索引（force index）
①在优化器选择了错误的索引，导致查询变慢时(很少发生)
②索引过多，优化器计算范围查询时使用哪个索引消耗很大时
6.6Multi-Range Read优化(MRR)
通过辅助索引进行范围查询时，会再去聚集索引进行离散读来获取数据，为了避免离散读时的大量磁盘IO消耗，InnoDB会将辅助索引查询结果排序，再去聚集索引中顺序的取数据来减少离散IO
6.7 Index Condition Pushdown(ICP)优化
查询时如果设定了like这样的限定条件，而在查询辅助索引时有覆盖这些列，则会直接先过滤再去聚簇索引取记录
7 哈希算法
7.1 哈希表
同Java Hash Map
7.2 存储引擎中的哈希算法
通过space_id进行散列除法计算，除数为页数x2后第一个质数
7.3 自适应哈希索引
由Innodb自己控制，在查找类似字典的类型常用，对范围查找无力，可以禁用
8 全文检索
8.1 概述
InnoDB1.2.x版本开始，InnoDB支持索引
8.2 倒排索引
对文章中出现的各单词建立倒排索引
类型：
1>inverted file index {单词，单词所在文档ID}
2>full inverted index{单词，(单词在文档ID，在文档中的位置)}
第2种需要更大的空间，但有更多的功能
8.3 InnoDB全文检索
实现方式为第2种
倒排索引在内存中有红黑树缓存，也可以合并更新
限制：
1>每张表只能有一个全文检索的索引
2>多列组合而成的全文检索索引必须用相同字符集与排序
3>不支持中文，日语，韩语
8.4 全文检索
1>Natural Language：默认方式
2>Boolean：查询字符串前后会有特殊意义P244
3>Query Expansion：对查询字符进行智能相关性查询
倒排索引可通过Hash表或B+树实现，但是hash表适合内存大，B+树适合磁盘存储