Spatial index and space-filling curves for multidimensional data
Spatial data has grown (and is still growing) rapidly thanks to web services that track where and when users do things. Most apps add location tags and often allow users to check in at specific places and times. This rise is largely due to smartphones, which act as location sensors, making it easier than ever to capture and analyze this type of data.
The goal of this post is to lay the groundwork for the need for multidimensional indexes and to delve into the use of space-filling curves for spatial indexes that are widely used in both relational and non-relational databases. We will discuss the advantages and disadvantages of each type and also discuss which indexes are currently the most popular.
Spatial indexes fall into two main categories: space-based structures and data-driven structures. Data-driven structures, such as the R-tree family, adapt to the distribution of the data itself. Space-based structures include partition trees (k-d trees, quad trees), space-filling curves (Z-order, Hilbert), and grid systems (H3, S2, Geohash), each of which are based on the distribution of the data.
