2022-WangDao-CS-DS-Notes/7.6B+树.md

## B+树——B-Plus-Tree

### 一、B树的定义

`B+树`，又名`多级分块查找`。

数据库索引技术里大量使用者B树和B+树的数据结构.

B+树是由`分块查找`升级为`查找树`

B树任何一层都可以找到，因为每一层都是数据
而B+树除叶子结点外，其余都是分类，只有最底层才会指向数据，必须找到最底层才能知道是否成功。

B+树有两种查找方式：①分块查找：从根结点查 ②顺序查找：从P开始横着查。

![uTools_1638279630033](https://github.com/oxyanyano/2022-WangDao-CS-DS-Notes/blob/main/images/uTools_1638279630033.png)

![uTools_1638279791118](https://github.com/oxyanyano/2022-WangDao-CS-DS-Notes/blob/main/images/uTools_1638279791118.png)

### 二、B+树的实现

无

### 三、查找效率分析

与B树一样

### 四、B+树的插入

![B Plus tree](https://images0.cnblogs.com/blog/94031/201403/290050048129679.png)

![img](https://files.cnblogs.com/yangecnu/Bplustreebuild.gif)

### 五、B+树的删除

与B树一样

### 六、B树与B+树的对比

![1638280509471](https://github.com/oxyanyano/2022-WangDao-CS-DS-Notes/blob/main/images/1638280509471.jpg)