B树的定义中有一个这样的规定:
除根结点和叶结点之外,其他每个结点至少有 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈
1个孩子,至少要有 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈
1个关键字
为什么又这样的定义呢呢?
我们假设现在有一棵深度为1的5阶B树:
现在往B树中添加一个结点,
在有限制的情况下是这样分裂的:
如果没有对孩子结点和关键字个数进行限制,那么可以分裂出如下B树:
可见,同样是5个关键字,有限制的5阶B树只有3个结点,而未进行限制的5阶B树却有4个结点。可以想象,当关键字数量增多时,如果不对B树加以限制,那么B树的结点和深度会迅速膨胀。
在实践的过程中我们发现,经过一定次数的转换,可消除关键数小于 ⌈ m 2 ⌉ − 1 \lceil\frac{m}
⌉−1的非根非叶节点。所以关键数小于 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈
⌉−1的非根非叶节点势必可以合并为大于的 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈
由于B树是针对外存储器设计的多路查找结构,而一次外存储器IO操作的时间代价要比主存储器读写高出上万倍。因此B树的层数每减少一层、结点数量每减少一个,就是在减少一次外存储器的IO操作。所以说此种限制是为了最大限度的减少查找路径的长度,提高查找效率。