Capped collections for fixed-size data in MongoDB - Time & Space Complexity

Time Complexity: Capped collections for fixed-size data

O(n)

Understanding Time Complexity

When working with capped collections in MongoDB, it's important to understand how the time to insert or read data changes as the collection grows.

We want to see how the fixed size of capped collections affects the speed of operations.

Scenario Under Consideration

Analyze the time complexity of inserting documents into a capped collection.

    db.createCollection("logs", { capped: true, size: 100000 });
    
    for (let i = 0; i < n; i++) {
      db.logs.insertOne({ message: `Log entry ${i}`, timestamp: new Date() });
    }
    

This code creates a capped collection with a fixed size and inserts n log entries into it.

Identify Repeating Operations

Look at what repeats as we insert documents.

• Primary operation: Inserting one document into the capped collection.
• How many times: n times, once for each log entry.

How Execution Grows With Input

As we add more entries, the collection stays the same size, so old entries get removed automatically.

Input Size (n)	Approx. Operations
10	10 insert operations, each quick
100	100 insert operations, still quick
1000	1000 insert operations, speed stays steady

Pattern observation: Each insert takes about the same time regardless of how many documents are already in the capped collection.

Final Time Complexity

Time Complexity: O(n)

This means inserting n documents takes time proportional to n, with each insert operation being very fast and consistent.

Common Mistake

[X] Wrong: "Inserting into a capped collection slows down as it fills up because it has to delete old data."

[OK] Correct: The capped collection is fixed size and uses a circular buffer, so insert speed stays constant no matter how full it is.

Interview Connect

Understanding capped collections shows you know how fixed-size data storage works efficiently, a useful skill for real-world logging and data retention tasks.

Self-Check

"What if we changed the capped collection to a normal collection without size limits? How would the time complexity of inserts change as data grows?"

Practice

1. What is the main purpose of a capped collection in MongoDB?

easy

A. To store data only in memory without writing to disk

B. To allow unlimited data growth without any size restrictions

C. To store data with a fixed size limit and automatically remove old entries

D. To create collections that support complex transactions

Solution

1. Step 1: Understand capped collection purpose

   Capped collections are designed to hold a fixed amount of data, automatically removing the oldest entries when full.

2. Step 2: Compare options with this behavior

   Only To store data with a fixed size limit and automatically remove old entries describes fixed size and automatic removal of old data, matching capped collection behavior.

3. Final Answer:

   To store data with a fixed size limit and automatically remove old entries -> Option C

4. Quick Check:

   Capped collection = fixed size + auto-remove old [OK]

Hint: Remember capped means fixed size with auto-removal [OK]

Common Mistakes:

• Thinking capped collections grow unlimited
• Confusing capped with in-memory storage
• Assuming capped collections support complex transactions

2. Which of the following is the correct command to create a capped collection named logs with a maximum size of 1MB?

easy

A. db.createCappedCollection('logs', 1048576)

B. db.logs.create({ capped: true, size: 1048576 })

C. db.createCollection('logs', { size: 1048576 })

D. db.createCollection('logs', { capped: true, size: 1048576 })

Solution

1. Step 1: Recall syntax for capped collection creation

   The correct syntax uses db.createCollection with options including capped: true and size in bytes.

2. Step 2: Check each option

   db.createCollection('logs', { capped: true, size: 1048576 }) matches the correct syntax. db.logs.create({ capped: true, size: 1048576 }) uses wrong method. db.createCollection('logs', { size: 1048576 }) misses capped: true. db.createCappedCollection('logs', 1048576) is invalid.

3. Final Answer:

   db.createCollection('logs', { capped: true, size: 1048576 }) -> Option D

4. Quick Check:

   Create capped = createCollection + capped:true + size [OK]

Hint: Use createCollection with capped:true and size in bytes [OK]

Common Mistakes:

• Omitting capped:true option
• Using wrong method like createCappedCollection
• Specifying size without capped:true

3. Given a capped collection cache with size 100 bytes, what will be the result of inserting 3 documents each of size 50 bytes?

medium

A. Only the last 2 documents will be stored, the first is removed

B. All 3 documents will be stored without removal

C. Insertion will fail due to size limit

D. Only the first document will be stored

Solution

1. Step 1: Understand capped collection size behavior

   The collection size is 100 bytes. Each document is 50 bytes, so two documents fit exactly.

2. Step 2: Analyze insertion of 3 documents

   When inserting the third document, the oldest document (first) is removed to keep size within 100 bytes, so last two remain.

3. Final Answer:

   Only the last 2 documents will be stored, the first is removed -> Option A

4. Quick Check:

   Size limit causes oldest removal [OK]

Hint: Capped size limits storage; oldest removed when full [OK]

Common Mistakes:

• Assuming all documents fit ignoring size
• Expecting insertion failure instead of removal
• Thinking only first document stays

4. You tried to create a capped collection with db.createCollection('events', { capped: true }) but got an error. What is the likely cause?

medium

A. The collection name 'events' is reserved and cannot be used

B. Missing the required size option specifying the maximum bytes

C. Capped collections cannot be created with createCollection

D. You must specify max documents instead of size

Solution

1. Step 1: Recall required options for capped collections

   When creating a capped collection, the size option (max bytes) is mandatory.

2. Step 2: Analyze the error cause

   Omitting size causes an error. Collection name and method are valid. max is optional.

3. Final Answer:

   Missing the required size option specifying the maximum bytes -> Option B

4. Quick Check:

   Capped creation requires size option [OK]

Hint: Always specify size when creating capped collections [OK]

Common Mistakes:

• Forgetting the size option
• Thinking collection names are restricted
• Confusing max documents with required size

5. You want to store recent user activity logs in a capped collection named userLogs with a max of 1000 documents and size limit 5MB. Which command correctly creates this collection?

hard

A. db.createCollection('userLogs', { capped: true, size: 5242880, max: 1000 })

B. db.createCollection('userLogs', { capped: true, max: 1000 })

C. db.createCollection('userLogs', { size: 5242880, max: 1000 })

D. db.createCollection('userLogs', { capped: true, size: 1000 })

Solution

1. Step 1: Identify required options for capped collection with limits

   Must specify capped: true, size in bytes, and max documents.

2. Step 2: Evaluate each option

   db.createCollection('userLogs', { capped: true, size: 5242880, max: 1000 }) correctly includes all three: capped true, size 5MB (5*1024*1024=5242880 bytes), and max 1000. Others miss required options or have wrong values.

3. Final Answer:

   db.createCollection('userLogs', { capped: true, size: 5242880, max: 1000 }) -> Option A

4. Quick Check:

   Capped + size in bytes + max docs = correct creation [OK]

Hint: Use capped:true with size in bytes and max docs for limits [OK]

Common Mistakes:

• Omitting size or max options
• Using size as number of documents
• Not setting capped:true