B+ 1 和 2 的树顺序
0 algorithm b-tree data-structures
我对于要插入顺序为 1 和顺序为 2 的 B+ 树中的键的最大和最小数量感到困惑。
在我看的视频中，据说一个节点（根除外）中插入的键的最大数量至少为m，最多为2m（假设m为阶数）。
根据这 2 个陈述，在 B+ 树中插入的键的最小和最大数量是多少，阶数为 1 和阶数为 2？我不确定以上两种说法是否冲突，或者我误解了什么。任何想法？
如果没有参考视频，看起来他们使用了术语order的非标准定义，这就是造成混乱的原因。
树的顺序的标准定义是最大分支因子，即节点可以拥有的最大子节点数。因此，在该定义中，它不是最小值，而是最大值，并且与键的数量无关，而是与子项的数量有关。
视频的定义意味着最大按键数始终是偶数，而实际上没有这样的要求。B+ 树很可能具有偶数的最大分支因子，从而使键的最大数量为奇数。
使用术语order的标准定义，我们对 B+ 树特别有以下约束：
- 它的内部节点最多有m个子节点。这意味着它们最多有m - 1 个密钥。
- 它的内部节点至少有m/2（向上舍入）子节点，根除外：
- 如果它的根不是叶子，它可能只有 2 个孩子。
- 它的叶子包含实际的数据值。
下面是一个阶数为 4（标准定义）的 B+ 树示例，它对应于键数必须在 1 到 3 之间的 B+ 树——这与视频的定义不符：
正如您所看到的，一个节点最多可以有 4 个子节点，最多有 3 个键。在您的定义中，2m表示最大键数，顺序实际上是2m+1。因此，您需要使用 order 的标准定义来获取 3 阶和 5 阶 B+ 树的示例。
下面是 3 阶的示例（B+ 树的最低阶），这意味着每个节点中的键数必须为 1 或 2：
