为什么B树的复杂度是O(log n)，不是二叉树

Question

根据 Wiki and GFG，B 树的 search/insert/delete 时间复杂度为 O(log n)。 B树可以有> 2 children，即它不是二叉树。所以我不明白为什么它是 log n——它不应该比 log n 快吗？例如搜索应该是最坏情况 O(h) 其中 h 是树的高度。

Answer 1

Big-O 是 最坏情况复杂度 的度量；由于 B-tree 个节点不需要超过 2 children，最坏的情况是没有个节点超过 2 children.

Answer 2

B-Tree 是二叉树的推广，其中每个节点可以有超过 2 children。但这并不确定。例如，如果每个节点的children个数定义为x，那么复杂度就是 $log_x n$ 。但是，当 children 的最小数量为 2（如 B-Tree）时，树的最大高度将为 $logn$ ，并且如前一个答案所述，Big-O 考虑最坏的情况是一棵树的高度最大（log base 2）。因此，B-Tree的复杂度为 $O(logn)$ .

Answer 3

是的，它不是二叉树。但是，如果我们在节点内执行二进制搜索算法（对于节点内的 kyes），时间复杂度可以认为是 O(logn)。

让我们考虑一下，

B-tree的度数（每个节点的最大children数）≤m。节点中的节点总数：n

如果是上述情况，

树的高度是

O(log<sub>m</sub>n)   ----------(1)

由于每个节点可以更改 children 的数量，因此必须对每个节点顺序

(lgm)   ----------(2)

进行对数搜索

所以在二叉树中搜索的总复杂度是

O(log<sub>m</sub>n) . O(lgm)   ----------(3)

根据对数运算，

{log<sub>b</sub>a = log<sub>c</sub>a / log<sub>c</sub>b}

将上述操作应用于(3)

O(log<sub>m</sub>n) . O(lgm) = O(lgn/lgm) . O(lgm)
                  = O(lgn)

所以B树搜索操作的时间复杂度是O(lgn)

为什么B树的复杂度是O(log n)，不是二叉树

Why B Tree complexity is O(log n), it is not a binary tree

b-tree

time-complexity