B树和B+树

B树

• B树，多路平衡查找树
• B树中所有结点的孩子个数的最大值称为B树的阶，用m表示

性质

一棵m阶B树或为空树，或为满足如下特性的m叉树

1. 每个结点最多m个子树，即最多m-1个关键字（注意结点和关键字的区别，一个结点可以有多个关键字）
2. 根结点不是终端结点，则至少两个子树
3. 非叶结点至少有⌈m/2⌉个子树，即至少⌈m/2⌉-1个关键字（除根结点）（向上取整）
4. 关键字的大小关系与二叉排序树类似
5. 叶结点都在同一层，并且不带信息

查找过程类比二叉排序树即可

插入

每次插入后都需要逐层向上检查是否溢出而且要满足关键字大小的要求

删除

B+树

性质

1. 每个分支结点最多m个子树
2. 非叶根结点至少有两个子树，其他结点至少有⌈m/2⌉个子树
3. 结点的子树个数与关键字个数相等（与B树有区别）