c - 对于大型和小型 btree，btree 中每个节点的密钥计数是否平均相同？

Question

我需要一些数学方面的帮助，这几天对我的大脑造成了伤害。

我为许多 btree 的不同大小的节点使用一个池。如果 btree 的每个节点的平均键数对于大树和小树相同，那么效果很好。但是，如果分布不同，我可能会遇到一种情况，即池中的一种大小的节点有太多空闲而其他节点不足。

所有更改都不是拆分节点，而是创建一个具有新键数的新节点，并用它覆盖树中的旧节点。当它通过每个节点的最大键数时，它将平均分割节点。

我直觉地认为节点大小的分布对于大树和小树（除了非常小的树）是相同的。但我知道最好不要相信我的直觉。这是一个合理的假设，还是btree中给定键计数的节点百分比会随着树的大小而变化？

Answer 1

btree 的经典实现是在树上使用单个基数（每个节点的最大键数），并在节点填充时拆分，并在节点填充减少到所选阈值以下时加入。btrees 比二叉树 (AVL) 树的一个好处是平衡树被最小化。基数的选择、键的添加和删除的混合以及添加到 btree 中的键的分布都会影响填充率。使用不同大小的节点会减少节点上的拆分次数，尤其是在向树中添加有序数据时。但是重新平衡树可以解决有序数据的问题。