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

Question

是2n吗？只是检查。

Answer 1

术语
B 树的顺序在文献中的定义并不一致。
(例如，参见 terminology section of Wikipedia's article on B-Trees )
一些作者认为它是非叶节点可以容纳的最小键数，而另一些作者则认为它是最大键数非叶节点可以拥有的子节点(比该节点可以拥有的最大键数多1)。
然而，许多其他人通过假设固定长度的键(和固定大小的节点)来绕过歧义，这使得最小值和最大值相同，因此顺序的两个定义产生相差 1 的值(正如所说的键的数量是总是比 child 的数量少一。)

我将深度定义为在叶记录的搜索路径中找到的节点数，包括根节点和叶节点。从这个意义上说，一棵非常浅的树，只有一个根节点直接指向叶节点，其深度为 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 树的显着之处在于，相对较浅的树(根和查找记录之间的“跳数”有限)可以保持相对较高的数字记录。该数字乘以每个级别的订单。