B树、B+树到底是什么？

B树

B树又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一般从查找效率考虑，通常要求m>=3.

概念

一棵m阶b树或为空树，或为满足如下特质的n叉树：

1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字
2. 若根节点不是终端结点，则至少有两棵树
3. 除根结点外的所有非叶节点至少有【m/2】（向上取整）棵子树，即至少含有【m/2】（向上取整）-1个关键字
4. 所有非叶节点的结构如下： 其中Ki（i=1，2，。。。，n）为结点的关键字，Pi（i=1，2，。。。，n）为指向子树根结点的指针

nP0K1P1K2P2…KnPn

5. 所有的叶节点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
6. B树是所有结点的平衡因子均等于0的多路平衡查找树。

B树的高度

B树的高度不包括最后的不带任何信息的叶结点所在的那一层。 若n>=1，则对任意一棵包含n个关键字、高度为h、阶数为m的B树：

1. 因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足n=logm（n+1）
2. 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义：第一层至少有1个节点；第二层至少有2个结点；除根结点外的每个非终端节点至少有【m/2】棵子树，则第三层至少有2【m/2】个结点。。。第h+1层至少有2（【m/2】^(h-1)), 注意到第h+1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1，因此有n+1>2([m/2])^(h-1),即h