除了满度的要求，B树和B*树有什么区别？

Question

我知道关于这个问题，但它涉及B树和B+树。如果有关于B*-树的类似内容，我很抱歉，但我找不到。

---

那么，这两棵树之间有什么区别？wikipedia文章关于B * -trees非常简短。唯一指出的区别是"非根节点至少为2/3完全而不是1/2"。但我想还有其他的区别...如果这是唯一的区别，可能只会有一种类型的树-B-tree，只是具有不同的常量（用于每个非根节点的完整度），而没有两种不同的树，对吧？另外，还有一件事情让我想到更多的区别：

"A B*-tree should not be confused with a B+ tree, which is one where the 
leaf nodes of the tree are chained together in the form of a linked list"

因此，B+-树有一些非常特殊的东西 - 链表。 B*-树有什么具体特点，还是没有这样的特点？

---

此外，维基百科的文章中没有任何外部链接/参考资料。是否有任何资源可用？文章、教程或其他什么东西吗？

谢谢！

- Kiril Kirov

---

“不是一个真正的问题”？这里的“不真实”部分是什么意思？ - Kiril Kirov

你能给一些背景信息吗？如果关于B*树的信息很少，你是如何对它们产生兴趣的？a）出于好奇心，但也b）因为它可能帮助人们朝着正确的方向思考。 - Nicolas78

我并没有说“关于B树的信息很少”。维基百科上的简短文章并不意味着网络上没有相关信息，也不意味着这些树是陌生的。此外，我认为我对B树感兴趣的原因并不重要.. :) 无论如何，我只是在学习高级数据结构，除了不同的满度之外，我没有注意到任何其他区别。我想寻求一些帮助 :) 我们就是为此而在这里，对吧？ - Kiril Kirov

并不是想批评你提问的事实，只是有直觉认为如果有特定的使用情况，你可能会得到更多的答案。这经常发生在我身上："不知道那是什么...哦，原来他在谈论这个". 没关系 :) - Nicolas78

你说得对，但是没有其他信息。只是出于好奇心(: - Kiril Kirov

Answer 1

编辑 除了最小填充因子之外没有区别。

第489页

_{(来源：mit.edu)}

从上述书籍中可知,

B-tree*是B树的一种变体，要求每个内部节点至少为2/3满，而不是至少半满。

Knuth也像这样精确地定义了B*树(计算机编程艺术，第3卷)。

"

“普遍存在的B-Tree”有一个完整的子章节，介绍了B-树*。在这里，Comer确切地定义了B-树*，就像Knuth和Corment等人所做的那样，但他也澄清了混淆的根源——B-树*搜索算法以及由Knuth设计的一些未命名的B树变种，现在被称为B⁺-树。

"

- Apoorv

---

在这本书中，我们将探讨计算机编程的各个方面。我们将学习如何使用不同的编程语言创建应用程序和网站，以及如何设计和实现算法来解决问题。我们还将讨论软件工程的基础知识，包括版本控制、测试和协作。通过阅读这本书，您将学会如何成为一名合格的程序员，并为未来的职业发展打下坚实的基础。 - blubb

@Simon：话虽如此，这是一本非常好的书，尽管有时数学内容令人望而生畏。 - Matthieu M.

我在询问B*，而不是B+ ;p - Kiril Kirov

谢谢，现在你从我这里得到+1分(: - Kiril Kirov

@Monster TrucK: +1。谢谢你抽出时间！这是 Stack Overflow 社区完美运行的一个绝佳例子 :D - blubb

Answer 2

也许你应该看一下Comer的《普遍B树》（ACM计算调查，1979年）。

Comer在那里写了一些关于B*Tree的东西（在B-Tree及其变种部分）。在那个部分，他还引用了一些有关这个主题的论文。这应该帮助你自己进行进一步的调查：）！ （我不是你的研究员;)）

然而，我不理解你引用的那部分的要点，即B*Tree在叶节点层没有链接列表。我非常确定，那些节点也是彼此链接的。

关于只有一个B-Tree的问题。实际上，你就有了一个。其他的，像B+Tree、前缀B+Tree等都只是标准B-Tree的变体。看一下《普遍B树》这篇论文就好了。

- mkn

---

还没有。谢谢你指向这篇论文，我稍后会阅读它，因为现在无法阅读。不，我在这里发帖并不是为了找一个“研究员”，而只是想请有人指引我一些论文/教程/实现等，正如我在问题中已经提到的;) - Kiril Kirov