数据结构-B树、B+树

1.一颗五阶的B树（5叉查找树）

叶子节点都为空

B树，又称多路平衡查找树（多路：m叉查找树中，规定除了根节点外，任何节点至少有  [m/2]  (向上取整)个分叉，至少含有[m/2]-1 个关键字  平衡：m叉查找树中，规定对于任何一个节点，其所有子树的高度都要相同），B树中所有节点的孩子个数的最大值称为B树的阶（也就是说有几个分叉），通常用m表示。一颗 m阶B树、空树、m叉树查找树有如下特性

  * 树中每个节点至多有m棵子树，即至多含有m-1个关键字

  * 若根节点不是终端节点，则至少有两颗子树（平衡原则）

  * 除根节点外的所有非叶子节点至少有[m/2] 棵子树，即至少含有 [m/2]-1 个关键字。

  * 所有的叶节点都出现在同一层次上，并且不带信息（可以视为外部节点，实际上这些节点是不存在的，指向这些节点的指针为空）

  * 

 2.B树的插入与删除

 视频链接：

https://www.bilibili.com/video/BV1b7411N798?p=73&vd_source=2c8d3b8b4e9d03424a43fa463ee9dc24

3.B+树的基本概念

一棵m阶的B+树需满足下列条件：

1）每个分支结点最多有m棵子树（孩子结点）

2）非叶根节点至少有两棵子树，其他每个分支结点至少有 [m/2](向上取整) 棵子树。

3）结点的子树个数与关键字个数相等。

4）所有叶结点包含全部关键字及指向对应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序互联链接起来。

5）所有分支结点（可视为索引的索引）中仅仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向子结点的指针。

数据结构(54) B树、B+树__李白_的博客-CSDN博客_b+树和b树高度

MySQL面试题——数据库为什么使用B+树而不是B树_Find Our Way的博客-CSDN博客_为什么用b+树而不用b树

深入理解MySql为何使用B+树而不是B树_爱xiao的程序猿的博客-CSDN博客_mysql为什么用b+树不用b树