在n阶的B树中可以保存多少个元素？

Question

是2n吗？只是检查.

Answer 1

术语 B-Tree
的顺序在文献中不断定义.
(参见例如维基百科上关于B-树文章的术语部分),
一些学者认为这是最低的数字键的非叶节点可持有,而其他人则认为它是最大的数子节点非叶节点可以保持(这比节点可以容纳的最大密钥数多一个).
然而,许多其他人通过假设一个固定长度的密钥(和固定大小的节点)绕过模糊性,这使得最小值和最大值相同,因此订单的两个定义产生相差1的值(如所说的密钥数量是总是少于孩子的数量.)

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

在n阶B树中可以保存多少个元素？
假设固定长度密钥,并假设"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层等,这个编号btw也是模糊定义的......) - "第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来说通常是显着的,并且使它们受欢迎的是相对浅的树(在根和所寻找的记录之间具有有限数量的"跳")可以保持相对高的数量记录.此数字乘以每个级别的订单.