MySQL 索引（一）B-/+树

MySQL索引相关知识小结，欢迎交流，指正错误。

0. 前言

MyISAM和InnoDB是MySQL最常用的两个存储引擎，本文将进行详尽的介绍和对比。

本文会图解两种引擎的索引结构区别，然后讲解索引的原理，理解本文内容，就能够理解索引优化的各种原则的背后原因。

B-树、B树和B-tree是同一个数据结构。

MyISAM和InnoDB的索引均采用B+树数据结构，所以接下来先介绍一下B树与B+树。

1. B树和B+树

1.1. B树

B树是一种多路搜索树。

• 定义任意非叶子结点最多只有M个儿子，且M>2。
• 根结点的儿子数为[2, M]。
• 除根结点以外的非叶子结点的儿子数为[M/2, M]。
• 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）。
• 非叶子结点的关键字个数=指向儿子的指针个数-1。
• 非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] <= K[i+1]。
• 非叶子结点的指针：P[1], P[2], …,P[M]（其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树）。
• 所有叶子结点位于同一层。

下图是一个M=4阶的B树。

B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的是叶子结点。

查找文件29的过程：

• 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。（磁盘IO操作1次）
• 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。
• 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。（磁盘IO操作2次）
• 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。
• 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。（磁盘IO操作3次）
• 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。

B树的特性：

• 关键字分布在整颗树的所有节点。
• 任何一个关键字出现且只出现在一个结点中。
• 搜索有可能在非叶子结点结束。
• 其搜索性能等价于在关键字全集内做一次二分查找。

1.2. B+树

下图是一个M=3阶的B+树。

B+树是B树的一种变形树，总结起来，数据库索引的B+树与B树的差异在于：

• 非叶子结点的子树指针与关键字个数相同。
• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i],K[i+1])的子树（注意，区间是前闭后开）。
• 为所有叶子结点增加一个链指针。
• 所有关键字都在叶子结点出现。

B+树的特性：

• 所有关键字都出现在叶子结点的链表中，且链表中的关键字是有序的。
• 搜索只在叶子结点命中。
• 非叶子结点相当于是叶子结点的索引，叶子结点是存储关键字数据的数据层。

1.3. B-/+树做索引的原因

解释这个问题之前，需要了解一些基础知识。

局部性原理与磁盘预读 由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用——程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B-/+树做索引的原因分析 一般来说，磁盘I/O次数可以用于评价索引结构的优劣。在B-Tree中查找，可知检索一次最多需要访问h个节点（上文举例查找文件29的过程）。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

为了达到这个目的，在实际实现中，B树还使用如下技巧：

• 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。
• B树中一次检索最多需要h-1次I/O（根节点常驻内存）。一般实际应用中，出度d（树的分叉数）是非常大的数字，通常超过100；h非常小，通常不超过3。

综上所述，用B树作为索引结构效率是非常高的。

红黑树或者平衡二叉树的其他树结构

• h明显要深的多，执行效率低。
• 逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，
• 每个节点存储的数据量太小了，对磁盘空间造成浪费，带来频繁的IO操作。

所以其他树结构的效率明显比B树差很多。

相对B树，B+树做索引的优势

• B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
• B+树的查询效率更加稳定：由于所有数据都存于叶子节点。所有关键字查询的路径长度相同，每一个数据的查询效率相当。
• B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。

笔者认为第三条原因才是MySQL使用B+树而不是B树做索引的主要原因，毕竟MongoDB的索引是B树，所以两种数据结构并没有绝对的好坏，要看实际的业务需求。

文章源于：一文彻底搞懂MySQL索引