c - 对于大型和小型 btree，btree 中每个节点的键数平均相同吗？

Question

我的数学需要一点帮助，这几天我的大脑很痛。

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

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

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

Answer 1

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