INnoDB（索引与算法）

索引与算法

InnoDB存储引擎支持&常见索引

1. B+树索引

2. 全文索引

3. hash索引

B+ 树索引不能给具体行数据，索引只能找到行所在的页，读到内存之后，再进行查找

mysql5.5之前（不包括5.5）增加索引流程

1. 创建临时表

2. 原始数据导入临时表

3. 删除原表

4. 修改临时表为原来表名

缺点：大表的索引添加修改，需要很长时间，且修改时间内数据库不可用

InnoDB1.0.x解决了这个痛点问题

​ 解决方案：引入FIC（快速索引创建）

1. 创建索引的表上增加S锁（不需要重建表）
2. 添加S锁期间，只能读操作
3. 删除索引，只需要存储引擎更新内部视图，将辅助索引标记为可用
4. FIC 仅限于辅助索引，主键操作依旧需要重建表

OSC（在线架构改变）

Online DDL

FIC 可以避免InnoDB创建临时表，提高索引创建的效率，但是会阻塞DML，OSC也没有完美解决这个问题，mysql5.6开始支持Online DDL

1. 辅助索引的创建与删除
2. 改变自增长
3. 添加或者删除外键约束
4. 列的重命名

MRR（减少磁盘随机访问，转化为相对有序的访问）

1. mysql 5.6开始支持MRR
2. 适用范围 range ref eq_ref
3. 优势
   1. 使数据访问相对有序，查询辅助索引时，根据查询结果按照主键排序，按照主键排序顺序进行查找
   2. 减少缓冲池中页被替换的次数
   3. 批量处理对键值对的查询操作
4. MRR工作原理
   1. 查询得到的辅助索引放到缓存里面（根据辅助索引键值对排序）
   2. 缓存中键值对按照RowID排序
   3. 根据RowID排序顺序实际访问数据文件
   4. 缓冲池不够大的时候 MRR会失效

ICP（根据索引进行查询的优化模式）

1. mysql5.6之后开始支持
2. ICP工作原理
   1. 根据索引查找记录，然后直接根据where条件过滤数据（过滤数据操作在引擎层操作）
3. ICP使用范围：
   1. myidsam引擎&InnoDB引擎
   2. 支持 range，ref，eq_ref，ref_or_null类型查询

哈希算法

哈希表（散列表）

1. 解决hash碰撞采用链表法

InnoDB存储引擎的哈希算法

自适应哈希索引

1. DBA无法干预
2. 只能用来搜索等值查询

全文检索

1. InnoDB引擎1.2.x支持，myisam支持
2. InnoDB存储全文检索索引限制
   1. 每张表只能有一个全文索引的索引
   2. 多列组合而成的全文索引的索引列必须使用相同的字符集和排列规则
   3. 不支持没有单词界定符的语言（中文，日文，韩语）

倒排索引

1. 辅助表存储单词与单词自身在的一个或者多个所在位置的映射
   1. 位置存储的是位置数组