遇到这种问题，你就要高度集中，保持空杯心态，脑海里要有以下三个问题
为什么添加索引会提高查询速度
索引提高了查询速度对增删改有影响
索引常用的算法原理分析B树和B+树
下面来详细介绍介绍
一句话回答：索引可以将无序内容转换为有序的一个集合（相对），就如同新华字典，如果没有目录，那么查询一个汉字就需要很长时间了。
MySQL 使用的是 Btree 索引，那它是怎么加速检索的呢？
检索中主要耗时在于内存与磁盘的IO耗时，所以加速的关键在于减少IO的次数。
图中是一颗 b 树，每个磁盘块包含几个数据项和指针，
如磁盘块 1 包含数据项 17 和 35，包含指针 P1、P2、P3，
P1指向包含数据项小于17的磁盘块，P2指向数据项在17和35之间的磁盘块，P3 指向数据项大于35的磁盘块。
真实的数据存在于叶子节点，即 3、5、9、10、13、15、28、29、36、60、75、79、90、99。
非叶子节点只不存储真实的数据，只存储指引搜索方向的数据项，如 17、35 并不真实存在于数据表中。
【查找过程】 以查找数据项29为例
首先会把磁盘块 1 由磁盘加载到内存，此时发生一次 IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的 P2指针，相比磁盘的 IO，内存时间非常短可以忽略不计。
通过磁盘块 1的 P2 指针的磁盘地址把磁盘块 3 由磁盘加载到内存，发生第二次 IO，29 在 26 和 30 之间，同理锁定磁盘块 3 的 P2 指针。
通过指针加载磁盘块 8 到内存，发生第三次 IO，同时内存中做二分查找找到了数据项 29，结束查询，总计三次 IO。
真实的情况中，3 层的树可以表示上百万的数据，上百万的数据查找只需要三次 IO，性能提高是巨大的，速度自然很快。相反如果没有索引，那就要遍历所有数据，最差情况下每个数据项都要发生一次 IO，那么总共需要百万次的 IO，速度自然很慢。
索引可以提高查询速度，但是会降低增删改的速度，为什么
任何事情都有有利有弊，在于你自己权衡利弊。
首先来说B+树就是平衡树的一种。
NOTE：平衡树它就是一颗空树或者说它左右两个子树的高度相差的绝对值不会超过1，并且左右两个子树都是一颗平衡二叉树。
如果一棵普通B树在极端情况下是有可能退化成链表的，这样所谓的查询提速也就不存在了
前面我们就说了B+树本身就是平衡树，所以它是不会退化成链表的，树的高度都是比较低的（矮胖墩）【正因为这一点，我们的检索时间复杂度为O】，在上面添加索引会提高查询速度中我们介绍的建立索引，说白了就是建立一个B+树。
B+树是一颗平衡树，如果我们对这棵树增删改的话，那肯定会破坏它的原有结构。
要维持平衡树，就必须做额外的工作。正因为这些额外的工作开销，导致索引会降低增删改的速度
和索引相关的算法：二分查找法、二叉查找树、平衡二叉树、B树、B+树，内容长，但很有用，如果看、请耐心点！
我们在这些数字中用不同算法（1、2、3、5、6、7、9）找出6。
二分查找法原理：先将记录按顺序排列，查找时先按序列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将查询范围缩小为左半部分；如果要找的元素值大于该中点元素，则将查询范围缩小为右半部分。以此类推，直到查到需要的值。
比如我们要找6，用了 3 次就查找到 6 这个数字了。如果是顺序查找，则需要查询 5 次（从第一个数字 1 开始，如果发现不是 6，则继续查找下一个，直到查询到 6）。
我们来对比一下这个例子顺序查找和二分查找法的平均查找次数：
顺序查找：(1 + 2 + 3 + 4 + 5 + 6 + 7)/7 = 4 次
二分查找法：(3 + 2 + 3 + 1 + 3 + 2 + 3)/7 ≈ 2.4 次
显然二分查找法相对顺序查找平均效率更高。
二叉树查找原理：二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值，并且每个节点最多只有两颗子树。
还是找6，这组数字的平均查找次数为：(3 + 2 + 1 + 2 + 3 + 4 + 5)/7 ≈ 2.9 次
试想一下，如果 3 的右子树后面拖更多的数字，那查询效率得多低啊！
此时，平衡二叉树出场了。
平衡二叉树的定义：满足二叉查找树的定义，另外必须满足任何节点的两个子树的高度差最大为 1。
如果要查值为 6 的记录，先找到根（这里是 5 ），这里借用二分查找的思想，因为要找的值 6 大于中点元素 5，所以需要查找的是 5 的右子树，而又因为 6 小于 7，则应该找 7 的左子树，找到 6 这条记录，一共查找了 3 次。如果查找记录使用顺序查找，找到 6 这个值需要查 5 次。
平衡二叉查找树的平均查找次数：(3 * 4 + 2 * 2 + 1) /7 ≈ 2.4 次
计算方式：该平衡二叉查找树中 4 个第三层的值需要查找 3 次，2 个第二层的值需要查找 2 次，第一层也就是根的值只需要查 1 次。
上面我们说了顺序查找需要查找4次，比起来显然平衡二叉查找树的平均查找速度比顺序查找更快。
但是平衡二叉树有个缺点就是，每个节点最多只有两个分支，如果数据量比较大，要经历多层节点才能查询在叶子节点的数据。
如果在平衡二叉树的基础上，每个节点可以有多个分支，那即使在叶子节点的数据，是不是查询效率也比较高呢？这就引出了 B 树结构。
B 树可以理解为一个节点可以拥有多于 2 个子节点的多叉查找树。B 树中同一键值不会出现多次，要么在叶节点，要么在叶的子节点上。
比如用 1、2、3、5、6、7、9 这些数字构建一个 B 树结构，其图形如下：
与平衡二叉树相比，B 树利用多个分支（平衡二叉树只有两个分支）节点，减少获取记录时所经历的节点数。
B 树也是有缺点，因为每个节点都包含 key 值和 data 值，因此如果 data 比较大时，每一页存储的 key 会比较少；当数据比较多时，同样会有：“要经历多层节点才能查询在叶子节点的数据”的问题。这时，B+ 树站了出来。
B+ 树是 B 树的变体，定义基本与 B 树一致
所有叶子节点中包含了全部关键字的信息各叶子节点用指针进行连接非叶子节点上只存储 key 的信息，这样相对 B 树，可以增加每一页中存储 key 的数量。
B 树是纵向扩展，最终变成一个“瘦高个”，而 B+ 树是横向扩展的，最终会变成一个“矮胖子”。
在 B+ 树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上。B+ 树中的 B 不是代表二叉(binary) 而是代表（balance），B+ 树并不是一个二叉树。
B+与B树最大的区别就是：B+树它的键一定会出现在叶子节点上，同时也有可能在非叶子节点中重复出现。而 B 树中同一键值不会出现多次。
到此为止基本mysql查找算法就全部讲完了，下一篇我们主要来看mysql的聚簇索引和非聚簇索引。
原文链接: https://www.yukx.com/bingningm/article/details/1786.html 优科学习网为什么MySQL添加索引后就可以提高查询速度
