插入一个 b+ 树是 O(log n) 一个元素，因此 O(m log n) 是 m 个元素。有没有可能做得比这更好？例如，通过假设大多数要插入的元素在结果中大部分是连续的(并对它们进行预排序)，有没有办法将其减少到类似 O(m log m + log n) ?
最佳答案
即使这是可能的，也不要忘记你需要一棵相当大的树 (n) O(m log n) 与 O( m log m ) 有显着差异，特别是如果您在后一种情况下有更大的常数。 假设你的树有十亿 (10^9) 个节点并且两个常量都是 1，那么它的 9*m 操作与 m log m 操作。
关于algorithm - 一次将多个值插入 B+树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20429194/