1.索引介绍
索引优化，可以说是数据库相关优化，尤其是
query
优化中最常用的优化手段之一。
是mysql为了满足某种特定查找算法而维护的数据结构。
在mysql中，有着不同类型的索引：
B-Tree索引，Hash索引、Fulltext索引和R-Tree索引
。不同的存储引擎使用不同的结构：比如MyIsam跟innodb，其底层使用的是B+树，如果是Memory存储引擎，那么对应的底层数据结构是Hash表。
如果从应用方面去区分：
主键索引，普通索引，唯一索引，复合索引，全文索引
从数据的物理顺序与键值的逻辑区分：
聚集索引，非聚集索引
2.二叉树与btree
二叉树的特点：一个节点只能有两个子节点，左子节点小于本节点，右子节点大于本节点
平衡二叉树：而二叉树又有平衡与否的问题，原因是在于虽然二叉树可以使用二分查找法，每次先找中间值，然后进行值判断，小于则左边找，大于则向右边找。但如果两边节点不平衡的情况下，这种查找性能不是特别高。于是就有平衡二叉树诞生了，平衡二叉树即两边子节点数对应，且平衡。
但平衡二叉树的维护成本也不小，每次新增一个节点就要调整一次平衡。
其他树：
AVL树：平衡二叉树又称为AVL树，在满足二叉树特点的基础上，还要求每个节点的左右子树的高度差不能超过1
AVL优点：很好的查找性能，不存在极端的低效查找情况。 可以实现范围查找，数据排序
红黑树：从根到叶子的最长的
可能路径不多于最短的可能路径的两倍长
红黑树优缺点：每次插入都要检查规则，再把树进行重新平衡，这个是非常消耗时间,数据量大的话，
红黑树的深度会比较深，并且产生“右倾”,树一旦深就代表着我们读取磁盘次数就会增加，因此 不能直接用于实现 Mysql 底层索引
Btree：为了提升查找效率，在每个节点上尽可能的存储多点数据，一次磁盘io就尽可能的加载数据到内存，所以把树的高度降低，节点提升数据存储，这就有了B树
B树优点：
1.优秀的检索速度，2.尽可能少的磁盘io，加快了检索速度，3.可以支持范围查找
B+Tree :
对B树的改进，简单的说是：只有叶子节点才存数据，非叶子节点存储指针，且所有叶子节点构成一个有序链表
3.主索引和辅助索引
在innodb引擎中，每一个索引都对应一颗B+ tree ，innodb的索引主要分为主索引和辅助索引：
主索引：在innodb中，
主索引的叶子节点存的是整行数据，记录的数据根据主索引，即主键制定的顺序排序。这也称为聚集索引。
一张表只能有一个聚集索引
辅助索引：innodb中的辅助索引在叶子节点中并不存储实际的数据，只会包含主索引的值。这就意味着在
innodb中辅助索引是依赖于主索引的，
因为数据存放于主索引中。
为什么建表的时候都添加有一个自增的主键？
答：因为主键是聚簇索引，它是要按照顺序进行排序的，要求有聚簇性。如果使用一般字段作为主键，不能保证每次插入的数据都是按某种顺序进行排列的，这就使得每次主键的插入都变得完全随机，可能导致每次插入一条数据都会引起页分裂的问题。所以在表结构定义的时候，应该使用一个具有聚集性的 key 作为主键，如果真的没有的话，可以使用一个 AUTO INCREMENT 代理键作为主索引，这样可以保证数据行是顺序写入的。
如果真的没有定义主键，innodb会选择一个唯一的非空索引代替，但是如果没有这样的索引，innodb会隐式定义一个主键来作为聚集索引。
4.回表
回表主要是因为使用了辅助索引，但是因为所需要的数据不在辅助索引中而产生的回表情况。
eg: 使用explain分析select语句，但是里面的Extra为空，这种情况下就是发生了回表，说明数据的查询只查询到辅助索引。
需要回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用二级索引。
比方说
gender
值为
0
的用户记录数量占全部记录数量90%以上，那么如果使用
gender
索引的话，有
90%
多的
id
值需要回表，这不是吃力不讨好么，还不如
直接去扫描聚簇索引（也就是全表扫描）
。
优化器会实现对表中的记录计算一些统计数据，然后根据这个信息判断回表的记录数，
如果回表很多就可能会改为全表扫描
，通常来说回表越少越好。
5.hash索引
哈希索引是一种基于哈希表的索引结构，它是一种需要精确匹配才生效的索引结构。
实现原理：对索引列计算哈希值把记录映射到哈希槽中，然后指向对应记录行的地址。因此，在查询的时候只要正确匹配到索引列，就能在O(1)的时间复杂度内查到记录
相比于B-Tree索引而言，哈希索引有不少的局限性：
- 哈希索引不支持排序
- 哈希索引不支持部分列索引查找
- 哈希索引只支持等值查询，无法提供范围查询功能