Memory and storage engine basics (WiredTiger) in MongoDB - Time & Space Complexity

Time Complexity: Memory and storage engine basics (WiredTiger)

O(log n)

Understanding Time Complexity

When using MongoDB's WiredTiger storage engine, it's important to understand how the time to read and write data changes as your data grows.

We want to see how the engine handles more data and what affects the speed of operations.

Scenario Under Consideration

Analyze the time complexity of a simple document insert and read operation using WiredTiger.

// Insert a document
db.collection.insertOne({ _id: 1, name: "Alice", age: 30 });

// Find a document by _id
db.collection.findOne({ _id: 1 });
    

This code inserts one document and then retrieves it by its unique _id field.

Identify Repeating Operations

Look at what happens repeatedly when inserting or finding documents.

• Primary operation: Searching the B-tree index for the _id field.
• How many times: Once per insert or find operation, but the search may traverse multiple tree levels.

How Execution Grows With Input

As the number of documents grows, the B-tree index grows in height slowly.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find a document
100	About 4-5 steps
1000	About 5-6 steps

Pattern observation: The number of steps grows slowly, increasing by a small amount even when data grows a lot.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find or insert a document grows slowly as the data size grows, thanks to the efficient tree structure.

Common Mistake

[X] Wrong: "Finding a document always takes the same time no matter how much data there is."

[OK] Correct: The time depends on the size of the data because the engine searches through a tree structure, which grows with data size, so it takes a bit longer as data grows.

Interview Connect

Understanding how WiredTiger uses tree structures to keep operations efficient shows you know how databases handle large data smoothly, a useful skill in many real projects.

Self-Check

"What if we added a new index on a non-unique field? How would that affect the time complexity of inserts and queries?"