关于mysql:Mysql-B树索引

二分查找法（binary search）也成为折半查找法。用来查找一组有序的记录组中的某一记录。

根本思维是：将记录按有序化（递增或递加）排列，在查找过程中采纳跳跃式办法查找，即先以有序数列的中点地位为比拟对象，如果要找的元素值小于该中点元素，则将待查问列放大为左半局部，否则为右半局部。通过一次比拟，将查问区间放大一半。

如有 5,10,19,21,31,37,42,48,50,52 这 10 个数，要查 48 这个数，其查找过程：

从图看，用了 3 次就找到了 48 这个数。如果是程序查找，则须要 8 次，因而二分查找法的效率比程序查找法要好（均匀）。然而如果要查 5 这个数，程序查只需 1 次，而二分查找须要 4 次。

对于下面的 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

B+ 树是通过二叉查找树，再由均衡二叉树，B 树演变而来。

二叉查找树中定义：左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。因而能够通过中序遍历失去键值的排序输入

若想最大性能的结构一颗二叉查找树，须要这颗二叉查找树是均衡，从而引出了新的定义 —– 均衡二叉树，或称为 AVL 树。

均衡二叉树定义 ： 首先复合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为 1.

均衡二叉树的查问速度很快，然而保护一颗均衡二叉树的代价很大，通常来说，须要 1 次或屡次左旋和右旋来失去插入或更新后树的平衡性。如下所示：

B+ 树和二叉树、均衡二叉树一样都是经典的数据结构。

B+ 树由 B 树和索引程序拜访办法（ISAM，这就是 MyISAM 引擎最后参考的数据结构）演变而来，理论中曾经没有应用 B 树的状况了。

B+ 树是为磁盘或其余间接存储辅助设备设计的一种均衡查找时。

B+ 树中，所有记录节点都是按键值的大小程序寄存在同一层的叶子节点上，由各叶子节点指针进行连贯。

如下：其高度为 2，每页寄存 4 条记录，扇出（fan out）为 5。所有记录都在叶子节点上，并且是程序寄存的。

B+ 树的插入 必须保障插入后叶子节点中的记录仍然排序，同时须要思考插入到 B + 树的三种状况，每种状况都会导致不同的插入算法。如下所示：

1、如下图这颗 B + 树，若用户插入 28 这个值，发现以后叶子页 leafPage 和 IndexPage 索引页都没有满，直接插入就行。

图（1）

图（2）

2、从上图接着插入 70 这个键值，这时原来的 leafPage 曾经满了，然而 IndexPage 还没有。这时插入 leafPage 后的状况为 50、55、60、65、70，并依据两头值 60 来拆分叶子节点，可得下图。

图（3）

为了保持平衡对于新插入的键值可能须要做大量的拆分页（split）操作。因为 B + 树结构次要用于磁盘，也拆分意味着磁盘操作，所以应该在可能的状况下尽量减小页的拆分操作。因而 B + 树会提出均衡二叉树的旋转（Rotation）性能。

旋转产生在 leafPage 已满，然而其左右兄弟节点没有满的状况下。这时 B + 树不会急于去拆分页操作，而是将记录移到所在页的兄弟页节点上，通常状况下，左兄弟会被首先查看用来做旋转操作。若如此，插入 70 应该左旋为：

图（4）

3、最初插入 95，这时复合第三种状况，即 leafPage 和 IndexPage 都满了，这时须要做两次拆分

图（5）

B+ 树应用填充因子（fill factor）来管制树的删除变动，50% 是填充因子可设的最小值。

B+ 树的删除操作同样必须保障删除后叶子节点中的记录仍然排序，同插入一样，B+ 树删除操作同样须要思考以下三种状况：

1、依据图（5）的 B + 树来进行删除。首先删除键值为 70 的记录：

接着删除键值为 25 的记录，然而该值还是 IndexPage 中的值，因而在删除 LeafPage 中的 25 后，还应将 25 的右兄弟节点 28 更新到 PageIndex 中，如图：

最初删除 60 这个键值。删除 LeafPage 中键值为 60 的记录后，Fill Factor 小于 50%，这时须要做合并操作，同样，在删除 IndexPage 中相干记录后须要做 IndexPage 的合并操作。

B+ 树索引构造解析