# Design Choices for Location Based Services / Part II

As we've seen, calculating locations in 2D space using **latitude and longitude** can be **compute-intensive** and **time-consuming**. However, queries and lookups in **1D** are significantly faster. Therefore, we are exploring methods to map 2D coordinates (lat, long) to 1D space.

This can be achieved in two main ways: **hash-based** and **tree-based** methods. We've already examined hash-based approaches, namely **Even Grid** and **GeoHash**. In this blog post, we will be discussing **Quad Tree**.

## Quad Tree

A **Quadtree** is a tree data structure used to efficiently **organize and partition a two-dimensional space**. It recursively divides a region into **four quadrants** (**quads**) until the content of a quadrant meets a certain condition (e.g., a maximum number of points). It is an effective method for **spatial indexing**, allowing for fast lookups and queries on data points (like latitude and longitude) that are clustered in a 2D plane.

A Quadtree is an **in-memory data structure**, not a database solution. It typically runs on a **Location-Based Service (LBS) Server** and is built during the server's startup time. The following steps detail the construction process:

1. The process begins with a single node (the **root**) that represents the entire 2D space being indexed (e.g., a city map).
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765295833458/ba03a3db-e0c0-416e-b58c-79b2b99501a6.png align="center")
    
2. A node is split into four child regions if it contains more data points or objects than a predefined **maximum capacity (threshold)**.
    
3. The four child regions are typically designated as **North-West, North-East, South-East, and South-West**.
    
4. The points within the parent node are then redistributed into the new child quadrants based on their coordinates.
    
5. This same splitting rule is **applied recursively** to each of the four child nodes.
    
    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1765295862955/9ffb19b6-ad62-49d0-8621-5b433d96e5e3.png align="center")
    
6. The process stops when a node (**a leaf**) satisfies the stopping condition—usually containing less than the maximum capacity of points or reaching a maximum defined depth.
    

The Quadtree follows **adaptive precision**, meaning the structure automatically adjusts to the data density. It saves computational resources by not over-dividing empty regions. It is due to this property that it is used for **collision detection** in games and **Level of Detail (LOD) rendering** in graphics.

While Quadtrees are excellent for spatial analysis, it is useful to compare them to alternative methods. For instance, **Geohash** is typically preferred for **high-volume writes** (like tracking moving objects) and simplicity, while Quadtrees excel for complex spatial analysis and non-uniform data distribution.

Additionally, as the server builds the Quadtree at startup, indexing **millions of records** can result in the Location-Based Service (LBS) taking **a few minutes to become operational**. This creates a period of **service unavailability** during the startup process. To mitigate this downtime, a deployment strategy of **incremental rollout** (or canary deployment) can be used, updating only a small subset of servers at a time while maintaining the availability of the others.

This deployment method, however, may result in some servers serving **stale data** for a short period. An alternative is to update the Quadtree **as changes occur** (on-the-fly). While this ensures data freshness, it significantly **complicates the design** because it necessitates implementing **locking mechanisms** within the Quadtree structure to ensure **thread safety** in a multi-threaded environment.

**Additional Reads & Watch**

* Quadtree - [https://www.youtube.com/watch?v=jxbDYxm-pXg](https://www.youtube.com/watch?v=jxbDYxm-pXg)
    
* Booking.com uses Quadtree - [https://medium.com/booking-com-development/how-to-search-point-of-interest-poi-markers-on-a-map-efficiently-b5f3f37a914a](https://medium.com/booking-com-development/how-to-search-point-of-interest-poi-markers-on-a-map-efficiently-b5f3f37a914a)