从地图到智能地图：空间索引技术如何改变我们的世界

图源：@WL

为什么空间索引很有用?

在处理地理空间数据时，空间索引是一个至关重要的功能，它决定了我们如何高效地从海量的地理数据中检索出所需的信息。想象一下，如果你正在处理一个包含数千万乃至数亿条记录的数据库，这些记录可能涵盖全球各城市、街道和建筑物的详细信息。在没有合适的索引的情况在，每次查询都可能不得不扫描整个数据集，这将是非常低效的。空间索引的引入，正是为了优化这一过程，确保查询操作既迅速又高效。在这篇文章中，我将讨论空间索引是如何实现的，以及它的优点和局限性。

什么是空间索引?

首先让我们重温下普通索引，普通索引就像我们经常会在书的末尾看到的：一个包含名词及其出现位置的列表。它可以帮助我们快速查找感兴趣的名词在特定内容中的引用。如果没有它，我们就不得不手动翻阅书中的每一页进行寻找。

在数据库中，查询和搜索一直都是十分常见且重要的功能。索引的引入通常使查找数据比遍历整个数据库更快，并且我们可以根据关注的列创建索引。而在对地理空间数据的处理中，通常需要执行诸如“交叉路口”或“在…附近”之类的操作。怎样才能建立一个空间索引，使这些操作尽可能快呢？接下来，让我们看一下数据库中的地理空间数据：

两个不相交的湖泊 图源：@WL （由Mapmost平台制作）

假设我们想要通过查询来确定这两个湖泊是否相交。通过构造，空间数据库将根据包含几何图形的边界框创建索引

两个湖泊的边界框 图源：@WL （由Mapmost平台制作）

为了判断这两个湖泊是否相交，数据库将比较两个边界框是否有任何共同区域，正如图所显示的。然而这可能直接导致错误的结论。为了解决这个问题，像PostGIS这样的空间数据库通常会将这些大的边界框分割成越来越小的边界框。

划分了小边界框的两个湖泊 图源：@WL （由Mapmost平台制作）

这种分区策略采用了一种叫做 R 树的结构进行存储。R树是一种具有层级特性的数据组织形式，它记录了一个较大的父级边界框，父级边界框下包含其所有子级边界框，以及子级边界框的子级，依次类推，形成了一个层级嵌套的体系。在这个结构中，每个父级边界框都完整地覆盖了其所有子级边界框的位置。

R-树结构示例 图源：@WL

得益于R-树结构的优势，判断“相交”与否将十分迅速：在执行相交查询时，数据库会遍历这棵树，检查每个节点的边界框，询问“当前的边界框是否与我们感兴趣的地理特征相交？”如果是，它将继续检查该边界框内的所有子框，并重复相同的相交检验。在这个过程中，数据库能够迅速地遍历整个树形结构，同时忽略那些显然不相交的分支，显著提高了查询效率。最终，系统会根据查询要求，返回所有与查询条件相交的数据。

空间索引到底有多快？

GeoPandas库同时提供了判断两个几何特征是否相交的普通方法，以及通过建立R-Tree空间索引后求解两个几何特征交集的方法，让我们采用GeoPandas库进行一个简单的对比测试吧，步骤如下。

第一步：数据准备，这里我们使用纽约市公共设施的数据集(通过开放数据下载，有需要的同学关注公众号获取)。

第二步：环境安装，通过anaconda官网下载安装包一键安装conda，接着通过conda搭建python环境，并安装GeoPandas及其依赖。

conda create -n geo_env
conda activate geo_env
conda config --env --add channels conda-forge
conda config --env --set channel_priority strict
conda install python=3 geopandas

第三步：编写测试用例，我们主要使用geopandas.GeoSeries.intersects()方法进行普通"交集"运算；通过调用geopandas.GeoSeries.sindex属性生成指定数据集的R-Tree空间索引；使用geopandas.sindex.SpatialIndex.query()方法利用建立的索引进行两个几何体的交集查询。

第四步：运行程序，结果：

从测试结果中，可以看出通过依次将34171条数据与固定的某个几何图形做“交集”运算，在不采用R-Tree空间索引的情况下耗时3.4秒，而使用了R-Tree空间索引之后耗时则是其十分之一不到。

R-Tree空间索引一定好用吗？

是否存在使用了R-Tree索引后没有任何好处的情况？是的。其中之一，便是由R-Tree空间索引存储数据的方式造成的。事实证明，原始数据的分布会影响边界框放入R-Tree中的位置。具体来说，如果大量数据集中在同一个地理空间中，它们往往会拥有相同的父节点，因此会被分组到相同的分支中。这将会导致树结构的倾斜，从而在查询时无法达到预期的优化。

Mapmost平台作为智能地图的工厂，在空间数据处理的API背后，自研并使用了多种结合特定场景的空间索引算法，致力于为用户提供极致性能体验，赶快扫码体验吧。