B树 - 为什么不能有一个偶数个键的节点?
我正在尝试根据“算法简介”中的“B-Trees”章节实现B树。
我不太了解的是“最小程度”。在书中,声明度是一个数字,表示节点可以容纳的键数的下限/上限。它还说:
每个非根节点至少存储
t - 1
个密钥,并且有t
个子节点。
每个节点最多存储2*t - 1
个键,并且有3ѭ个孩子。
所以你得到t = 2:
t - 1
= 1个键,t = 2个孩子
2*t - 1
= 3把钥匙和4个孩子
对于t = 3
t - 1
= 2个键,t = 3个孩子
2*t - 1
= 5把钥匙和6个孩子
现在问题是:B-Tree中的节点似乎只能在满满时存储奇数个密钥。
为什么不能有一个节点,最多可以说4个键和5个孩子?它与拆分节点有关吗?
没有找到相关结果
已邀请:
2 个回复
田眯衅
,允许使用1,2,3键的节点。对于
,允许使用具有2,3,4,5个键的节点。 而且,树的根只允许有1个密钥。 可以定义(和实现)具有例如的树。节点中的1或2个键(所谓的2-3棵树)。定义B树以容纳一个B-tree的原因是这导致更快的性能。特别是,这允许分摊
(计算拆分和连接操作)删除和插入操作。
为陡土