空间索引Spatial Index

在O2O行业里，LBS（Location Based Service）基于位置的服务有着非常广泛的应用场景，例如根据用户定位地址召回附近3公里可配送的商家，根据定位位置召回附近2公里的空闲出租车等，而LBS服务依赖空间检索（Spatial Index）相关技术支撑，常见的做法是把球面坐标系通过墨卡托投影映射为二维平面坐标系，然后基于二维平面坐标做相应的位置检索服务。

本文主要内容如下：

介绍空间索引的基本概念：GeoHash、R-树、四叉树；

分析支持空间索引的5大存储系统：MySQL，PostgreSQL，Redis、MongoDB和ElasticSearch等的特点，对比不同存储系统空间索引功能特性、海量数据下的并发性能（RT、QPS），以及官方API文档初窥；

Part I - 基本概念

空间索引（Spatial Index）是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。

GeoHash

geohash的核心思想是降维，把空间划分为一个个矩形网格，将二维矩形区域映射成一维的01字符串，每个geohash出来的字符串表示一个矩形区域，hash值越长，精度越高，表示的区域越小。

geohash出来的字符串具有前缀索引信息（类似字典树Trie树），前缀表示了比整个串对应更大的矩形范围（例如wb12x是5位的，包含了wb12x..........的网格，即wb12x是个大格子，wb12x....是更小的格子），这个特性可以用于附近地点检索，首先根据用户当前坐标计算对应的geohash值，然后取其前缀匹配进行查询，即可查询附近的所有点。

算法分为三步：

先分别通过中值法计算经纬度，转换成二进制01字符串

合并字符串并分组，奇数位放经度，偶数位放纬度

对字符串进行base32编码转换

举个例子，例如某个点的经纬度是[42.18, 135.62]。

地球的纬度区间是[-90,90]。把这个区间分为2部分，即[-90,0)，[0,90]。42.18位于(0,90]区间，即右区间，标记为1。然后继续把(0,90]区间二分，分为[0,45)，[45,90]，42.18位于[0,45)区间，即左区间，标记为0。一直划分下去。同理对于经度，把区间[-180,180]按照类似的中值方法进行划分也能够得到一个01字符串。下面这张图展示的是9个矩形对应的geohash字符串。

R-树

R-树采用一种叫做MBR（Minimal Bounding Rectangle）最小外界矩形，其中的R就是指的Rectangle矩形的意思，从叶子结点开始用矩形（Rectangle）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。R-树是处理空间数据的B+树的改进，它像B+树一样，是一个高度平衡的数据结构，现已成为空间数据库索引中应用最广泛的算法之一。

R-树是B+树在高维空间的扩展，是一颗平衡树，每个R-树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R-树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。

四叉树

四叉树（Quad-Tree）是一种树状数据结构，在每一个节点上会有四个子区块。四叉树是一个二维空间递归细分。它使用了平分划分实现，将每一个块平分成了四个同等大小的方块。四元树常应用于二维空间数据的分析与分类。它将数据区分成为四个象限。四叉树可以认为是二叉查找树的高维变体，它适合对有二维属性的数据进行存储和查询。

四叉树跟GeoHash类似，都具有前缀索引信息（类似字典树Trie树），通过四个方向的编码来确定周边位置，跟GeoHash的查找原理区分为：

GeoHash 本质上是hash编码将二维信息用一维来表示，其查找原理从根本上来说是二叉树，在查找时会根据hash编码选择两个方向之一继续精确，查询复杂度为log2N

四叉树保留了其二维查找的特性，其查找会根据其X,Y选择四个方向之一继续查找，其查询复杂度为log4N

Part II - 存储系统

MySQL

MySQL 是一个全面集成、事务安全、符合 ACID 的数据库，默认使用InnoDB存储引擎，可以交付高性能、可扩展的联机事务处理 (OLTP) 应用，是互联网最广泛的开源持久化存储系统。

MySQL5.7对于GIS进行了大幅重构和优化，InnoDB引擎原生支持地理空间数据类型，内部通过R-树来实现空间索引。MySQL5.7还提供了原生的st_geohash函数，可将地理空间坐标转化为Geohash格式，通过SPATIAL KEY添加空间索引。

优点：5.7新版功能，未来值得期待

缺点：数据库版本升级较复杂，对于现有业务系统来讲是个巨大的挑战。另外对于大数据量下的空间索引支持有待线上系统检验。

API：http://mysqlserverteam.com/mysql-5-7-and-gis-an-example/

PostgreSQL

PostgreSQL 是一个自由的对象-关系数据库管理系统，PostgreSQL标榜自己是世界上最先进的开源数据库，完全由社区驱动的开源项目。PostgreSQL是属于根红苗正的学院派，走的是正经学术风格，但是没有搭上互联网这艘大船，导致没有被大规模使用。

构建在PostgreSQL上的空间对象扩展模块 PostGIS 使得其成为一个真正的大型空间数据库。PostgreSQL通过 R-树 或 GIST 树索引来实现空间索引，查询效率极高。

优点：支持多种复杂、灵活的查询特性，效率极高，大数据量下不会像MongoDB一样性能急剧下降

缺点：依赖安装较为繁琐，复杂索引时写入较慢

API：http://mysql.taobao.org/monthly/2015/07/04/

Redis

Redis是一个使用ANSI C编写的开源、支持网络、基于内存、可选持久性的键值对存储数据库。

Redis 3.2 以上版本支持空间索引，Redis GEO实现主要包含了以下两项技术：

使用geohash保存地理位置的坐标。

使用有序集合（zset）保存地理位置的集合。

优点：效率高，使用方便

缺点：功能简单，无法实现多条件查询，版本升级在业务系统里是个麻烦的事情

API：http://redisdoc.com/geo/index.html

MongoDB

MongoDB是一种面向文档的，Schemaless，开源NoSQL数据库管理系统，用于存储非结构化数据，采用BSON描述数据类型。

MongoDB 是老牌的支持空间索引的数据库，MongoDB提供2dsphere类型的空间索引，2dsphere 索引支持查询在一个类地球的球面上进行几何计算，以GeoJSON对象或者普通坐标对的方式存储数据，2dsphere 索引使用 GeoHash 算法用 B+ 树来实现。

优点：灵活的空间索引，GeoJSON 对象有点、线、多边形、多条线段、多点、多个多边形。支持 包含、相交、临近的查询，支持多条件查询。

缺点：进行大量数据空间检索时，性能会急剧下降。

API：http://www.mongoing.com/docs/core/2dsphere.html

ElasticSearch

Elasticsearch 是一个分布式、可扩展的全文搜索引擎，底层依赖开源的Lucence库，ES是面向文档型数据库，内部使用倒排索引Inverted Index，而非MySQL内部的B+树，可以基于时间构建索引，历史索引可以定期删除，分布式多副本索引架构。

地理位置功能仅仅是 Elasticsearch 的冰山一角，Elasticsearch 的妙处在于，它让你可以把地理位置、全文搜索、结构化搜索和分析结合到一起。Elasticsearch 提供了两种表示地理位置的方式：用纬度－经度表示的坐标点使用 geo_point 字段类型，以GeoJSON格式定义的复杂地理形状，使用 geo_shape 字段类型。

优点：支持多种复杂查询，扩展性很好，例如在千万级别的数据量下，基于点的空间检索，性能也有比较好的表现。

缺点: 很难说他有明显的缺点，在海量数据检索领域是一个很好的选择

API：https://www.elastic.co/guide/cn/elasticsearch/guide/current/geoloc.html

总结

本文主要介绍了空间索引Spatial Index相关的基本概念，例如GeoHash，R-树，四叉树等基本算法，通过对比分析支持空间索引的常见存储引擎MySQL，PostgreSQL，Redis，MongoDB和ElasticSearch，给出了不同存储系统的特点，在实际的业务场景中，需要根据数据量、检索复杂度以及贴近公司的实际运维使用习惯，综合考虑选择适合自身的存储引擎，希望本文能给大家在空间检索服务技术评估选型带来一些参考和帮助。

参考文献

[1]https://github.com/digoal/blog/blob/master/201712/20171231_01.md

[2]http://www.mongoing.com/mongodb-geo-index-1/

[3]http://postgis.net/docs/manual-2.3/reference.html?spm=a2c4e.11153940.blogcont175035.24.326049dd1IqtMn