B-Tree插入操作时间复杂度为何是O(log n)而非O(2d-1)？

要搞懂这个问题，核心要抓住B-Tree的度d是一个固定常数这个关键点：

• 插入操作的第一步是从根节点向下定位到目标叶节点，这个查找过程和B-Tree的查找逻辑一致，每层节点都可以通过二分查找快速缩小范围，树的高度是log_d n，这部分的时间复杂度是O(log n)。
• 找到叶节点后，插入元素的最坏情况确实需要遍历节点内所有2d-1个元素来移动位置，但因为d是预先设定的固定值（比如数据库实现中d通常是几十甚至上百的常数），2d-1是个固定数字，这一步的时间复杂度属于O(1)（常数时间）。
• 如果插入后节点满了，需要执行分裂操作：把满节点拆分成两个节点，并将中间元素向上移到父节点。分裂操作同样只需要处理O(d)个元素，还是常数时间。即便分裂需要从叶节点向上传播到根节点，整个过程最多也只会经过log_d n层，每层都是常数时间，总开销依然是O(log n)。

拿你给出的例子来说：当d=3时，节点最多有5个元素，插入时遍历5个元素的开销是固定的，不会随着B-Tree中总元素数n的增长而变大。真正随n变化的是树的高度，而树高是对数级的，所以整个插入操作的时间复杂度最终由树高决定，也就是O(log n)。

内容的提问来源于stack exchange，提问作者Shubhang b