我一直在寻找最好的& B +树最坏的情况下（http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights），但我不知道如何使用这个公式与我有的信息。 假设我有一棵有1000条记录的树B，B级可以拥有的最大（和最大）数是多少？ 我可以在每个页面上拥有多少个小键。我也可以有很多/少量的页面。 任何想法？ （如果你想知道，这不是一个家庭作业问题，但它肯定会帮助我理解hw的一些东西。）B +树上最小/最大记录数？
它取决于树的arity。你必须定义这个值。如果说，每个节点都可以有4个孩子，然后你有1000条记录，则高度
最好的情况log_4（1000）= 5
最坏的情况LOG_ {} 4/2（1000）= 10
矩阵是m，记录数是n。
我没有数学得心应手，但...
基本上，树深度的主要因素是树中的每个节点的“扇出”。
通常情况下，在简单的B树中，扇出为树中每个节点的子节点为2,2个节点。
但是用B +树，它们通常会有更大的扇形。
进入播放的一个因素是磁盘上节点的大小。例如，如果您有4K页面大小，并且有4000字节的可用空间（不包括与节点相关的任何其他指针或其他元数据），并且可以说指向任何其他节点的指针在树中是一个4字节的整数。如果您的B +树实际上存储了4个字节的整数，则组合大小（指针信息的4个字节+ 4个字节的关键信息）= 8个字节。 4000个空闲字节/ 8个字节== 500个可能的孩子。
这给你一个500人的粉丝为这个人为的案件。
因此，只有一页索引（即根节点）或树的高度为1时，可以引用500条记录。添加另一个级别，并且您的值为500 * 500，因此对于501个4K页面，您可以引用250,000行。
很显然，密钥的大小越大，或者节点的页面尺寸越小，该树能够胜出的扇形越小。如果您允许每个节点中的可变长度密钥，那么扇出可以很容易地改变。
但希望你能看到这一切的工作原理。
有道理！谢谢！ – Eric
最好的和最坏的情况取决于没有。每个节点可以拥有的孩子。对于最好的情况，我们考虑这样的情况，即当每个节点具有m-1个密钥的每个节点时，子节点的最大数量（即m个树的m）。所以，
第一电平（或根）具有m-1条目 第二级具有m *（M-1）的条目（因为根具有m儿童每个m-1的键） 第三级具有平方公尺*（m-1）条目 ....（H-1）*（m-1）
因此，如果H是树的高度，则条目的总数等于n = m^H-1 这是相当于H = log_m（n + 1）
因此，在你的情况下，如果你有n = 1000个记录，每个节点有m个孩子（m应该是奇数），那么最好的情况高度将等于log_m （1000 + 1）
类似地，对于最坏的情况下：
1级（根）具有至少1个条目（和最小2个孩子） 第二级至少有2 *（d-1）个条目（其中d = ceil（m/2）是每个内部节点（根除外）可以拥有的最小子数） 第3级有2d *（d-1）个条目 ... Hth等级具有2 * d ^（h-2）*（d-1）个条目
因此，如果H是树的高度，则条目的总数等于n = 2 *如果你有n = 1000条记录，每个节点有m个孩子（m应该是奇数），则最差情况高度将等于log_d（（1000 + 1）/ 2 + 1）
这很容易！谢谢！ – Eric