MongoDB Find and Remove Algorithmic Complexity

Question

What is the big-o complexity of MongoDB find operation and remove operation. Say I have n strings in my MongoDB collection - 'abc' and I query the collection 'abc' using abc.find() to get all the elements in abc what is the runtime complexity of this operation?

Also, if I do abc.remove({"string": s}, what would the runtime complexity be for that, given I have n elements in my collection?

Answer 1

Your question depends on whether an index can be used for the query criteria of your find or not. If an index can be used, it also depends on the type of index:

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

• In most cases, indexes are b-trees, 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() ton analyse the query execution plan (COLLSCAN O(1) vs IXSCAN index type specific big-O).

For the removal, of an item in the collection, all indexes must be updated. As you can infer from above, it depends pretty much on how many and what type of indexes refer to this collection.