数据库——MySQL必知之B+树索引
MySQL索引
索引（index）是帮助MySQL高效获取数据的数据结构。
以上是MySQL对索引的官方定义，由此可得到索引的本质：索引是数据结构。InnoDB存储引擎支持以下几种常见索引：B+树索引，全文索引、哈希索引，其中比较关键的就是B+树索引。
你知道为啥HashMap不适合做数据库索引？
- hash表只能匹配是否相等，不能实现范围查找
- 当需要按照索引进行order by时，hash值没办法支持排序
- 组合索引可以支持部分索引查询，如(a,b,c)的组合索引，查询中用到了a和b也可以查询的；若使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引
- 当数据量很大时，hash冲突概率也非常大。
B+Tree
B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最常用和最为有效的索引。B+树索引的构造类似于二叉树，根据键值（Key Value）快速找到数据。注意B+树中的B不代表二叉（binary），而代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来的，但是B+树不是二叉树。
在将二叉树之前，我们有必要了解一下二分查找：
二分查找法（binary search）也称为折半查找法，用来查很早一组有序的记录数组中的某一记录。
在以下数据中找到数字48对应的下标
通过3次二分查找，就找到了我们所要的数字，而顺序查找需8次。
对于上面10个数来说，顺序查找平均查找次数为（1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10）/ 10 = 5.5次。
而二分查找法为（4 + 3 + 2 + 4 + 3 + 1 + 4 + 3 + 2 + 3）/ 10 = 2.9次。在最快的情况下，顺序查找的次数为10，而二分查找次数为4。
所以为了索引查找的高效性，我们引入了二分查找树。
二叉树
树（Tree）
N 个节点构成的有限集合。
- 树中有一个称为“根(Root)”的特殊节点
- 其余结点可分为M个互不相交的树，称为原来结点的“子树”
下图都不属于树，原因如下
- 子树是不能相交的
- 除了根结点之外，每个结点有且只有一个父结点
- 一个N个结点的树只有 N - 1 个结点
下图才属于树
关于树的一些术语
- 结点的度：结点的子树个数
- 树的度：树中所有结点中最大的度
- 叶结点：度为0的结点
- 父节点：有子树的结点是其子树的根结点的父结点
- 子结点：若A是B的父节点，B就是A的子结点
- 树的深度：树中所有结点中最大的层次是这棵树的深度
二叉树
二叉树就是度为2的树（也可称为阶）。
树的度就是树中所有结点最大的度。
结点的度：结点的子树个数
子树有左右顺序之分
二叉查找（搜索）树
二叉查找树（Binary Search Tree）是一个二叉树，此外还有以下特点
- 左子树的所有的值小于根结点的值
- 右子树的所有的值大于或等于根结点的值
- 左右子树均满足以上条件
但是二叉查找树，若设计不良，完全会变成一颗极不平衡的二叉查找树
因此若想最大性能地构造一颗二叉查找树，需要这棵二叉查找树是平衡的，从而引出新的定义——平衡二叉树，又称AVL树。
平衡二叉树（AVL树）
平衡树，又称AVL树（Adelson-Velsky and Landis Tree），是一棵二叉排序树，它的左右两个子树的高度差（平衡因子）的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
目的使得树的高度最低，因树查找的效率决定于树的高度。
平衡二叉树的查找性能是比较高的，但维护一棵平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋和右旋得到插入、更新和删除后树的平衡性。
B+ 树
B+树是从平衡二叉查找树演化而来的（但B+树不是二叉树，而是一个多叉查找平衡树）。
借助网页工具：Data Structure Visualization (usfca.edu)
现在我们将其改造成B+树。
树的阶数表示一个节点最多能有多少个子节点。
每个叶子页（LeafPage）存储了实际的数据，如下图中有的叶子页就存放了3条数据，当然可以更多，叶子节点由小到大（有序）串联在一起，叶子页中的数据也是排好序的
从AVL到B+数的变化可知，若节点特点多的话，AVL树的高度远远高于B+树。我们可以归纳B+树的几个特征
- 相同节点数量的情况下，B+树高度远低于平衡二叉树
- 非叶子节点值保存索引信息和下一层节点的指针信息，不保存实际数据记录
- 每个叶子页（LeafPage）存储了实际的数据，比如上图中每个叶子页就存放了3条记录，当然可以更多，叶子节点由小到大（有序）串联在一起，叶子页中的数据也是拍好序的
- 相邻的叶子节点之间用指针相连
注意：叶子节点的数据在物理存储上完全可是无序的，仅仅是逻辑上有序（通过指针串在一起）
当然一棵m阶的B+树完整定义如下
- 每个节点最多有m个元素
- 除了根节点外，每个节点最少有(m/2)个元素
- 若根节点不是叶子节点，那么它最少有2个孩子节点
- 所有叶子节点都在同一层
- 非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放叶子节点中
- 一个有k个孩子节点的非叶子节点有(k - 1)个元素，按升序排列
- 某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它（二叉排序树的特征）
- 相邻的叶子节点之间用指针相连
以上了解即可，一般面试不会问到B+树的细节（B+树的插入、B+树的删除、B+树的旋转等等），除非面试岗位是做数据库实现的
若想详细了解，可找《算法导论》这书
面试问的比较多的也可能是B树（B-树）、B*树，以及为什么选用B+树。
B树与B+树的差别是，B树的非叶子节点也需要存放数据，下图是B树
而B+树的话，数据只存在叶子节点上，同时相邻的叶子节点有链表的结构
同时要注意，MySQL中实现的B+树，叶子节点之间的链表是双向链表，这是一个细微的差别。
另外B*树，与B+树的差别就是非叶子节点之间，也有相互的指针指向。Oracle中用的就是B*树。
那为什么MySQL不用B树而使用B+树呢？
- 因为B树每个节点都存储数据，每次查询的数据大小固定，就会造成每次查询返回的次数的条数变小，相同数据规模情况下B树会增加IO次数，而B+树，则数据量较小，一次可返回多条记录，IO次数较少
- 范围查询B+树明显优于B树
MySQL与B+树
为什么关系型数据库都选择了B+树，这个和磁盘的特性有着非常大的关系。
为了提高效率，要尽量减少磁盘IO。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要读取一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这个称之为预读。
预读的长度一般称为页（page）的整数倍。页是计算管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，这个存储块称为一页。页大小通常4k。
按照磁盘的这种性质，如果是一页存放一个B+树的结点，自然是可以存放很多数据的，如InnoDB引擎中，默认定义的B+树结点大小16KB，这就是说，假如一个key为8字节，那么一个节点可存放约1000个key,意味着B+树可以有1000个分叉。同时InnoDB每次磁盘IO，读取都是16KB的整数倍的树，也就是说InnoDB在节点的读写上是可以充分利用磁盘顺序IO的高速读写特性。
同时按照B+树逻辑结构来说，在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。同一层的非叶子节点也互相串联，形成了一个双向链表。那么在实际读写时，很大概率相邻的节点会放在相邻的页上，又可以充分利用磁盘顺序IO的高速读写特性。
所以我们对MySQL优化的一大方向就是尽可能的多让数据顺序读写，少让数据随机读写。
磁盘顺序读取的效率很高（不需要寻道时间，只需要很少的旋转时间），一般来说，磁盘的顺序读的概率是随机读的40-400倍都有可能，顺序写是随机写的10-100倍。
B+树作用总结
- 磁盘设备上，通过B+树可有效存储数据
- 所有记录都存储在叶子节点上，非叶子（non-leaf）存储索引（keys）信息；而且记录按照索引列的值由小到大排好了序。
- B+树含有非常高的扇出（fanout）,通常超过100，在查找一个记录时，可有效地减少IO操作
扇出：每个索引节点指向每个叶子节点的指针
扇出数：索引节点可存储的最大关键字个数+1
