hel*_*hod 10 algorithm b-tree data-structures
我正在尝试根据"算法简介"中的"B-Trees"章节实现B树.
我不太了解的是"最小程度".在书中,声明度是一个数字,表示节点可以容纳的键数的下限/上限.它还说:
t - 1密钥并具有t子节点.2*t - 1密钥并具有2*t子节点.所以你得到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个孩子？它与拆分节点有关吗？
看来B-Tree中的节点只能存储奇数个key？
当然不。您写入的数字分别是键的最小和最大数量，因此对于t = 2，允许具有 1、2、3 个键的节点。对于t = 3，允许具有 2、3、4、5 个键的节点。
而且，树的根只允许有 1 个密钥。
可以定义（和实现）具有例如的树。一个节点中有 1 个或 2 个键（所谓的 2-3 树）。B 树被定义为容纳更多的树的原因是，这会带来更快的性能。特别是，这允许摊销O(1)（计算拆分和连接操作）删除和插入操作。