How Quadtree Data Structure Enables Exploring Millions of Places Instantly on


2 min read's Lightning-Fast Location Search.

The most powerful feature on is the map.


There are tens of millions of listed properties on their marketplace, and users can search the map for the location and places nearby.

Thie experience on searching on the map is good only when it loads fast - and it sure does on

How does the backend search millions of different points across the world so quickly?

๐—ง๐—ต๐—ฒ ๐˜‚๐—ป๐—ฑ๐—ฒ๐—ฟ๐—น๐˜†๐—ถ๐—ป๐—ด ๐—ฑ๐—ฎ๐˜๐—ฎ ๐˜€๐˜๐—ฟ๐˜‚๐—ฐ๐˜๐˜‚๐—ฟ๐—ฒ ๐˜๐—ต๐—ฎ๐˜ ๐—ฝ๐—ผ๐˜„๐—ฒ๐—ฟ๐˜€ ๐˜๐—ต๐—ถ๐˜€ ๐—ถ๐˜€ ๐—ฎ ๐™Œ๐™ช๐™–๐™™๐™ฉ๐™ง๐™š๐™š.

A quadtree is a data structure used to represent and organize spatial data in a hierarchical manner. It is particularly useful for efficiently partitioning and querying information in two-dimensional space.

Here's how it works:

Start with the big square, which represents the entire space you want to divide and store information about.

Divide the square into four equal-sized smaller squares. These smaller squares are called "quadrants." Each quadrant represents a smaller part of the overall space.

If a quadrant is empty, you don't need to divide it further. You can mark it as empty and move on.

If a quadrant contains information, you can choose to divide it further into four smaller quadrants. You repeat the process for each of these smaller quadrants.

You continue dividing the squares until each quadrant either becomes empty or contains a single point of information. This forms the leaves of the quadtree.

Quadtrees find applications in various fields such as computer graphics, geographic information systems (GIS), collision detection, image processing, and more.

It is also an important system design topic for engineers to have an understanding of.

P.S - Repost this if you found it useful โ™ป๏ธ

P.P.S. If you want to learn more about software architecture and software engineering consider subscribing to my FREE newsletter.

Join 100+ "Adaptive Engineers"๐Ÿ‘‡

Did you find this article valuable?

Support Zahiruddin Tavargere by becoming a sponsor. Any amount is appreciated!