b树概念的理解_b树的叶子结点不包含关键字

 B 树又叫平衡多路查找树，俗称b-树，或者b树。

树中每个结点最多含有m个孩子（m>=2）；因为每个节点最多有m-1个关键字而已

2.除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；因为每个节点最少有cell(m/2)-1个关键字而已

3.若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；因为插入的分裂特性还是一分唯二。

4.所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（读者反馈@冷岳：这里有错，叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。@研究者July：其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。
因为删除时合并的特性，所以b-树的叶子节点都在同一层。

5.每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
       a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。 
        b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 
        c)   关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。如下图所示：
总结绕死人：k表示关键字，p表示指向子树根结点的指针。k左边的关键字小于右边的。同时因为分裂的特性，节点中的关键字满足公式ceil(m / 2)-1]<= n <= m-1