1、概述

1、Innodb引擎常见三种索引类型

全文索引

B+树索引
哈希索引

2、B+树怎么查找

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

3.二叉查找树与平衡树定义

可参考原文：
第五章：索引与算法

2、B+树索引

1、B+树定义

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

B+树索引的本质就是B+树在数据库中的实现，B+索引在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般在2~4层，也就是说查找某一个键值的行记录最多只需要2 ~ 4次。

关于B+树增删操作（二叉平衡树增删）查看原文。

2、聚集索引

聚簇索引就是按照每张表的主键构造一颗B+树，同时叶子节点存放的即为整张表的行记录数据，也将聚簇索引的叶子节点成为数据页。每一个数据页都是通过一个双向链表进行链接的。每张表只能拥有一个聚簇索引。

聚簇索引的存储并不是物理上连续的，而是逻辑上连续的。

聚簇索引对于主键的排序查找和范围查找的速度非常快。

3、辅助索引

叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark），该书签用来告诉InnoDb引擎哪里可以找到与索引相对应的行数据，Innodb存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引的查找过程：先遍历辅助索引并通过叶级别的指针获取指向主键索引的主键，然后在通过主键索引来找到一个完整的行记录。
第五章：索引与算法

4、B+树索引的分裂

参考原文

5、B+树索引的管理

sql之类的，参考原文

3、Cardinality值

1、判断是否创建索引的必要

并不是所有的查询条件中出现的列都需要添加索引，一般经验是：在访问表中很少一部分时使用B+书索引才有意义，如果一个字段的可取值范围小（低选择性），那么就不一定适合作为索引。如果一个字段的取值范围广（高选择性），几乎没有重复，那么使用B+树索引最适合。

通过SHOW INDEX From 表名语句查看结果的Cardinality观察是否有创建索引的必要性，一般通过查看Cardinality/数据总行树，越接近1，则越有必要创建索引

2、Cardinality值的统计

考虑到表数据量大和频繁的更新，数据库对Cardinality值的计算是通过采样的方法来完成的。

更新Cardinality数据的依据：

- 1、表中超过1/16的数据已发生过变化
- 2、存储引擎内部计数器stat_modified_counter发生了 2000000000次改变

Cardinality是对随机取的8个叶子节点进行分析，可能造成每次去到的Cardinality值不一样。

4、B+树索引的使用

1、联合索引

联合索引是指对表上的多个列进行索引，联合索引也是一颗B+树。

联合索引的生效举例：比如创建一个（A,B）的联合索引，那么在查询的时候，这个联合索引会对两类查询语句生效，一种是 where A= ？ and B = ？，以及where A=？，而对于where b = ？不生效，可以搜索索引的最左前缀原则，同理，大于两个键的联合索引也是在前面的索引生效的情况下后面的索引才可能生效，如果前面的索引键不生效，则后面的索引键不会生效。

联合索引对于第二个键（或者后面的键）已经做了排序，举个例子：比如我们现在有（A，B，C）的一个联合索引，如果我们的数据如下面所示：

                                          (1,      2,      1)
                                          (1,      2,      3)
                                          (1,      2,      5)
                                          (1,      3,      3)
     假如我们的sql语句是select * from 表名 where A= 1 and B= 2 order by C，那么这个时候，因为我们的联合索引已经排序好了，所以我们可以直接拿到数据，而略过排序这一步骤
      而如果我们的sql是：select * from 表名 where A= 1 order by C，直接略过中间的B，那么这个时候我们的（A，B，C）的联合索引的排序就没用，数据库会帮助我们重新排序一下。
      所以当我们如果使用到排序的时候可以考虑是否创建一个联合索引，排序的字段作为最后一个字段。

2、覆盖索引

参考原书

3、优化器不使用索引的情况