MySQL中一些关于索引的知识点 _MySQL

什么是索引
索引是一种数据结构，其作用就是用来提高数据查询效率。比较常用的比喻就是将其类比为书籍的目录。通过目录可以精确的找到某一章节的内容所在页。
在数据量较小的时候使用索引其实也没有什么意义，即使没有索引需要一条一条遍历数据对于计算机来说也并不需要太多时间。而一旦数据量较大，要保证我们能正常的对外提供服务，保证用户使用体验那么索引就是必要的了。
索引类型
索引时一种数据结构，为了应对不同的场景会有多种实现。在MySQL中主要就是Hash索引和B+Tree 。
Hash索引
hash相信大家应该都很熟悉，hash是一种key-value形式的数据结构。实现一般是数组+链表的结构，通过hash函数计算出key在数组中的位置，然后如果出现hash冲突就通过链表来解决(拉链法) 。当然还有其他的解决hash冲突的方法。hash这种数据结构是很常用的，比如我们系统使用HashMap来构建热点数据缓存，存取效率很好。
hash结构存数据首先通过计算key的hash值来确定其在数组中的位置，如果有冲突就在该数组位置建一个链表。这样很明显有几个问题：

即使是具有相同特征的key计算出来的位置可能相隔很远，连续查询效率低下。即不支持范围查询
hash索引存储的事计算得到的hash值和行指针，而不存储具体的行值，所以通过hash索引查询数据需要进行两次查询(首先查询行的位置，然后找到具体的数据)
hash索引查询数据的前提就是计算hash值，也就是要求key为一个能准确指向一条数据的key，所以对于like等一类的匹配查询是不支持的。

所以我们可以知道的是hash索引适用于快速选取某一行的数据。
B+Tree结构
从名字上看这明显是一种树结构，在大学期间数据结构的课本上树结构是必讲的。树结构是一种特别重要的数据结构，在很多地方都会使用到。
上面我们说到hash索引无法进行范围查询，在树结构中也有一种方便进行有序查询的结构--二叉搜索树。二叉搜索树的结构中要求父节点的值大于左孩子节点并且小于右孩子节点，如下图。

文章插图

上图中二叉树的查询的时间复杂度为O(log(n))，当然要保证O(log(n))的时间复杂度就需要保证二叉树时刻保持平衡。
而在MySQL索引中虽然也使用了树结构，但是并不是使用的二叉树。因为在数据库中数据最终都是存放在磁盘上的，而如果树的节点过多的话，那么在节点之间转移会花费较多的时间。在MySQL的实现中选择将更多内容放在同一个节点，对同一个节点的操作转入在内存中完成，减少在外存中节点之间转移的次数，以达到提高效率的目的。这就是B+Tree，在B+Tree的实现中一个三层的树结构就基本上可以满足我们几乎所有的需求了。
B-Tree
【MySQL中一些关于索引的知识点】要了解B+Tree首先就得了解B-Tree，B-Tree是一种平衡树，这里的B指的是Balance而不是Binary，更确切的说B-Tree是一种多路平衡搜索树。
多路平衡搜索树如下图：

文章插图

这是一种2-3树，意思就是每个节点存有两个值，同时每个节点分支数为3，从上图中可以看出来着中结构很适合查询数据。每个节点的左子树的值都是小于当前节点中最小的值，中间的子树的值全都是在当前节点两个值的中间，而右子树的值全都大于当前节点的最大值。
比如我们要查找24这个值：

首先从根节点判断24在根节点(15,25)之间，所以左右子树排除，从中间查找。
然后找到中间子树的根节点(18,22)，比较发现24大于该节点最大值，排除左子树和中间子树。
找到右子树，判断节点大值刚好等于24，查询结束

基于上面的流程可以总结B树的搜索：

从根结点开始，对结点内的关键字（有序）序列进行二分查找。
如果命中则结束，否则进入查询关键字所属范围的子结点；
重复上面的流程，直到所对应的子节点为空，或已经是叶子结点；

可以看出其搜索性能相当于在关键字集合内做一次二分查找。从这里看来好像B-Tree没有什么问题，但是需要注意到的是在B-Tree中每一个节点都是存储索引关键字以及其代表的具体行数据。而在MySQL中数据库加载数据是以页为单位加载，每一页的大小是固定的(默认16k) 。如果每一个节点都存储所有的值，那么一页中能存下的节点就会很少，一次查询可能就会进行多次从内存中去加载数据，导致性能降低。