algorithm - MongoDB 查找和删除算法复杂性

Question

MongoDB find操作和remove操作的big-o复杂度是多少。假设我的 MongoDB 集合中有 n 个字符串 - 'abc'，我使用 abc.find() 查询集合 'abc' 以获取 abc 中的所有元素此操作的运行时复杂度是多少？

此外，如果我执行 abc.remove({"string": s}，假设我的集合中有 n 个元素，运行时复杂度是多少？

Answer 1

您的问题取决于索引是否可以用于 query criteria您的 find 与否。如果可以使用索引，还取决于type of index :

• 如果没有索引可用，可以押O(n)。

• 在大多数情况下，索引是 b-trees ，在这种情况下，您可以期望 O(log n)。

• 在可以使用散列索引的特殊情况下，如果您的查询查找准确的值，它可能是 O(1)。

您可以使用 abc.explain() ton 分析查询执行计划(COLLSCAN O(1) vs IXSCAN 索引类型特定的 big-O)。

要删除集合中的项目，必须更新所有索引。从上面可以推断，这在很大程度上取决于引用该集合的索引的数量和类型。