R-Trees

Quad Trees and Geohashes are great for points on a map (like a car or a restaurant). But what happens when you need to search for shapes?

Imagine you are building Zillow, and a user draws a weird, squiggly polygon on the map and says, "Show me all the houses inside this area, and also all the parks that overlap with it."

Points are easy. Shapes (polygons, lines, rectangles) are messy. To search for shapes efficiently, we use an R-Tree.

The Bounding Box Trick

Let's use an analogy. Imagine you are moving, and you have hundreds of loose items: books, spatulas, shoes, cables. Finding a specific spoon is a nightmare.

So, what do you do? You put items into small boxes. Then, you put those small boxes into medium boxes. Then, you put the medium boxes into big moving trucks.

If you need a spoon, you don't check every truck. You look at the label on the truck: "Kitchen Stuff." You look at the medium box: "Utensils." You look at the small box: "Silverware." You found the spoon instantly.

This is exactly how an R-Tree works. The "R" stands for Rectangle.

Instead of dividing the world into a fixed grid, an R-Tree draws a Minimum Bounding Rectangle (MBR) around a group of nearby shapes.

1. It groups a few nearby houses and draws a box around them.
2. It groups several of these small boxes and draws a larger box around them.
3. It keeps doing this until everything is inside one massive root box.

Querying the R-Tree

When a user searches an area on the map, the database doesn't check the complex geometry of every park, lake, or house.

1. It takes the user's search area and sees which of the "big boxes" it overlaps with.
2. If a big box doesn't overlap, the database ignores everything inside it.
3. If it does overlap, the database looks at the smaller boxes inside.
4. It keeps drilling down until it finds the exact shapes that intersect the search area.

Comparing two simple rectangles to see if they overlap is incredibly fast. By using rectangles as proxies for complex shapes, R-Trees save massive amounts of CPU power.

Why not just use a Quad Tree?

Quad Trees divide space strictly into quadrants, regardless of what objects are there. R-Trees divide objects into logical groups, and the boxes are drawn around the objects themselves.

Because R-Tree boxes are tied to the data, they can overlap! If you have a long highway and a large park next to each other, their bounding boxes might overlap. The database might have to search down both branches of the tree if a user clicks in the overlapping area. Balancing an R-Tree to minimize this overlap is the hard part of making them efficient.

Real-World Examples

• PostGIS: The spatial extension for PostgreSQL uses R-Trees (specifically GiST indexes) to allow insanely fast queries on complex geographic shapes.
• Elasticsearch: Uses underlying spatial data structures heavily inspired by R-Trees to process geo-shape queries.
• CAD and GIS Software: AutoCAD and QGIS use them to render thousands of complex polygons (like city zoning maps) without freezing your computer.

Summary

R-Trees are hierarchical data structures designed for spatial data involving shapes, not just points. They work by grouping nearby objects and drawing Minimum Bounding Rectangles around them, creating a tree of boxes within boxes. This allows databases to quickly filter out irrelevant data by doing simple rectangle-overlap math, making complex geographic queries highly efficient.