MongoDB中通过任意索引字段和非索引字段进行查询的SEARCH操作的时间复杂度是多少？

Question

我发现，MongoDB 使用 B 树，在使用任何索引字段（如 _id (ObjectId)）进行搜索时会导致 O(log n) 时间复杂度。但是，使用索引以外的任何字段进行搜索是否需要 O(n) 时间？ 如果没有，那么需要多少时间以及如何实现？ [这里没有显示]

Answer 1

如果您在

_id

字段上使用单个值和相等匹配进行搜索，则时间复杂度为 O(log n)

如果添加索引中没有的附加条件，查询执行器将首先使用索引来查找可能匹配的文档，然后需要一个附加的匹配阶段，该阶段将检查索引扫描找到的文档以应用附加的条件标准。

由于对

_id

字段进行相等搜索最多会产生 1 个文档，因此第二个匹配阶段的时间复杂度将为 O(1)。

如果查询在

_id

字段上使用范围搜索，从索引中找到第一个结果将是 O(log n)，然后之后的每个文档将是 O(1)，第二个匹配阶段将需要O(m)，其中 m 是索引扫描找到的文档数量。