What is the complexity (Big-O) of searching indexed data in mongoDB?
This is a design problem. Can you tell me if I am indexing keywords as below.
obj = {
name: "Apollo",
text: "Some text about Apollo moon landings",
tags: [ "moon", "apollo", "spaceflight" ]
}
Providing such an index.
db.articles.ensureIndex( { tags: 1 } );
and a frequent request as follows.
db.articles.findOne( { tags: "apollo" } ).name
Please give me an idea of such a request if I have n such documents.
is it O (1)?
And what is the performance for regex search for such data.?
source to share
It is a B-tree index, as it is in almost all databases, so it has a search time of O (log n).
A regex search sounds like you need to do a full table scan or a full index scan, both of which are O (n). If the expression is prefixed, it will only need to scan the range, but I think it still counts as O (n).
source to share
As Thilo mentioned, MongoDB indexes are implemented as B-Tree indexes and, in general, indexes in MongoDB are operationally similar to indexes in other database systems. There is a good overview of indexes in MongoDB here .
I recommend reading up on indexing strategies and indexing operations to help with your implementation, administration, and design.
To analyze the performance of your queries and see what they do, you can add an explain () statement to your query. See here for more information on explain()
and how to interpret its output.
MongoDB uses PCRE for regular expressions. Usage is described here . There is no size limit other than the PCRE library limit. As with all regexes, be aware of the consequences of a poorly constructed regex :)
source to share