BTree实现 - 我需要先知道树的顺序吗？

Question

所以我有一个我的数据结构类的项目，我必须实现一个非常简单的信息数据库。记录必须存储在一个文件中，当程序打开时 - 必须从文件中读取并放入BTree。我的问题是我们还没有谈论BTrees，课本中的讲座也不太清楚（它没有任何代码，只是解释和几个例子）。

我的问题是：我可以创建一个BTree而不必先知道它的顺序吗？或者我应该为订单设置一个非常高的数字，以便我可以确定它能够适合很多记录？有什么建议么？

Answer 1

你当然可以 - BTrees被设计用来整理他们的输入。所需要的只是比较任何两个对象的能力，并能够确定哪一个“较大”或稍后应该去。 BTrees会随着您添加更多项目而动态增长，从而为它们增加更多级别。我希望你的教授能够很好地涵盖BTrees，因为它们是一个非常吸引人的结构:-)。

如果您希望将BTree作为您的任务的一部分来实施，那么您需要转到TA并详细解释它 - 总体思路是每个节点都是一个节点根据值的范围对其进行排序，或指向其他节点的值。每次将节点添加到此树时，都会走到节点所在的位置，并在可能的情况下添加节点。如果不是，则重新组织树直到可能，然后添加节点。

魔鬼的细节，在这种情况下的细节将需要一些时间，并很好的解释，以充分grok。人们忍受头痛的所有复杂原因的原因是因为BT预先不需要事先知道它们最终会有多大，或者这些元素会覆盖什么范围，或者其他什么。作为奖励，它们非常适合在磁盘上使用，甚至无法将所有元素存储在内存中。

Answer 2

如果您正在实施自己的BTree，那么您应该确保它可以支持不同的订单，具体而言，因为您要使用的订单将取决于介质。 BTree的目的是尽量减少进行随机访问所需的时间，因此内存中的BTree（如果要这样使用）需要单个节点适合缓存行，并且如果要要将BTree存储在磁盘上（在这种情况下你将要做的），你会希望你的节点适合磁盘扇区。