一、概念

        索引是一种可以高效获取数据的数据结构，类似一本书的目录，能加快数据库的查询速度，索引文件本身很大，是存储在磁盘中的文件中的。

1.优势

• 加快了数据库的查询速度，降低了IO成本
• 可以通过索引对数据进行排序，加快排序速度，降低CPU的消耗

2.劣势

• 索引会占用一定的磁盘空间
• 数据更新变慢，当更新数据时，不仅要存储数据，还要存储索引

二、索引的数据结构

1.Hash表

        Hash表类似Java中的HashMap，以建值的方式进行存储数据，键存储的就是索引，值存储的是对应的列值或数据的地址。因此Hash表在等值查询中速度很快，时间复杂度只有O(1)，但不支持范围查询，范围查询还需要进行全表扫描。

2.二叉树

        每个根节点最多有两个分支，左分支的节点值必须小于根节点的值，右分支的节点值必须大于根节点的值。

• 优势：采用二分查找，减少了IO的次数，查询效率提高

• 劣势：不稳定，可能存在根节点取值的问题

 3.平衡二叉树

        平衡二叉树具备二叉树的特点，其本身的左右子树层级的高度差不会超过1，在插入或删除的时候，会对二叉树进行左旋转或右旋转，不会出现左子树很低，右子树很高的情况。

• 优势

1. 使用二分查找法，时间复杂度为O(log2n)，降低了磁盘IO操作
2. 不会存在左右子树层级相差过大的情况

• 劣势

1. 时间复杂度和树的高度有关，数据量越大，树的高度越大，树的高度相当于读取磁盘IO的次数，在数据量很大时，读取效率很差。
2. 数据是不连续的，不能进行范围查找，范围查找需要多次遍历根节点，效率较低。

4.B树(改造二叉树)

        Mysql的数据是存储在磁盘中的，当读取磁盘中的数据时，会先查询磁盘中的数据到内存中。每一次磁盘查询都是一次IO，是非常耗时的，然而读取二叉树的每一个节点都是一次IO，如果想要减少磁盘的IO，就需要降低树的高度，因此诞生了B树。

        B树是一种多平衡二叉树，其特点为：

• B树每个节点中都保存了多个数据，每个节点都有多个分叉
• 节点中的数据包含键值和数据，根据键值从小到大排列，即每个节点包包含数据
• 父节点中的数据不会出现在子节点中
• 所有的叶子节点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接

 缺陷

1. 所有的节点都存储数据导致数据是不连续的，无法范围查询数据
2. 每个节点存储列数据，随着数据量的增多，会占用很多的磁盘空间

5.B+树(改造B树)

        B+树是B树的改造，B树和B+树最主要的区别是非叶子节点是否保存数据。

• B树：非叶子节点和叶子节点都会保存数据
• B+树：只有叶子节点才会保存数据，非叶子节点只会保存键，且叶子节点所有的数据都是连续的双向有序链表，适合范围查找

 三、Innodb引擎的索引

1.主键索引(聚簇索引)

        每个Innodb的表都有一个聚簇索引，其底层结构是B+树。

• 当表中定义主键PRIMARY KEY时，Innodb会将主键作为聚簇索引
• 当表没有定义主键时，Innodb会将第一个不为NULL的唯一索引作为聚簇索引
• 当上两个条件不满足时，Innodb会建立一个6字节的长整型rowid作为聚簇索引，会根据列的数量进行自增

2.辅助索引(二级索引)

        除聚簇索引之外的所有索引都是辅助索引，辅助索引只会存储当前索引的列和主键的列。

        当使用辅助索引且需要查找除辅助索引之外的列时，Innodb会先从辅助索引找到当前辅助索引的列值和主键索引，再根据主键索引查询其他列的值，这个操作叫做回表。这样的磁盘IO数为：辅助索引3次+获取记录回表3次。

 3.联合索引(组合索引)

        联合索引是指对表上的多个列进行索引，同时也会保存主键索引。

 最左匹配原则

        对表table设置了(a,b,c)的联合索引。

        最左匹配原则和联合索引的索引存储结构和检索方式是有关联的。

        当设置了a，b，c的联合索引，B+树的最底层叶子节点的第一层会根据a的顺序进行排序，因此b列只有在a列等值的情况下才会小范围递增排序，c列在a，b列等值的情况下才会小范围递增。

        如上图的查询，当查询条件有a列时，B+树会从a列开始进行查询，来确定下一步的查询方向(向左还是向右)，a列相同再比较b列，如果查询条件没有a列，那么查询效率就会慢很多。

4.覆盖索引

        上述中说到联合索引，当索引中没有要查询的列值时，只有一部分，B+树会根据主键索引进行回表，查询其他的列值，每一次回表操作都是一次IO，会消耗磁盘的性能。

        覆盖索引就是将要查询的所有列都设置为联合索引，这样就可以避免回表，降低磁盘的IO，加快查询效率，是最常用的索引优化手段。

四、总结与优化

1.避免回表

        尽量将要查询的列都设置为联合索引，这样可以避免B+树的回表，增加查询效率。

2.联合索引的使用

1. 尽量在单列索引上判断是否可以使用联合索引，例如建立了(a,b,c)的联合索引，就相当于有了(a)，(a,b)，(a,b,c)三个索引，这样不仅优化了查询效率，同时还节省了需要建立多个单列索引的空间。
2. 创建联合索引时，尽量把查询频繁、区分度高的索引列放在左边，查询频繁说明引用率高，区分度高说明粒度大，这样可以在第一次筛选就过滤掉大部分数据，很大的优化了查询的效率。

五、Mysql设计之三星索引

        三星索引指满足了三个星级的索引

1. 把where后面的等值查询的列作为联合索引的开头，可以与联合索引最前面的列相邻，也就是最左匹配原则，这样可以在索引首次查询时过滤掉大部分数据，尽可能减少索引列的宽度。

2. 排除了排序操作，order by后面的排序条件与索引的顺序相同，可以减少排序带来的性能消耗。

3. 所要查询的列全部都在联合索引中，可以避免B+树的回表，减少磁盘IO，提高查询效率。