sql进阶：索引类型的选择和索引原理，为什么会失效?

昨天看了半天的索引，也说了半天的失效情况，其实大多数都是在索引方法是b+tree的前提下的建立的。
不过索引方法又不一定是B+tree。所以这里简单的也说一下别的索引方法和其实现。我们要想知道为什么失效，首先要知道它是怎么做的，怎么生效的！（涉及到的一些算法，术语什么的，有些是我查阅的资料结合自己的理解，如果说的不准确或者有误请指出）

从二叉树说起

二叉树
二叉查找树（也叫二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树（每个结点最多有两个子树的树结构。）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
下面是关于二叉排序树的百度百科的定义:

二叉排序树定义
个人感觉二叉树还算是好理解，每个节点最多两个子节点，左小右大。一个新数据的插入放在哪里从根节点开始比较。
简单二叉树
这个时候如果15插入进来了，就会跟根节点也就是10比较，一看大于10.往右，跟12比较，再一看大于12，往右跟13比较，还是大于13，跟14比较，最后还大于14.并且没有可比较的了，就放在14的右下面。
新元素的插入
查找的时候其实也是同样的，比如想查找几。从根节点开始左右比较，最后比对成功就是找到了。比对到没有节点就是没有。但是看我的图（虽然贼丑）大家就能发现问题，如果连续插入递增的数，那么这个二叉树会在一条分支上一直进行延伸，这样基本就由二叉搜索树变成了线性表，搜索效率就会大大下降。
平衡二叉树
就是普通的二叉树，是固定根节点，然后新数据只是插入没有别的操作。但是平衡二叉树是尽量保证左右平衡的一种二叉树。比如上图，就不平衡，右边一直加元素，左边很萎靡。因为根节点是10，而是随着数据越来越大，左边不会变，右边越来越长。解决这种办法的方法就是根节点随着数据的插入而变换。类似于上图如果根节点是12.就会平衡了。左右数据层级啥的都差不多了。！！！！重点我这里只是打个比方，真正的平衡二叉树的旋转算法不是这么简单的，但是肯定是要每插入数据都会引起树的旋转，这样就会消耗特别大的性能。
最主要的是一个节点只能存储一个值，数据量太大的时候就会一颗高度特别高的二叉树，这样搜索效率就会出现大幅下降。所以索引不用二叉树实现。

接下来说说B+树

先来看看百度百科对B树的定义：

B树定义

反正我直接看是没看懂，也可能是我没什么数学基础吧，然后开始找资料，教程啥的，最后总结一些不是这么全面，但是容易理解的定义:
我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。(这个M是我们自己指定的。)
一颗m阶的B树定义如下：

1. 每个结点最多有m-1个关键字。

2. 根结点最少可以只有1个关键字。

3. 非根结点至少有(m/2)-1个关键字(这里无条件向上取整，比如说结果是2.2，则取3)。

4. 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。（还是左小右大原则）

5. 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

下面是一个三阶B树:

三阶B树（图片网上资源）

以上图为例：若查询的数值为9：
　　第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树；
　　第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８大，比12小，下子树；
　　第三次磁盘ＩＯ：在内存中定位（与9、10比较），找到9，终止。
整个过程中，我们可以看出：比较的次数并不比二叉查找树少，但是磁盘IO的次数却是大大减少。
比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

B+树

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。
B+树与B树最大的不同就是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

B+树定义

下面是一个B+树作为索引的结构图：

B+树结构图
其实我个人看。除了最后一层叶子节点，上面的和B树很相似。但是也就是因为最后一层的叶子节点，更加方便我们查找。
如上图：如果我们要查询50这个节点，那么只需要在第一节点中进行查找，发现50在45和67之间，然后就走第二个节点，走到了（45,48,63）这个节点，然后发现46在48-63之间，走第二个节点，遍历，就找到了50。看似和B树的查找差不多，但是其实是有区别的。

1. b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
2. b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
3. 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。

所以我们数据库使用B+树作为索引而不是B树或者二叉树。

Hash索引

这个也是数据库索引的一种实现方式。其实这个可说行不太高。
Hash索引是指，将要创建索引的字段值进行hash，按照hash值为key，数据地址为value，保存成为一个HashMap结构，如果一个hash值对应多个行数据，就进行链表存储。

hash实现索引（红色那两个是hash值相同）

实现原理就不说了，说一下用Hash实现索引的优缺点：

1. 使用hash只需要进行一次hash就可以查找到值，不需要进行像二叉树一样的逐层查找，效率高。(优点)
2. 由于数据是进行hash之后进行保存的，所以原数据在里面是没有顺序的，所以仅仅能满足 “=” 、“IN”这样的操作，不能使用范围查询 。（大缺点）
3. 无法被用来数据的排序操作，因为不像B+树，B+树的存储是有顺序的，是按照索引值进行排序的，但是hash索引是hash后的数据，所以无法用来排序。
4. 不能利用部分索引键查询，在B+树中，多个字段的索引是通过按照字段一次排序进行存储的，所以如果创建了(A,B,C)三个字段的联合索引，那么可以使用部分索引例如A，(A,B)，但是hash的联合索引是所有字段一起进行hash的结果去映射的，所以部分字段无法使用。（联合索引只能联合使用）
5. 遇到大量hash值相等的情况后，也就是出现大量的hash碰撞后，链表就会非常长，变成线性结构，查询效率并不一定会比B+-Tree高。

谈一谈怎么选择索引？

其实上面主要讲的就是B+树和Hash索引的实现方式，由此，我们也能得到一些结论：
指定查询首选Hash索引。B+树的查询都是要经过多次范围比对，最后才能定位到想要查询的值，而hash不是，只要一次就可以查找到想要的值，所以例如id，姓名这种，Hash索引是比较合适的。
模糊查询Hash无用。这个很好理解啊，因为hash算法是基于等值计算的，所以对于“like”等范围查找hash索引会无效。
范围查询Hash无用。额，跟like差不多，没啥说的。B+树的叶节点以链表形式存储，所以支持范围查询。但是in这种，如果in里只有几个数字，也不算范围查询。
Hash索引不支持排序。这个其实上文也说了，原因就是hash索引是hash后的数据。没有顺序的。而B+树左到右递增，有顺序。
Hash索引不支持最左前缀匹配。这个其实也很好理解，根据他的存储方式，联合索引是将所有的索引值一起去计算hash值的，所以拆开了无法使用。但是咱们可以想想，如果联合索引，并且所有字段都用到了，肯定Hash索引要比B+树快很多。因为hash只要计算一次，而B+树一层层查找。

大概就总结到这里，好像除了第一条剩下的都是对Hash索引的限制，但是呢！！！这不是说明hash索引就不如B+树好了。因为我们要结合具体的环境，就好像我刚刚说的id查找，反正目前我是没使用过id<XX的条件查询，因为id肯定是定值查询的，还有名字（这个偶尔有时候会模糊查询），但是大部分还是指定名字查询！最后一个最最最常见的业务：
登录功能，我们做登录验证，账号肯定是定值查询的！这个查询我们经常用到，如果给账户这个字段加索引，肯定是hash索引比B+树索引的效率高的。
但是像是时间之类的经常用来做范围查询的字段，那就是B+tree了。
其实哪有什么好坏，存在即合理。记得群里看到过一句话:脱离了实际业务需求的设计都是耍流氓。
这篇文章写了很久，中间大量的查阅资料，看数据结构算法（B树和B+树那块都要自闭了，尤其是到现在做B树旋转测试还要靠运气才能蒙对），中间很多很深刻的概念我这里也都是一笔带过甚至直接不说了。我这里只是一些表层的实现和简单的例子，中间如果有说的不严谨或者说错了的地方欢迎指出。
今天就到这里了。争取每天学习一点点，不知道多久会发生质变。然后大家共勉，祝大家工作生活顺顺利利的吧！还要周末愉快！
全文手打不易，如果你觉得有帮到你或者有点用，别吝啬的点个喜欢和点个关注哦~~