概述
InnoDB存储引擎支持以下几种常见的索引：
- B+树索引
- 全文索引
- 哈希索引
哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为的干预是否在一张表中生成哈希索引。
B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。 B+树索引的构造类似于二叉树，根据键值快速找到数据。
相关算法
- 二分查找法：折半查找，需先将数据有序化。
- 二叉查找树（不一定平衡）：左子树的键值总小于根的键值，右子树的键值总大于根的键值。
- 平衡二叉树（AVL）：2子树高度最大差1。
平衡二叉树的查找性能是比较高的，但不是最高的，只是接近最高性能。最好的性能需要建立一棵最优二叉树，但是最优二叉树的建立和维护需要大量的操作。
B+树
B+树是为磁盘或其它直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。（叶子节点之间互相有双向链表指针）
B+树索引并不能找到一个给定键值的具体行。 B+树索引能找到的只是被查找数据行所在的页。 然后数据库通过页读入到内存，再在内存中进行查找，最后得到要查找的数据。
注：B+树中的
B不是代表二叉（binary），而是代表平衡（balance）。
来源：平衡二叉树 -> B树 -> B+树
插入
B+树必须保证插入后叶子节点中的记录依然有序，同时需要考虑插入到B+树的三种情况，每种情况都会导致不同的插入算法。
| Leaf Page满 | Index Page满 | 操作 |
|---|---|---|
| No | No | 直接将记录插入到叶子节点 |
| Yes | No | 1.拆分Leaf Page 2.将中间的节点放入到Index Page中 3.小于中间节点的记录放左边 4.大于或等于中间节点的记录放右边 |
| Yes | Yes | 1.拆分Leaf Page 2.小于中间节点的记录放左边 3.大于或等于中间节点的记录放右边 - 4.拆分Index Page 5.小于中间节点的记录放左边 6.大于中间节点的记录放右边 7.中间节点放入上一层Index Page |
使用兄弟节点平衡
B+树为了保持平衡，对于新插入的键值可能需要做大量的拆分页操作。 因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作。
因此，B+树提供了类似于平衡二叉树的旋转功能。当Leaf Page满了，但其它左右兄弟节点没有满的情况下，这时B+树并不会急于去拆分页，而是将记录移到所在页的兄弟节点上。（通常，左兄弟会先检查用来做旋转操作）
删除
B+树使用填充因子来控制树的删除变化。（最小为50%）
B+树在删除时，需要考虑3种情况，但不同于插入的是，删除需要根据填充因子的变化来平衡。
| 叶子节点小于填充因子 | 中间节点小于填充因子 | 操作 |
|---|---|---|
| No | No | 直接将记录从叶子节点删除。 如果该节点还是Index Page的节点，用该节点的右节点代替。 |
| Yes | No | 合并叶子节点和它的兄弟节点，同时更新Index Page。 |
| Yes | Yes | 1.合并叶子节点和它的兄弟节点。 2.更新Index Page。 3.合并Index Page和它的兄弟节点。 |
B+树索引
B+树索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般都在2～4层。也就是说查找某一键值的行记录时，最多只需要2～4次IO。
一般的机械硬盘每秒至少可以做100次IO。
数据库中的B+树索引可以分为聚集索引（clustered index）和辅助索引（secondary index），都是B+树，叶子节点存放着所有的数据。二者不同的是，叶子节点存放的是否是一整行的信息。
聚集索引
InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。
而聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。
聚集索引的特性决定了索引组织表中的数据也是索引的一部分。
聚集索引的存储并不是物理上连续的，而是逻辑上连续的。
好处
对于主键的排序查找和范围查找非常快。
- 排序查找的操作：由于聚集索引本身就是逻辑上顺序的。
- 范围查找的操作：通过叶子节点的上层中间节点就可以得到页的范围。
例1：
explain select * from Profile order by id limit 10;虽然使用了ORDER BY对记录进行排序，但实际过程并没有进行排序操作，这就是聚集索引的特点。 例2：
explain select * from Profile where id>10 and id<10000;row行返回的是预估值，不是确切的值。 如果要找到主键某一范围的数据，通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可。
辅助索引
辅助索引（secondary index，也称非聚集索引），叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。
辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。 当通过辅助索引寻找数据时，InnoDB存储引擎会查找辅助索引并通过叶级别的指针获得指向主键索引的主键，然后通过主键索引来找到一个完整的行记录。
流程：非主键查询 -> 辅助索引 -> 主键 -> 聚集索引
-- 添加列 alter table t add c int not null; -- 添加索引 alter table t addkey idx_c(c); create index index_x_y on t(x, y);
B+树索引的相关操作
分裂
B+树索引页的分裂并不总是从页中间记录开始（简单情况），这样可能会导致页空间的浪费。实际情况，涉及并发，这才是最困难的。
例如：
数据1、2、3、4、5、6、7、8、9、10 | |分裂 V P1:1、2、3、4 P2：5、6、7、8、9、10如果插入是顺序的，P1页将不会再有数据被插入，从而导致空间的浪费。而P2又会再次分裂。
InnoDB存储引擎的Page Header中有几部分用来保持插入顺序：PAGE_LAST_INSERT、PAGE_DIRECTION、PAGE_N_DIRECTION。用于决定是向左，还是向右进行分裂，同时决定分裂记录为哪一个。
若插入是随机的，则取页的中间记录作为分裂点的记录，和之前相同。若是一个方向进行插入，选择前或后的分裂点。
管理
索引的创建和删除可以通过：
- ALTER TABLE
- CREATE/DROP INDEX
ALTER TABLE可以选择添加
INDEX或KEY。区别：
- KEY：约束constraint + 索引index
- INDEX：索引index
可以对一个列的整个数据进行索引，也可以只索引一个列的开头部分数据。
alter table t add key idx_b(b(100));对b列开头100个字节索引。
不使用索引情况
多发生于范围查找、JOIN链接操作等情况。
联合索引
例：对于联合索引(a, b)
select * from t where a=xxx and b=yyy;可以使用(a, b)联合索引。
select * from t where a=xxx;可以使用(a, b)联合索引。
select * from t where b=xxx;则不可使用这棵(a,b)的B+树索引。
联合索引的好处是，已经对第二个键值进行了排序处理。
例：取出最近三次购买记录，使用联合索引，可以避免多一次排序操作。
更多的，联合索引与order by。
select * from t where a=xxx order by b;可以使用(a, b)联合索引。
select * from t where a=xxx order by b; select * from t where a=xxx and b=xxx order by c;可以使用(a, b, c)联合索引。
select * from t where a=xxx order by c;不可以使用(a, b, c)联合索引。因为索引(a, c)并未排序。
覆盖索引
指从辅助索引就可以得到查询的记录，而不需要查询聚集索引中的记录。
好处：辅助索引不包含整行记录的所有信息，故大小远小于聚集索引，因此可以减少大量的IO操作。
如果查询列覆盖了索引的列，直接就可得到数据。否则，还需要进行二次查询。 无需二次查询：
select id, c from t where c='abc'; select c from t where c='xyz';需要二次查询：
select c, d from t where c='qwe';
哈希算法
InnoDB存储引擎使用哈希算法来对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列方式。
K = space_id « 20 + space_id + offset，除法散列到各个槽。
自适应哈希索引
数据库创建，不能干预。对于范围查找无能为力。
全文检索
B+树支持字段内容的前缀查找。
select * from t where content like 'xxx%';
更多情况下，用户需要查找含有单词xxx的文章。
select * from t where content like '%xxx%';
全文检索通过存储于数据库中的词，也可以进行各种统计和分析。
倒排索引
存储单词与单词在一个或多个文档中所在位置之间的映射。
- {单词， 单词所在的文档ID}
- {单词， （单词所在的文档ID，在具体文档中的位置）}
目前不支持中文。
注
聚集索引必须要求字段唯一？
不是，可以建立在任意列上，如果没有unique约束，数据库将自动添加一个4字节的uniqueifier列，使每个键唯一。
聚集索引一定比非聚集索引性能优？
不是，例如查询学生姓名和分数，在姓名和学分上建立联合非聚集索引，此时的索引就形成了覆盖索引，即索引所存储的内容就是最终的输出数据。这种情况下，非聚集索引性能更好。