B树的顺序
我正在准备考试，并想到了 B 树。维基百科将 B 树描述为一棵树，其中节点至少有 d 个、最多 2d 个键，因此最多有 2d+1 个叶子。例如，如果 d=1，它将最多有 2 个键和 3 个子节点，使其成为 2-3 树。然而，除非我弄错了，否则这不允许使用 2-3-4 树。
然而，我们的材料将 b 树描述为一棵树，其中每个节点至少有 t>=2 t-1 个键，最多 2t-1 个键。这意味着节点具有奇数个键和偶数个子节点。例如，t=2 将有 1 到 3 个键，以及最多 4 个子节点，使其成为 2-3-4 树。另一方面，用这种表示法不可能有 2-3 树。
除此之外，Knuth 有一个符号，其中 d 表示节点中子节点的最大数量。这种表示法允许偶数和奇数的子节点，即允许 2-3 树和 2-3-4 树。
我知道 2-3 树和 2-3-4 树都存在。
真正的记号是什么？有真正的记号吗？作为一个额外的问题；大小为 h 的树中键的最大数量是多少？
I'm studying for an exam, and came up on B-trees. Wikipedia describes a B-tree as a tree where the nodes have at least d and at most 2d keys and therefore at most 2d+1 leafs. For example if d=1, it would have a maximum of 2 keys, and 3 children, making it a 2-3 tree. However this wouldn't allow for example a 2-3-4 tree unless I'm mistaken.
However our material describes a b-tree as a tree where each node has at least t>=2 t-1 keys and at most 2t-1 keys. This would mean that the nodes have an odd number of keys and an even number of children. For example t=2 would have from 1 to 3 keys, and up to 4 children, making it a 2-3-4 tree. On the other hand there couldn't be a 2-3 tree with this notation.
On top of this, there is a notation by Knuth where the d would mean the maximum number of children in a node. This notation would allow both even and odd number of children, allowing both 2-3 trees and 2-3-4 trees.
I know both 2-3 trees and 2-3-4 trees exist.
What is the real notation? Is there a real notation? As an extra question; what is the maximun number of keys in a tree of size h?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您仔细阅读 wiki 文章，您会发现 B 树有两种主要变体（不包括 B* 和 B+ 等结构变体），其中一种带有
t-> 。2t键，以及一个带有t-> 的键2t+1键。将这些变体翻译为#children，我们有一个带有
t+1->2t+1个子级，以及一个具有t+1-> 的子级2t+2个孩子。因此，本质上要回答您的问题，2-3 和 2-3-4 树都是有效的树，每个树都根据不同的变体/定义：
2-3 属于第一种（
t+1->2t+1子节点，其中 t=1)2-3-4 属于第二类 (
t+1->2t+2< /code> 孩子，其中 t=1)这两种变体的有效性源于以下事实：拆分和合并（从 ADT 删除和插入 ADT 时执行的操作）都是有效的：
t->2t：分割。
当我们添加一个新元素并且节点的键数超过最大数量
2t时会发生所以我们有
2t+1键，我们将节点拆分为两个节点，并将一个元素推送到父节点，将2t键留在两个子节点中，并且t每个子项中的键。这是可以接受的，因为节点中键的最小数量确实是t。合并。
当我们删除一个键并且一个节点包含的数量小于最小数量
t时就会发生这种情况，并且它的兄弟节点也是最小的。因此，我们的新合并节点中有t-1 + t键，结果节点必须有效：t-1 + t = 2t-1 <= 2t。伟大的。t也是如此 ->2t+1：分割。
2t+2变成t和t+1就可以了。合并。
t-1 + t = 2t-1 <= 2t+1当然，运行时间没有区别，这只是轻微的实现差异，理论上的重要性不大（您可以使用以下方法稍微优化一些算法）第一个变体，但不会改变运行时复杂性）。
If you read the wiki article a little more closely you'll see that there are two main variants of B-trees (excluding structural variants like B* and B+), one with
t->2tkeys, and one witht->2t+1keys.Translating those variants to #children we have one with
t+1->2t+1children, and one witht+1->2t+2children.So essentially to answer your question, both 2-3 and 2-3-4 trees are valid trees, each according to a different variant/definition:
2-3 is of the first kind (
t+1->2t+1children where t=1)2-3-4 is of the second kind (
t+1->2t+2children where t=1)The validity of both variants stems from the fact that both splits and merges (actions done on delete and insert from/into the ADT) are valid:
t->2t:Split.
Happens when we add a new element and a node has more than the max number of keys
2tSo we have
2t+1keys, we split the node into two nodes, and push one element to the parent, leaving2tkeys in the two children, andtkeys in each child. This is acceptable because the minimum number of keys in a node is indeedt.Merge.
Happens when we delete a key and a node contains less than the minimum number,
t, and it's sibling is also at the minimum. So we havet-1 + tkeys in our new merged node, the resulting node must be valid:t-1 + t = 2t-1 <= 2t. Great.So too with
t->2t+1:Split.
2t+2becomestandt+1which is OK.Merge.
t-1 + t = 2t-1 <= 2t+1Of course there is no difference in running times, it's just a slight implementation difference of little theoretical importance (you can slightly optimise some algorithms with the first variant, but not so much that it will change run-time complexities).
在谷歌学术中搜索 b 树角 => Ubiquitous B-Tree，Comer，1979
这是数据结构论文中引用次数最多的论文。本文详细描述了 b 树（它是如何工作的、复杂性及其变体......）。在那里你应该找到你的答案。
我希望这有帮助
。如果您使用的公式与教授的公式不同，请在考试中引用该论文：P
search in google scholar for b tree comer => Ubiquitous B-Tree, Comer, 1979
This is the most cited paper which you find in data structure papers. This paper describes the b tree in detail (how it works, complexity and it variants...). There you should find your answer.
I hope this helps
p.s. cite that paper in the exam if you use a different formula than the taught one :P