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

Question

根据Wiki和GFG，B 树的搜索/插入/删除时间复杂度为 O(log n)。AB 树可以有> 2 个孩子，即它不是二叉树。所以我不明白为什么它是 log n - 它不应该比 log n 快吗？例如，搜索应该是最坏情况 O(h)，其中 h 是树的高度。

标签： time-complexityb-tree

Answer 1

B-Tree 是二叉树的推广，其中每个节点可以有超过 2 个子节点。但这并不确定。例如，如果每个节点的子节点数定义为 x，那么复杂度将为. 但是，当最小子节点数为 2（如在 B-Tree 中）时，树的最大高度将为对数基数 2)。因此，B-Tree 的复杂度为。