术语
The Order文献中对 B 树的定义并不一致。
(例如参见维基百科有关 B 树的文章的术语部分 http://en.wikipedia.org/wiki/Btree#Terminology)
一些作者认为它是minimum数量keys一个非叶节点可能成立,而其他人则认为它是maximum数量子节点非叶节点可以保存(比该节点可以保存的最大键数多 1)。
然而许多其他人通过假设固定长度的键(和固定大小的节点)来回避歧义,这使得最小值和最大值相同,因此顺序的两个定义产生相差 1 的值(正如所说的键的数量是总是比孩子的数量少一。)
我定义depth作为在叶记录的搜索路径中找到的节点数,包括根节点和叶节点。从这个意义上说,一棵非常浅的树,只有一个直接指向叶节点的根节点,其深度为 2。如果该树要生长并需要中间级别的非叶节点,则其深度将为 3 等。
n 阶 B 树中可以容纳多少个元素?
假设固定长度的密钥,并假设“顺序”n 被定义为最大数量子节点, 答案是:
(Average Number of elements that fit in one Leaf-node) * n ^ (depth - 1)
我怎么算?...:
数据(“元素”)仅保存在叶节点中。因此,持有的元素数量是一个节点中适合的平均元素数量乘以叶节点的数量。
叶节点的数量本身由适合非叶节点的子节点数量(顺序)驱动。例如,叶节点上方的非叶节点指向 n 个(顺序)叶节点。然后,该非叶节点之上的非叶节点指向n个相似节点等,因此“为(深度-1)次方”。
请注意,上面的公式通常使用平均值(非叶节点中保存的键和叶节点中保存的元素)而不是假设固定键长度和固定记录长度:树的节点大小通常为与键和记录大小相称,因此保存足够大的数字键或记录,使得任何叶子中保存的键或记录的有效数量与平均值相比变化相对较小。
Example:
一棵树depth 4(一个根节点,两层非叶节点和一层[显然]叶节点)和order 12(非叶节点最多可以容纳 11 个键,因此指向它们下面的 12 个节点),这样每个叶节点可以包含 5 个元素, would:
- 让它的根节点指向它下面的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 树的显着之处在于,相对较浅的树(根和查找记录之间的“跳跃”次数有限)可以保持相对较高的数字记录。这个数字是乘以按每个级别的顺序。