带着问题来探究通常会获得较好的成果,所以思考以下问题:

1. 为什么哈希表、完全平衡二叉树、B树、B+树都可以优化查询，为何Mysql独独喜欢B+树？
2. 谈到了Hash,那如何解决Hash冲突?

先了解下Hash:

Hash的特点是精确查询,因为根据Hash算法可以获取到一个坐标,这个值是固定的,对于范围查询就不支持了,所以SQL中的查询语句,如果是等于的查询,可以很快索引到,如果是>或者<的查询,则不会很快，而是要进行范围查询(即需要扫描表),所以Hash在范围查询这种场景下就不太合适了,需要其他算法来优化查询.

重点: Hash 适合等值查询的场景,只有KV的情况, 例如Redis、Memcached这些NoSql的中间件

上面谈到的Hash是无序的Hash表,那是否有有序的数据结构呢? 

这个就要谈到有序数组了,有序数组在等值及范围查询都很好。但是有序就以为这新增、删除、修改的成本很大,因为上述的操作要经历 有序——>无序(add,delete,update造成的)——>(重新恢复到)有序,所以比较耗费能量,是有成本的。故,有序数组特别适合做静态的存储引擎,例如历史的数据,比如购物记录等等

二叉树:

二叉树是有序的,所以支持范围查询.   但是他的时间复杂度是O(log(N))，为了维持这个时间复杂度，更新的时间复杂度也得是O(log(N))，那就得保持这棵树是完全平衡二叉树了。但是完全平衡二叉树也不能说适合做索引,因为随着数据量的增多,不论是什么树,维护的树高度都会越来越多，如果硬盘不是很好,则一次查询的耗时会很长

B树:

B树的索引一个节点可以存储多个元素,所以明显的比二叉树矮很多,既然矮很多,就减少了查询的时间

B+树:

B+数首先是比B数宽的(或者说胖),因为它们吧非叶子节点在叶子节点中冗余了一份,然后叶子节点之间使用指针(内存地址)链接,冗余带来的好处是 提高了范围查找的效率(因为指针指向了下一个节点的叶子节点~)

所以MySQL喜欢B+树,可以提高索引时的磁盘IO效率,可提高范围查询的效率("矮"),并且B+树种的元素也是有序的

MySQL的基本存储结构是页(我们平时的记录都存储在页中)

页于页之间是双向列表,页中的记录是单向链表

每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。如果使用非主键作为搜索条件进行查询,则只能从最小的记录开始一次遍历(因为页中的记录是单向链表)

回表:回表就是回到主键索引树的搜索过程,比如你使用age来查,通过age查到主键为2,再用主键2来查出记录。

如果想避免回表可以使用覆盖索引,所谓覆盖索引就是我们要查询的值就在索引里面,比如给age字段建立索引,我们用age作为条件,就很快,因为是直接查索引的

索引的最左匹配原则是什么?

MySQL会一直向右匹配直到遇到范围查询 （>,<,BETWEEN,LIKE）就停止匹配。

例如: 如有索引 (a,b,c,d)，查询条件 a=1 and b=2 and c>3 and d=4，则会在每个节点依次命中a、b、c，无法命中d。(c已经是范围查询了，d肯定是排不了序了)

所以,列的排序决定了可命中索引的列数

其他

• 索引可以简单如一个列 (a)，也可以复杂如多个列 (a,b,c,d)，即联合索引。
• 如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询 (>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。

总结

• 最左前缀匹配原则。这是非常重要、非常重要、非常重要（重要的事情说三遍）的原则，MySQL会一直向右匹配直到遇到范围查询 （>,<,BETWEEN,LIKE）就停止匹配。
• 尽量选择区分度高的列作为索引，区分度的公式是 COUNT(DISTINCT col)/COUNT(*)。表示字段不重复的比率，比率越大我们扫描的记录数就越少。
• 索引列不能参与计算，尽量保持列“干净”。比如， FROM_UNIXTIME(create_time)='2016-06-06' 就不能使用索引，原因很简单，B+树中存储的都是数据表中的字段值，但是进行检索时，需要把所有元素都应用函数才能比较，显然这样的代价太大。所以语句要写成 ： create_time=UNIX_TIMESTAMP('2016-06-06')。
• 尽可能的扩展索引，不要新建立索引。比如表中已经有了a的索引，现在要加（a,b）的索引，那么只需要修改原来的索引即可。
• 单个多列组合索引和多个单列索引的检索查询效果不同，因为在执行SQL时，MySQL只能使用一个索引，会从多个单列索引中选择一个限制最为严格的索引(经指正，在MySQL5.0以后的版本中，有“合并索引”的策略，翻看了《高性能MySQL 第三版》，书作者认为：还是应该建立起比较好的索引，而不应该依赖于“合并索引”这么一个策略)。
• “合并索引”策略简单来讲，就是使用多个单列索引，然后将这些结果用“union或者and”来合并起来

最后,那如何解决hash冲突呢?

Hash不用想的太复杂,就是 == 等于号,用来定位的

因为一个地址不能存放多个hash值,如果一个地址出现了多个hash值就是冲突,解决方法有:

1.开放定址法：
   既然当前位置容不下冲突的元素了，那就再找一个空的位置存储 Hash 冲突的值（当前 index 冲突了，那么将冲突的元素放在 index+1)。

2.再散列法：
   换一个 Hash 算法再计算一个 hash 值，如果不冲突了就存储值（例如第一个算法是名字的首字母的 Hash 值，如果冲突了，计算名字的第二个字母的 Hash 值，如果冲突解决了则将值放入数组中）。

3.链地址法：
   每个数组中都存有一个单链表，发生 Hash 冲突时，只是将冲突的 value 当作新节点插入到链表（HashMap 解决冲突的办法）。

4.公共溢出区法：
  将冲突的 value 都存到另外一个顺序表中，查找时如果当前表没有对应值，则去溢出区进行顺序查找。