m阶B树的非根非叶结点至少要ceil(m/2)个孩子原因

简介: m阶B树的非根非叶结点至少要ceil(m/2)个孩子原因

B树的定义中有一个这样的规定:


除根结点和叶结点之外,其他每个结点至少有 ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈



1个孩子,至少要有 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2}\rceil-1 ⌈



1个关键字


为什么又这样的定义呢呢?


我们假设现在有一棵深度为1的5阶B树:


20200830112952656.jpeg


现在往B树中添加一个结点,

在有限制的情况下是这样分裂的:


20200830112952656.jpeg


如果没有对孩子结点和关键字个数进行限制,那么可以分裂出如下B树:


20200830112952656.jpeg


可见,同样是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操作。所以说此种限制是为了最大限度的减少查找路径的长度,提高查找效率。


相关文章
|
5月前
|
人工智能 测试技术 Windows
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
|
5月前
|
测试技术
【动态规划】【组合数学】1866. 恰有 K 根木棍可以看到的排列数目
【动态规划】【组合数学】1866. 恰有 K 根木棍可以看到的排列数目
|
5月前
|
人工智能 算法 BI
【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目
【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目
|
5月前
|
人工智能 算法 BI
【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块
【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块
|
5月前
leetcode-129:求根节点到叶节点数字之和
leetcode-129:求根节点到叶节点数字之和
33 0
|
5月前
|
Python
平方根,又叫二次方根,表示为〔√ ̄〕
平方根,又叫二次方根,表示为〔√ ̄〕
|
5月前
|
机器学习/深度学习
【每日一题Day181】LC1026节点与其祖先之间的最大差值 | 树形dp
【每日一题Day181】LC1026节点与其祖先之间的最大差值 | 树形dp
39 0
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树验证二叉搜索树验证二叉搜索树v
60 2
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树
|
Python
LeetCode 129. 求根节点到叶节点数字之和
给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
99 0
leetcode 129 求根节点到叶节点数字之和
leetcode 129 求根节点到叶节点数字之和
74 0