一次将多个值插入B+tree

Question

插入到b+tree中的元素是O(log n)，所以O(m n)用于m元素。有可能做得比这更好吗？例如，假设要插入的大多数元素在结果中大部分是连续的(并对它们进行预排序)，是否有一种方法可以将其简化为O(m log m+ log n)。

Answer 1

即使这是可能的，也不要忘记O(m log n)需要一棵相当大的树(n)才能与O( M log M )产生显著的区别，特别是在后一种情况下有更大的常数时。假设树有10亿个节点(10^9)，两个常量都是1，那么它的9*m操作与m log m操作。