B树的一个公认的好处是分支度可以很高，这在限制到达节点所需的磁盘访问次数方面很有用。
但是，假设我们有一个（k，2k）B树，并且天真的实现了这些节点。搜索实际上将在
log（n）* k / log（k）
人们可能选择在嵌套的平衡树中表示节点内部的值，这样即使在很大k的情况下，这些节点中键的插入和删除也将保留在log（k）中，而搜索将保留在log（n）中。 。
是否有论文建议采用这种方法或后续的实现方式，或者分支因子k通常太低而无法引起麻烦？
您可能想读F. Cesarini和G. Soda的“二叉树分页”。它着重介绍了B树树页面嵌入AVL树的类似方法。我不确定是否可以在这里链接它，但是通过使用Google谷歌搜索就可以轻松获得它。
这是一个有趣的想法，但通常您看不到这一点。为什么有两个原因。
对于初学者，当您在B树上进行插入或删除时，主要瓶颈是执行的I / O传输次数而不是CPU工作量。从这个意义上讲，转移一堆数组元素的成本可能不会占B树操作成本的很大一部分。
接下来，是这些操作的频率问题。如果您使用的是B +树，其中的键仅存储在叶子中，而每个内部节点仅存储路由信息，则绝大多数插入和删除操作实际上不会更改树的内部节点，而只是触摸叶子（图每2k个插入中大约只有一个需要拆分一个节点，而（2k）2操作中只有一个需要拆分两个节点，依此类推）。这意味着开始时并没有那么多的数组编辑，因此提高它们的速度不一定是值得的。
您遇到的另一个主要问题是如何为那些树节点分配内存。 B树等已针对磁盘上的存储进行了优化。这意味着典型的B树操作将通过将磁盘中的原始字节块分页到某个缓冲区中，然后将这些字节视为您的节点来工作。反过来，这意味着如果您以这种方式存储BST，则该BST中的节点将无法存储常规指针，因为一旦将节点的内存地址加载到内存中，它们之间的运行地址就不一致。这就排除了使用malloc或new之类的东西，并且您需要实现自己的内存管理器才能将磁盘页面的字节分配给节点。这将带来很多开销，并且要使其具有足够的时间和空间效率以保证通过原始阵列切换到BST会很棘手。
与原始阵列相比，使用BST还会增加内存开销。与原始数组相比，BST每项需要两个额外的指针/偏移量，这减少了您可以塞入某个模式的键的数量。由于B树的主要速度来自于将尽可能多的键装配到节点中，因此首先可能会吃掉B树的优势。
希望这会有所帮助！