7

是2n吗？只是检查。

4

4 回答 4

13

术语
B 树 的顺序在文献中没有经常定义。
（例如，参见维基百科关于 B-Trees 的文章的术语部分）
一些作者认为它是非叶节点可能持有的最小键数，而另一些作者认为它是非叶节点的最大子节点数节点可以持有（比此类节点可以持有的最大密钥数量多一）。
然而，许多其他人通过假设固定长度的键（和固定大小的节点）来绕过歧义，这使得最小值和最大值相同，因此顺序的两个定义产生的值相差 1（如所说的键数是总是比孩子的数量少一。）

我将深度定义为在叶记录的搜索路径中找到的节点数，包括根节点和叶节点。从这个意义上说，只有一个根节点直接指向叶节点的非常浅的树的深度为 2。如果该树要生长并需要中间级别的非叶节点，那么它的深度将为 3，以此类推。

在 n 阶 B-Tree 中可以容纳多少个元素？
假设固定长度的键，并假设“order” n 被定义为子节点的最大数量，答案是：

   (Average Number of elements that fit in one Leaf-node) * n ^ (depth - 1)

我如何计算？...：
数据（“元素”）仅保存在叶节点中。因此，持有的元素数是适合一个节点的平均元素数乘以叶节点数。
叶节点的数量本身由适合非叶节点的子节点数量（顺序）驱动。例如，叶节点上方的非叶节点指向 n 个（顺序）叶节点。然后，该非叶节点上方的非叶节点指向n个相似节点等，因此“到（深度-1）的幂”。

请注意，上面的公式通常使用平均值（非叶节点中保存的键和叶节点中保存的元素）而不是假设固定的键长度和固定的记录长度：树的节点大小通常为与键和记录的大小相称，因此持有一个或多个足够大的键或记录，以使任何叶子中保存的键或记录的有效数量与平均值相比变化相对较小。

示例：深度为 4
的树 （一个根节点、两级非叶节点和一层 [显然] 叶节点）和12 阶（非叶节点最多可容纳 11 个键，因此指向 12 个节点在它们下方）并且每个叶节点可以包含 5 个元素，将：   - 使其根节点指向其下方的 12 个节点 - 它下方的每个节点都指向它们下方的 12 个节点（因此该层中将有 12 * 12 个节点“3”（假设根是第 1 层等，这个编号顺便说一句也定义不明确......） - “第 3 层”中的每个节点将指向 12 个叶节点（因此将有 12 * 12 * 12 个叶节点。-   每个叶节点有 5 个元素（在本例中）


因此..这样一棵树将持有...

  Nb Of Elements in said tree = 5 * 12 * 12 * 12
                              = 5 * (12 ^ 3)
                              = 5 * (12 ^ depth -1)
                              = 8640

认识第 3 行的公式。

B-Tree 的普遍显着之处是其受欢迎程度的原因在于，一棵相对较浅的树（在根和寻找的记录之间“跳跃”数量有限的一棵树）可以保持相对较高数量的记录。这个数字乘以每个级别的顺序。

于 2010-04-03T18:25:17.037 回答
3

我的书说B树的顺序是可以存储在节点中的最大指针数。（第 348 页）“钥匙”的数量比订单少一。所以 n 阶的 B 树可以容纳 n-1 个元素。

这本书是 Michael J. Folk 的“文件结构”，第二版。

于 2010-04-03T18:56:57.377 回答
0

如果您的元素数量公式在某处不包含求幂，那么您做错了。

5 阶二叉树可以容纳 2^0 + 2^1 + 2^2 + 2^3 + 2^4 个元素，因此 31 ..（即 2^order - 1）。

编辑：我似乎把顺序和深度/长度弄混了。二叉树的顺序到底是什么？您似乎在讨论 B-树，就好像它们不按照其定义的本质，每个元素最多包含两个子元素。

于 2010-04-04T00:01:10.563 回答
0

令 b-tree 的顺序为 'm' 表示可以在 b-tree=m-1 的同一级别中插入的最大节点数。之后节点将分裂。例如：如果 order 为 3，则在第 3 个元素到达时只能插入 2 个最大节点，节点将按照二叉搜索树或自平衡树的属性进行拆分。

于 2016-11-25T15:03:09.123 回答