作者简介:万汨,饿了么资深开发工程师。iOS,Go,Java均有涉猎。目前主攻大数据开发。喜欢骑行、爬山。
https://juejin.im/post/5da40462f265da5baf410a11
前言:针对“附近的人”这一位置服务领域的应用场景,常见的可使用PG、MySQL和MongoDB等多种DB的空间索引进行实现。而Redis另辟蹊径,结合其有序队列zset以及geohash编码,实现了空间搜索功能,且拥有极高的运行效率。
本文将从源码角度对其算法原理进行解析,并推算查询时间复杂度。
要提供完整的“附近的人”服务,最基本的是要实现“增”、“删”、“查”的功能。以下将分别进行介绍,其中会重点对查询功能进行解析。
操作命令
自Redis 3.2开始,Redis基于geohash和有序集合提供了地理位置相关功能。Redis Geo模块包含了以下6个命令:
GEOADD: 将给定的位置对象(纬度、经度、名字)添加到指定的key;
GEOPOS: 从key里面返回所有给定位置对象的位置(经度和纬度);
GEODIST: 返回两个给定位置之间的距离;
GEOHASH: 返回一个或多个位置对象的Geohash表示;
GEORADIUS: 以给定的经纬度为中心,返回目标集合中与中心的距离不超过给定最大距离的所有位置对象;
GEORADIUSBYMEMBER: 以给定的位置对象为中心,返回与其距离不超过给定最大距离的所有位置对象。
其中,组合使用GEOADD和GEORADIUS可实现“附近的人”中“增”和“查”的基本功能。
不过本质上,GEORADIUSBYMEMBER = GEOPOS + GEORADIUS,即先查找用户位置再通过该位置搜索附近满足位置相互距离条件的其他用户对象。
以下会从源码角度入手对GEOADD和GEORADIUS命令进行分析,剖析其算法原理。
Redis geo操作中只包含了“增”和“查”的操作,并没有专门的“删除”命令。主要是因为Redis内部使用有序集合(zset)保存位置对象,可用zrem进行删除。
在Redis源码geo.c的文件注释中,只说明了该文件为GEOADD、GEORADIUS和GEORADIUSBYMEMBER的实现文件(其实在也实现了另三个命令)。从侧面看出其他三个命令为辅助命令。
GEOADD
使用方式
领取专属 10元无门槛券
私享最新 技术干货