B+树索引结构解析

我不是女神ヾ 2021-12-09 01:04 218阅读 0赞

## 一、二分查找法 ##

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

基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式方法查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查询列缩小为左半部分，否则为右半部分。通过一次比较，将查询区间缩小一半。

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

![1007094-20190714212112865-1505892471.png][]

从图看，用了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次或多次左旋和右旋来得到插入或更新后树的平衡性。如下所示：**

**　　![1007094-20190714213820319-2142522129.png][]**

## 三、B+树 ##

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

B+树由B树和索引顺序访问方法（ISAM，这就是MyISAM引擎最初参考的数据结构）演化而来，实际中已经没有使用B树的情况了。

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

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

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

![1007094-20190714214607088-2001103733.png][]

## 四、B+树的插入操作 ##

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

![1007094-20190715183222522-74104570.png][]

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

![1007094-20190715183410648-1481295178.png][]

图（1）

![1007094-20190715183321918-762706256.png][]

图（2）

2、从上图接着插入70这个键值，这时原来的leafPage已经满了，但是IndexPage还没有。这时插入leafPage后的情况为50、55、60、65、70，**并根据中间值60来拆分叶子节点，**可得下图。

![1007094-20190715183840768-739369271.png][]

图（3）

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

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

![1007094-20190715185137260-1416232269.png][]

图（4）

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

![1007094-20190715185201919-774153102.png][]

图（5）

## 五、B+树的删除操作 ##

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

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

![1007094-20190715185531259-2115301571.png][]

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

![1007094-20190715185933863-978982346.png][]

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

![1007094-20190715190317126-751944863.png][]

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

![1007094-20190715190658067-69285584.png][]

[1007094-20190714212112865-1505892471.png]: /images/20211209/93a18b197d234a80b113a8671c90be89.png
[1007094-20190714213820319-2142522129.png]: /images/20211209/bc260464417546cb9d013af84927f80d.png
[1007094-20190714214607088-2001103733.png]: /images/20211209/b65cfd2d8abe4a92a5b8ac14e4131d45.png
[1007094-20190715183222522-74104570.png]: /images/20211209/0be50254d42e474caadb60125cbd177c.png
[1007094-20190715183410648-1481295178.png]: /images/20211209/10f55d5f8b2f492f94a4372c21ea1294.png
[1007094-20190715183321918-762706256.png]: /images/20211209/d00b4564e64a4c468b214acfe7dad9a3.png
[1007094-20190715183840768-739369271.png]: /images/20211209/e89ca548e6824523af6e0e3d4b7751a3.png
[1007094-20190715185137260-1416232269.png]: /images/20211209/1eb2699bcf904ea5a993ef1cd8f4d67e.png
[1007094-20190715185201919-774153102.png]: /images/20211209/d9d52f305367471588628078f9ef2b06.png
[1007094-20190715185531259-2115301571.png]: /images/20211209/591130fa778a481fa92cdd928cbe2804.png
[1007094-20190715185933863-978982346.png]: /images/20211209/f56e8da21b8c4e51bf88bb7008dda829.png
[1007094-20190715190317126-751944863.png]: /images/20211209/439aec3cca634742b7142da9453f210c.png
[1007094-20190715190658067-69285584.png]: /images/20211209/6ece98d2546e4d2991f589039142e465.png