MongoDB 查找和删除算法复杂度

Question

MongoDB的查询（find）和删除（remove）操作的时间复杂度是怎样的？如果我有n个字符串存在MongoDB的集合中，当我使用abc.find()来获取其中所有的元素时，这个操作的运行时间复杂度是多少？

另外，如果我使用abc.remove({"string": s})进行删除操作，那么它的运行时间复杂度是多少，假设我的集合中有n个元素？

- meh123

Answer 1

Your question depends on whether an index can be used for the 查询条件 of your find or not. If an index can be used, it also depends on the 索引类型:

• If no index can be used, you can bet on O(n).

• In most cases, indexes are B-树, in which case you can expect O(log n).

• In the special case that a hash index can be used, and provided your query looks for the exact value, it could be O(1).

You can use abc.explain() 来分析查询执行计划 (COLLSCAN O(1) vs IXSCAN 索引类型特定的大O)。

如果要从集合中删除一个项目，则必须更新所有索引。正如您可以从上面推断出的那样，这在很大程度上取决于有多少个和哪些类型的索引与该集合相关。

- Christophe

---

如果我的查找调用中没有查询，并且我只需要数据库中的所有元素，它仍然是O(n)吗？ - meh123

是的：没有查询意味着您浏览所有元素。这是O(n)。 - Christophe

根据 https://docs.mongodb.com/v3.2/reference/explain-results/，上述可能存在一个错别字，`COLSCAN` 的时间复杂度为 O(n)，而 FETCH 的时间复杂度为 O(1)。在引用说明之前的描述中似乎已经正确说明了这一点。 - Alpar