If you have been following the Spatial index seriesIt started with the need for multidimensional indices and an introduction to curves that fill the spacefollowed by a deep dive into network systems (GeoHash and Google S2) and mosaic (Uber H3).
In this post, we will explore the R-Tree data structure (data-driven structure), which is popularly used to store multidimensional data such as data points, slices, and rectangles.
For example, consider the floor plan of a university shown below. We can use the R-Tree data structure to index the buildings on the map.
To do this, we can place rectangles around a building or group of buildings and then index them. Suppose there is a much larger section of the map representing 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 figure above, the red rectangle represents the query rectangle, used to ask…
