B+Tree上的最小/最大记录数？

Question

我正在研究B+Tree (http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights)的最好和最坏情况，但我不知道如何结合我所掌握的信息使用这个公式。假设我有一个包含1,000条记录的树B，B可以拥有的最大(和最大)级别数是多少？我可以在每一页上有尽可能多/更少的密钥。我也可以有尽可能多/最少的页数。有什么想法吗？(如果你想知道，这不是一个家庭作业问题，但它肯定会帮助我理解一些关于hw的东西。)

Answer 1

这取决于树的多重性。您必须定义此值。如果你说每个节点可以有4个子节点，那么你有1000条记录，那么高度是

最佳情况log_4(1000) =5

最坏情况log_{4/2}(1000) = 10

正确率是m，记录数是n。

Answer 2

我手头没有算术，但是...

基本上，影响树深度的主要因素是树中每个节点的“扇出”。

通常，在简单的B-Tree中，扇出是2，2个节点作为树中每个节点的子节点。

但对于B+Tree，他们通常会有更大的扇形。

发挥作用的一个因素是磁盘上节点的大小。

例如，假设您有一个4K的页面大小，以及4000字节的空闲空间(不包括任何其他指针或与节点相关的其他元数据)，假设指向树中任何其他节点的指针是一个4字节的整数。如果您的B+Tree实际上存储的是4字节的整数，那么组合大小(4字节的指针信息+4字节的键信息)=8字节。4000个可用字节/8个字节== 500个可能的子项。

在这个假造的案子里给你打了满分500分的分数。

因此，如果只有一页索引，即根节点，或者树的高度为1，则可以引用500条记录。添加另一个级别，您将处于500*500，因此对于501个4K页面，您可以引用250,000行。

显然，键大小越大，或者节点的页面大小越小，树的扇出能力就越低。如果您允许在每个节点中使用可变长度的键，那么扇出的值很容易发生变化。

但希望你能看到这一切是如何工作的。

Answer 3

最好和最坏的情况取决于否。每个节点可以拥有的子节点的。对于最好的情况，我们考虑这样的情况，当每个节点具有最大数量的子节点(即，对于m元树，m)，并且每个节点具有m-1个关键字。所以,

第一级(或根)具有m-1个条目，第二级具有m*( m-1 )个条目(因为根具有m个子节点，每个子节点具有m-1个键)，第三级具有m^2*(m-1)个条目...Hth能级为m^(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)是每个内部节点(根节点除外)可以具有的子节点的最小数目)第三级具有2d*(d-1)个条目...Hth级别有2*d^(h-2)*(d-1)个条目

因此，如果H是树的高度，则条目总数等于n=2*d^H-1，这相当于H=log_d((n+1)/2+1)

因此，在您的示例中，如果您有n=1000记录，并且每个节点都有m个子节点(m应该是奇数)，那么最坏情况下的高度将等于log_d((1000+1)/2+1)