n 阶 B 树中可以容纳多少个元素？

Question

是2n吗？只是检查。

Answer 1

术语
B 树的顺序在文献中的定义并不一致。
（例如，请参阅维基百科有关 B 树的文章的术语部分）
一些作者认为它是非叶节点可以容纳的最小键数，而另一些作者则认为它是最大键数非叶节点可以容纳的子节点（比该节点可以容纳的最大键数多1）。
然而，许多其他人通过假设固定长度的键（和固定大小的节点）来回避歧义，这使得最小值和最大值相同，因此顺序的两个定义产生相差 1 的值（正如所说的键的数量是总是比子节点的数量少一。）

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

如何n 阶 B 树中可以容纳许多元素？
假设固定长度键，并假设“顺序”n 被定义为子节点的最大数量，答案是：

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

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

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

示例：
一棵深度 4 的树（一个根节点、两层非叶节点和一层[显然]叶节点）和阶 12（非叶节点最多可以容纳 11 个键，因此指向它们下面的 12 个节点），并且每个叶节点可以包含 5 个元素，将：
  - 让它的根节点指向它下面的12个节点
  - 它下面的每个节点都指向它们下面的 12 个节点（因此“3”层中将有 12 * 12 个节点（假设根是第 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

认识第三行的公式。

B 树的显着之处在于，相对较浅的树（根和查找记录之间的“跳跃”次数有限）可以保持相对较高的数字记录。该数字乘以每个级别的订单。

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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