2.1 索引算法
在介绍MySQL的索引之前，下面先介绍常见的索引算法。
2.1.1 顺序查找
如果要在一组数据中找到对应的记录，通常是一个一个地扫描，直到找到对应的记录。
例如，如果要从1、2、3、5、6、7、9这组数字中找到6，那么需要查询5次（从数字1开始，一个一个地对比，如果不是6，那么继续对比下一个，直到找到6为止）。
对于上面一组数字，可以计算出顺序查找的平均查找次数：
（1+2+3+4+5+6+7）/7=4（次）
2.1.2 二分查找
二分查找是将记录顺序排列，查找时先将序列的中间元素作为比较对象。如果要找的元素的值小于该中间元素的值，那么只需要在前一半元素中继续查找；如果要找的元素的值等于该中间元素的值，则匹配成功，查询完成；如果要找的元素的值大于该中间元素的值，那么只需要在后一半元素中继续查找。
以此类推，直到查询到对应的元素为止。
例如，要从1、2、3、5、6、7、9这组数字中找到6，首先找到中间元素5，因为6大于5，所以在5的右边的数字中（6、7、9）进行下一次查找，中间元素为7，因为6小于7，所以继续查找6、7、9中7左边的数字，此时就会找到目标元素6。二分查找的具体过程如图2-1所示。
图2-1 二分查找的具体过程
对于上面一组数字，可以计算出二分查找的平均查找次数：
（3+2+3+1+3+2+3）/7≈2.4（次）
显然，二分查找的效率优于顺序查找的效率。
2.1.3 二叉查找树
二叉查找树是将一组无序的数据构造成一棵有序的树，其设计思想与二分查找的设计思想类似。二叉查找树有如下几个重要的特性。
● 每个节点最多有两个子节点。
● 每个节点都大于自己的左子节点。
● 每个节点都小于自己的右子节点。
下面以1、2、3、5、6、7、9这组数字举例。假设这组数字构造的二叉查找树如图2-2所示。
图2-2 二叉查找树
在图2-2中，3为根节点，1和2这一部分为根节点的左子树，5、6、7、9这一部分为根节点的右子树，整棵树的高度为5。
如果这组数字采用的是图2-2中这种二叉查找树的结构，那么平均查找次数为
（3+2+1+2+3+4+5）/7≈2.9（次）
试想一下，如果3的右子树的后面有更多的数字，那么查询效率会更低。
所以，如果想让二叉查找树的性能最好，那么这棵树的高度应尽可能低，这时可以考虑平衡二叉树。
2.1.4 平衡二叉树
平衡二叉树是二叉查找树的改进版，除了要满足二叉查找树的定义，还必须满足任意节点的平衡因子（两棵子树的高度差）的绝对值最大为1。
仍然以1、2、3、5、6、7、9这组数字举例。这组数字构造的平衡二叉树可能如图2-3所示。
图2-3 平衡二叉树
如果这组数字采用的是图2-3中的这种平衡二叉树，那么这组数字的平均查找次数为
（3×4+2×2+1）/7≈2.4（次）
在该平衡二叉查找树中，第3层有4个数字，每个数字需要查找3次；第2层有2个数字，每个数字需要查找2次；第1层就是根节点，只需要查找1次。
2.1.5 B树
B树可以理解为平衡二叉树的拓展，也是一棵平衡树，但是是多叉的。也可以把B树看成1个节点可以拥有多于2个子节点的多叉查找树。
B树具有如下几个特点。
● 每个节点都存储了真实的数据。
● B树的查询效率与键在B树中的位置有关，最大时间复杂度与B+树的相同（数据在叶子节点上），最小时间复杂度为1（数据在根节点上）。
下面以1、2、3、5、7、8、10、11、13、15、16、17、18、20这组数字举例。它们构造的B树大致如图2-4所示。
图2-4 B树
2.1.6 B+树
B+树是B树的变体，其定义与B树的定义基本一致。与B树相比，B+树的不同点包括以下几点。
● B+树的键都出现在叶子节点上，可能在内节点上重复出现。
● B+树的内节点存储的都是键值，键值对应的具体数字都存储在叶子节点上。
● B+树比B树占的空间更多，因为B+树的叶子节点包含所有数据，而B树是整棵树包含所有数据。多出的部分就是B+树的内节点，但是B+树的内节点具有索引的作用，因此，B+树的查询效率比B树的查询效率更高。
继续以1、2、3、5、7、8、10、11、13、15、16、17、18、20这组数字举例。它们构造的B+树大致如图2-5所示。
图2-5 B+树
2.1.7 B+树索引
上面介绍了与索引相关的一些算法，这是为了引出B+树索引。
B+树索引就是基于B+树发展而来的，通常在InnoDB上对某个字段添加索引，就是对这个字段构建一棵 B+树。当查询条件是该索引字段时，查询速度非常快，对比逐行扫描，效率明显高很多。