m阶B树的非根非叶结点至少要ceil(m/2)个孩子原因
B树的定义中有一个规定:除根结点和叶结点之外,其他每个结点至少有⌈m2⌉\lceil\frac{m}{2}\rceil⌈2m⌉个孩子,至少要有⌈m2⌉−1\lceil\frac{m}{2}\rceil-1⌈2m⌉−1个关键字为什么要这样规定呢?我们假设现在有一棵深度为1的5阶B树:现在往B树中添加一个结点,在有限制的情况下是这样分裂的:如果没有对孩子结点和关键字个数进行限制,那么可以分裂出如下
B树的定义中有一个这样的规定:
除根结点和叶结点之外,其他每个结点至少有 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m⌉个孩子,至少要有 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈2m⌉−1个关键字
为什么又这样的定义呢呢?
我们假设现在有一棵深度为1的5阶B树:
现在往B树中添加一个结点,
在有限制的情况下是这样分裂的:
如果没有对孩子结点和关键字个数进行限制,那么可以分裂出如下B树:
可见,同样是5个关键字,有限制的5阶B树只有3个结点,而未进行限制的5阶B树却有4个结点。可以想象,当关键字数量增多时,如果不对B树加以限制,那么B树的结点和深度会迅速膨胀。
在实践的过程中我们发现,经过一定次数的转换,可消除关键数小于 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈2m⌉−1的非根非叶节点。所以关键数小于 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈2m⌉−1的非根非叶节点势必可以合并为大于的 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈2m⌉−1结点。
由于B树是针对外存储器设计的多路查找结构,而一次外存储器IO操作的时间代价要比主存储器读写高出上万倍。因此B树的层数每减少一层、结点数量每减少一个,就是在减少一次外存储器的IO操作。所以说此种限制是为了最大限度的减少查找路径的长度,提高查找效率。
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)