Spatial Index: R Trees

Data-driven structures for spatial indexing

If you have been following the Spatial Index Series, it started with the need for multi-dimensional indexes and an introduction to space-filling curves, followed by a deep dive into grid systems (GeoHash and Google S2) and tessellation (Uber H3).

In this post, let’s explore the R-Tree data structure (data-driven structure), which is popularly used to store multi-dimensional data, such as data points, segments, and rectangles.

1. R-Trees and Rectangles

For example, consider the plan of a university layout below. We can use the R-Tree data structure to index the buildings on the map.

To do so, we can place rectangles around a building or group of buildings and then index them. Suppose there’s a much bigger section of the map signifying a larger department, and we need to query all the buildings within a department. We can use the R-Tree to find all the buildings within (partially or fully contained) the larger section (query rectangle).

In the above figure, the red rectangle represent the query rectangle, used to ask the…