码农code之路面试官：你在工作中有遇到SQL查询比较慢的情况吗？
果子：有的。随着业务的发展，表中的数据量会越来越大，查询就会越来越慢
面试官：那你是如何优化查询慢的问题？
果子：在需要查询的列上加索引
面试官：那你知道为什么加索引可以让查询变快吗？
果子：。。。思考中。。。
今天我们就来聊一聊，为什么加了索引查询会变快？
什么是索引？
在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单
假如你现在看一本书，首先肯定会先看书的目录，看看这本书到底有哪些内容，然后通过目录找到自己感兴趣的章节进行阅读
这里的书就相当于数据库中的表，目录就相当于索引，查询表中的数据通过索引可以快速找到对应的数据
索引的数据结构
索引的数据结构是B+树，这里的B指的是balance（平衡），那为啥要用平衡的树呢？我们先来复习一下数据结构和算法
二分查找
二分查找也叫对半查询法，就是每次查找先找中位数，通过中位数就可以过滤掉一半的结果，比如有如下有序数组
3,5,9,12,17,18,27
- 1
现在我们要查找18这个元素，假设我们用顺序查找法需要查询6次才可以完成
用二分查找，先找中位数12，目标18比12要大，往右继续找中位数，第二次中位数就是18，可以看到二分查找只需要2次就可以找到
可以看到二分查找减少了查找次数，大大的提升了查找的效率
有的人可能会说，我查找元素3，顺序查找只需要一次就可以找到，但二分查找需要3次才可以找到
二分查找是一种算法，算法体现的整体上的时间，顺序查找在特殊场景下可能是比二分查找要快一些，但整体上是慢于二分查找的
顺序查找的时间复杂度为O(n)，二分查找的时间复杂度为O(log n)
平衡二叉树
平衡二叉树是基于二分查找提高数据查找速度的二叉树的数据结构，如下图
平衡二叉树的特点：
- 非叶子节点最多拥有两个子节点
- 非叶子节值大于左边子节点、小于右边子节点
- 树的左右两边的层级数相差不会大于1
- 没有值相等重复的节点
保证树的平衡是为了保证查找的速度更快，树的高度越小，查询速度越快，假如树不平衡，如下图
这样树的查找效率就退化成顺序查找，完全失去了树的优势
B树
B树是搜索二叉树的一种拓展，B树 是一种自平衡的树（所有的叶子节点拥有相同的高度）类型的数据结构。但是和其它树比如红黑树，AVL树只有两个子节不同，B树的子节点大于或等于2两个子节点。
B树减少了定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统
B树的特点：
- 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
- 在关键字全集内做一次查找,性能逼近二分查找；
传统的平衡二叉树有很多，而且性能也很高，那为什么还需要B树这类数据结构？
当数据量小的时候，传统的平衡二叉树确实性能很高，而随着数据量越来越大，传统平衡树的高度相对较大，这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理）
空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问
- 1
索引的效率依赖与磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确
B+树
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找，
而MySQL中InnoDB存储引擎的索引就是使用的B+树作为数据结构
B+树的特点：
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
- B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快
B+树区别于B树的最明显特征是：
- B+树只有叶子节点上才存储数据，而B树所有节点上都存储了数据
- B+树所有叶子节点构成了一个有序链表，在查询大小区间的数据时候更方便
为啥不用哈希算法
我们知道哈希的算法复杂度是O(1)，明显要快于B+树，那索引为啥不使用哈希算法，而要使用B+树
在使用等于、in等精确匹配的情况下，哈希确实是要快于B+树
但关系型数据库的操作远远不止这些简单的操作，当需要使用排序、范围查询等操作时，哈希的效率会远远低于B+树
所以说B+树是一种综合了各方面考虑的数据结构
为啥加了索引，查询会变快？
是因为索引使用了B+树数据结构来存储，利用二分查询的原理，有效的减少了磁盘IO的次数，所以查询会变快~~~~
作者：果子爸聊技术 | 来源：http://39sd.cn/FA80E
