B树中的节点数 [英] Number of nodes in a B-Tree
问题描述
如果我按顺序从1到n插入数字，结果B树（最小度2）有多少个节点？
How many nodes does a resulting B-Tree(min degree 2) have if I insert numbers from 1 to n in order?
我尝试从1插入节点到20，有一个系列的节点数量来了，但我无法推广。
I tried inserting nodes from 1 to 20 there was a series for the number of nodes coming but i could not generalize it.
任何人都可以帮助我得出这个公式。
Can anyone please help me derive the formula for this.
推荐答案
它将取决于B-Tree的顺序。 BTree的顺序是非叶节点可以保持的最大子节点数（这比节点可以容纳的最小密钥数量多一个）。
It will depend on the order of the B-Tree. The order of a BTree is the maximum number of children nodes a non-leaf node may hold (which is one more than the minimum number of keys such a node could hold).
根据Knuth的定义，订单m的B树是满足以下属性的树：
According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:
- 每个节点最多有m个子节点。
- 每个非叶节点（根除外）至少有⌈m/2⌉个孩子。
- 如果根目录不是叶节点，则至少有两个子节点。
- 带k个孩子的非叶节点包含k-1个键。 >
- 所有的叶子都出现在相同的水平上，内部顶点不会包含任何信息。
- Every node has at most m children.
- Every non-leaf node (except root) has at least ⌈m⁄2⌉ children.
- The root has at least two children if it is not a leaf node.
- A non-leaf node with k children contains k−1 keys.
- All leaves appear in the same level, and internal vertices carry no information.
所以在你的情况下当您插入20个键时，如果顺序为m，则根据上述条件，您可以导出一组描述m的可能值的不等式。但是没有相等的公式表示B树中的内部节点数。
So in your case when you are inserting 20 keys if the order is m then based on the conditions mentioned above you can derive a set of inequalities that describes the possible value of m. But there is no equality formula that says the number of internal nodes in a B-Tree.
这篇关于B树中的节点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
