为什么单个节点要搜索的时间复杂度是O（1）而不是O（logn）？

Question

在存储了n个元素的四阶B树中的搜索中，查找单个节点的时间复杂度应为O（n），我知道B树搜索需要顺序登录时间，并且没有任何错误。

Answer 1

让我们的评论仅在一个NODE中搜索吗？这很重要。

B树具有子级数组。通常，在Array中进行搜索具有O（n）的复杂度。

如果对子级进行排序并使用二进制搜索，您将获得O（logn）复杂度。

因此，在通常情况下，B树中的搜索具有O（logn）复杂度。在更坏的情况下，它将具有O（n）。有2种情况：

1. 当所有元素都存储在未排序数组的第一个节点中时。

2. 所有节点只有一个孩子。然后将是列表。