Spatial index and space-filling curves for multi-dimensional data
Jun 11, 2024
Spatial data has grown (/is growing) rapidly thanks to web services tracking where and when users do things. Most applications add location tags and often allow users check in specific places and times. This surge 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 set a foundation for the need for multi-dimensional indexes and dive into the use of space-filling curves for spatial indexes that are widely used in both relational and non-relational databases. We’ll look at the pros and cons of each type and also discuss which indexes are the most popular today.
Spatial indexes fall into two main categories: space-driven and data-driven structures. Data-driven structures, like the R-tree family, are tailored to the distribution of the data itself. Space-driven structures include partitioning trees (kd-trees, quad-trees), space-filling curves (Z-order, Hilbert), and grid systems (H3, S2, Geohash), each…
