Single field index in MongoDB - Time & Space Complexity

Time Complexity: Single field index

O(log n)

Understanding Time Complexity

When we use a single field index in MongoDB, it helps the database find data faster. We want to understand how the time to find data changes as the data grows.

How does using this index affect the speed of searching?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.users.createIndex({ age: 1 });

const result = db.users.find({ age: 30 });

This code creates an index on the "age" field and then searches for users who are 30 years old.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database uses the index to quickly locate matching entries without scanning all documents.
• How many times: The search moves through the index entries, which grow as more documents are added.

How Execution Grows With Input

As the number of documents grows, the index helps keep the search fast by not checking every document.

Input Size (n)	Approx. Operations
10	About 3-4 steps through the index
100	About 7 steps through the index
1000	About 10 steps through the index

Pattern observation: The number of steps grows slowly, much less than the total number of documents.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly as the data grows, making queries efficient even with lots of data.

Common Mistake

[X] Wrong: "Using an index makes the search time constant no matter how big the data is."

[OK] Correct: The search still takes more steps as data grows, but thanks to the index, it grows slowly, not instantly.

Interview Connect

Understanding how indexes speed up searches helps you explain how databases stay fast with lots of data. This skill shows you know how to make queries efficient.

Self-Check

"What if we searched without creating an index? How would the time complexity change?"

Practice

1. What is the main purpose of creating a single field index in MongoDB?

easy

A. To backup the database automatically

B. To speed up queries that filter or sort by one specific field

C. To store multiple fields in a single document

D. To create relationships between collections

Solution

1. Step 1: Understand what single field index does

   A single field index helps MongoDB find documents faster when searching or sorting by that one field.

2. Step 2: Compare options with this purpose

   Only To speed up queries that filter or sort by one specific field describes speeding up queries on one field, which matches the purpose of a single field index.

3. Final Answer:

   To speed up queries that filter or sort by one specific field -> Option B

4. Quick Check:

   Single field index = speed up queries on one field [OK]

Hint: Indexes speed up queries on the indexed field [OK]

Common Mistakes:

• Thinking indexes store multiple fields
• Confusing indexes with backups
• Believing indexes create relationships

2. Which of the following is the correct syntax to create a single field ascending index on the field age in MongoDB?

easy

A. db.collection.createIndex({ 'age' => 1 })

B. db.collection.createIndex(age: 1)

C. db.collection.createIndex({ age: 1 })

D. db.collection.createIndex({ age: 'asc' })

Solution

1. Step 1: Recall correct syntax for createIndex

   The correct syntax uses an object with the field name as key and 1 for ascending order: createIndex({ field: 1 }).

2. Step 2: Check each option

   db.collection.createIndex({ age: 1 }) matches the correct syntax exactly. The other options use invalid syntax or wrong symbols.

3. Final Answer:

   db.collection.createIndex({ age: 1 }) -> Option C

4. Quick Check:

   Correct syntax = createIndex({ field: 1 }) [OK]

Hint: Use curly braces and 1 for ascending index [OK]

Common Mistakes:

• Missing curly braces around the field
• Using wrong symbols like =>
• Using string 'asc' instead of 1

3. Given the following commands run on a MongoDB collection:

db.users.createIndex({ username: 1 })
db.users.find({ username: 'alice' })

What is the effect of the index on the find query?

medium

A. The query will use the index to find documents faster

B. The query will cause an error due to index usage

C. The query will ignore the index and scan all documents

D. The query will run slower because of the index

Solution

1. Step 1: Understand index effect on find queries

   Creating an index on 'username' helps MongoDB quickly locate documents matching that field.

2. Step 2: Analyze the find query

   The find query filters by username 'alice', so it will use the index to speed up the search.

3. Final Answer:

   The query will use the index to find documents faster -> Option A

4. Quick Check:

   Index on field = faster find queries on that field [OK]

Hint: Find queries on indexed field run faster [OK]

Common Mistakes:

• Assuming indexes slow down queries
• Thinking queries ignore indexes
• Believing index causes errors

4. You tried to create a single field index on email using this command:

db.users.createIndex(email: 1)

What is the problem with this command?

medium

A. Indexes cannot be created on the email field

B. Using 1 instead of 'asc' for ascending order

C. The field name should be a string in quotes

D. Missing curly braces around the field and order

Solution

1. Step 1: Check syntax for createIndex

   The argument to createIndex must be an object with curly braces: { field: 1 }.

2. Step 2: Identify error in given command

   The command lacks curly braces around email: 1, so it is invalid syntax.

3. Final Answer:

   Missing curly braces around the field and order -> Option D

4. Quick Check:

   createIndex needs { field: 1 } syntax [OK]

Hint: Always use curly braces for index fields [OK]

Common Mistakes:

• Omitting curly braces
• Using strings instead of numbers for order
• Thinking any field cannot be indexed

5. You want to speed up queries that sort users by their score field in descending order. Which command correctly creates a single field index to optimize this?

hard

A. db.users.createIndex({ score: -1 })

B. db.users.createIndex({ score: 1 })

C. db.users.createIndex({ score: 'desc' })

D. db.users.createIndex({ score: 0 })

Solution

1. Step 1: Understand index order for sorting

   To optimize descending sort, the index must be created with -1 for descending order.

2. Step 2: Evaluate each option

   db.users.createIndex({ score: -1 }) uses { score: -1 } which is correct. The option with { score: 1 } is ascending order, the option with { score: 'desc' } uses invalid string, the option with { score: 0 } uses 0 which is invalid.

3. Final Answer:

   db.users.createIndex({ score: -1 }) -> Option A

4. Quick Check:

   Descending index = { field: -1 } [OK]

Hint: Use -1 for descending index order [OK]

Common Mistakes:

• Using 1 for descending sort
• Using strings like 'desc' instead of numbers
• Using 0 which is invalid