一、简介
名称：平衡多路查找树
出现的原因：为了解决 平衡二叉树在存储大量数据时的树过高的问题。
主要使用场景：数据库索引
二、定义与性质
基础1：B树节点的结构
1）叶子结点结构
叶子节点里面什么都没有，但它在逻辑上确实是一个结点。可以把它想象成一个空盒子。
2）非叶结点（即不是叶子结点的结点）结构
指针比
key
（关键字）多一个（多一个指针
0
），因为
key
是夹在指针之间的。
这里的“结点”指的是，它是构成
B
树的基本单元，在图中表示为这个淡黄色的圆角矩形。即
B
树是由多个该结构的结点构成的，这些结点的
n
可能等于任意正整数。它的形状就是下图这样。
基础2：B树的阶
B树中所有节点的孩子结点数（节点的指针数）的最大值称为B树的阶。下图为一棵3阶B树，因为该树的所有结点中，单个节点拥有的孩子结点数（指针数）最多为3
即key“78”和key“88”所在的节点，拥有三个子树（三个指针）。
基础3：终端结点
终端结点是叶子节点的父节点
性质1
在一棵
m
阶B树中，树中单个节点最多有
m
棵子树（即最多有
m-1
个
key
）
解析：这其实和“阶的定义”是对应的。换句话说就是：
m
阶
B
树单个节点最多有
m
个指针。那么那个拥有
m
个指针的结点自然也就有
m-1
个
key
了
。
注意：这里的“最多”（至多），即：子树最多的那个节点，子树数目可以比
m
小。性质
1
限定了
B
树结点内部的最大规模。
性质
2
若根结点不是终端结点，则至少有两棵子树。
解析：该
B
树
若根结点是终端结点
若根结点不是终端结点
但是
性质
3
除根结点之外的所有非叶节点至少有
[m/2]
棵子树。
解析
：即图中绿色圆角矩形中的每个结点都至少要有
[m/2]
（
m
除以
2
，并向上取整）棵子树。
例如：这里是一棵
3阶B树，这里图中绿色圆角矩形中的每个结点都至少有（[m/2]=[3/2]=[1.5]=1.5向上取整=2） 2棵子树。可以看到，这里是符合的。
性质3限定的是B树单个结点的最小规模。（性质1限定的是B树单个结点的最大规模）
性质4
非叶节点的结构
解析：节点上的指针指向的结点的
key
与当前结点的
key
，这些值从左到右是
以从小到大的顺序排列
的。
即：设
p
1v
表示指针
1
指向的结点的最大的
key
；
k1
表示
key1
的值，则有：
p
0v<k1<p1v<k2<p2v<…<kn<pnv
如该例子中的：
12<15<20<22<…<75<80
性质
5
所有的叶子节点都出现在同一层次上，并不带任何信息
解析：图中红色矩形框中的结点均为叶子节点，看得出它们都在最下层，并不带任何信息，因此用
null
表示。
三、常用操作
1.插入
B
树元素的插入
例如给定如下
key【
20,30,50,52,60,68,70
】
创建一个
3
阶
B树。
（性质1要求子树数<=3,性质3要求子树数>=2）
插入20：
Ok
，满足
3
阶
B树的性质，继续插入
插入30：
Ok
，满足
3
阶
B
树的性质，继续插入
插入50：
NO
，
3
阶
B
树最多只能有
3
个子树，这里有了
4
棵子树，违反了“性质
1
”；于是开始进行“结点的分裂”（提出中间位置（
[3/2]=2
）的
key 30
，将其作为独立节点。
Ok
，满足
3
阶
B
树的性质，继续插入
插入52：
Ok
，满足
3
阶
B
树的性质，继续插入
插入60：
No
，不满足
3
阶
B
树的性质
1
，
这里有了
4
棵子树，违反了“性质
1
”；于是开始进行“结点的分裂”
Ok
，满足
3
阶
B
树的性质，继续插入
插入68：
Ok
，满足
3
阶
B
树的性质，继续插入
插入70：
No
，不满足
3
阶
B
树的性质
1
，
这里有了
4
棵子树，违反了“性质
1
”；于是开始进行“结点的分裂”
No
，分裂之后仍然不满足
3
阶
B
树的性质
1
，
这
里根节点有了
4
棵子树，违反了“性质
1
”；
于是继续进行
“结点的分裂”
Ok
，满足
3
阶
B
树的性质，完成插入。
小结：插入操作主要涉及到两个操作，一是节点的分裂：
中间位置（
[3/2]=[1.5]=1.5向上取整=2
）key
的踢出，使其作为独立的结点。结点的合并：被踢出的中间key合并到其父节点，也可以看成是中间key先变成了独立结点，再与其父结点合并。
2.结点的删除
删除的关键：要使得删除后的结点中的key个数>=[m/2]-1，因此将涉及到结点的“合并”问题。可以分为关键字在终端结点上和不在终端结点上两种情况。
情况的划分：
1）关键字在终端结点上
1.1 结点内key数量>[m/2]-1，删除key不会破坏其作为B树的结构，可以直接删除。
1.2 结点内key数量=[m/2]-1，并且其左右兄弟结点中存在key数量>[m/2]-1的结点，则去兄弟结点中借key。
注释：从兄弟结点借
key
“
20”，将
它独立为一个节点，然后按照规则排列涉及到的节点。
1.3 结点内key数量=[m/2]-1，并且其左右兄弟结点中不存在key数量>[m/2]-1的结点，则需要进行结点合并。
2）关键字不在终端结点上
补充定义：
相邻关键字key：对于不在终端结点上的key，它的相邻key是其左子树中值最大的key和其右子树中值最小的key。注意是子树而不是子节点中。
“
20
”的相邻
key
：“
19
”和“
39
”
“
52
”的相邻
key
：“
50
”和“
60
”
需要先转换成在终端结点上，再按照在终端结点上的情况来分别考虑对应的方法。
删除“
52
”
第一
步：待删除
key
与位于终端结点的相邻
key
互换位置
第二步：删除换位之后的待删除
key
