Geospatial queries basics in MongoDB - Time & Space Complexity

Time Complexity: Geospatial queries basics

O(log n)

Understanding Time Complexity

When we use geospatial queries in MongoDB, we want to find locations near a point or within an area.

We ask: How does the time to find these locations grow as we have more places stored?

Scenario Under Consideration

Analyze the time complexity of the following geospatial query.

db.places.createIndex({ location: "2dsphere" })

const nearbyPlaces = db.places.find({
  location: {
    $near: {
      $geometry: { type: "Point", coordinates: [ -73.97, 40.77 ] },
      $maxDistance: 5000
    }
  }
})
    

This code finds places within 5 kilometers of a given point using a 2dsphere index.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Searching the geospatial index to find matching locations.
• How many times: The index search visits parts of the tree structure depending on data size and query area.

How Execution Grows With Input

As we add more places, the search looks through more index nodes but not every place.

Input Size (n)	Approx. Operations
10	About 3-5 index checks
100	About 7-10 index checks
1000	About 10-15 index checks

Pattern observation: The search grows slowly, checking only parts of the index, not every place.

Final Time Complexity

Time Complexity: O(log n)

This means the query time grows slowly as the number of places grows, thanks to the index.

Common Mistake

[X] Wrong: "The query checks every place one by one, so it takes longer linearly as data grows."

[OK] Correct: The 2dsphere index lets MongoDB skip many places, searching efficiently like a tree, not a list.

Interview Connect

Understanding how geospatial queries scale shows you know how databases handle location data efficiently.

Self-Check

"What if we removed the 2dsphere index? How would the time complexity change?"