Redis GEO 用做存储地理位置信息，并对存储的信息进行操作。通过geo相干的命令，能够很容易在redis中存储和应用经纬度坐标信息。Redis中提供的Geo命令有如下几个：
- geoadd：增加经纬度坐标和对应地理位置名称。
- geopos：获取地理位置的经纬度坐标。
- geodist：计算两个地理位置的间隔。
- georadius：依据用户给定的经纬度坐标来获取指定范畴内的地理位置汇合。
- georadiusbymember：依据贮存在地位汇合外面的某个地点获取指定范畴内的地理位置汇合。
- geohash：计算一个或者多个经纬度坐标点的geohash值。
要了解Redis的GEO相干的命令是如何实现了，就得先了解geohash的原理，实质上这些命令就是对geohash数据的封装而已。
geohash
geohash是2008年Gustavo Niemeye创造用来编码经纬度信息的一种编码方式，比方北京市核心的经纬度坐标是116.404844,39.912279，通过12位geohash编码后就变成了wx4g0cg3vknd，它到底是如何实现的？其实原理非常简单，就是二分，整个编码过程能够分为如下几步。
1. 转二进制
上过初中天文的咱们都晓得，地球上如何一个点就能够标识为某个经纬度坐标，经度的取值范畴是东经0-180度和西经0-180度，维度的取值范畴是北纬0到90和南纬0-90度。去掉东西南北，能够别离认为经度和维度的取值范畴为[-180,180]和[-90,90]。
咱们先来看经度，[-180,180]能够简略分成两个局部[-180,0]和[0,180]，对于给定的一个具体值，咱们用一个bit来标识是在[-180,0]还是[0,180]区间里。而后咱们能够对这两个子区间持续细分，用更多的bit来标识是这个值是在哪个子区间里。就好比用二分查找，记录下每次查找的门路，往左就是0往右是1，查找完后咱们就会失去一个0101的串，这个串就能够用来标识这个经度值。
同理维度也是一样，只不过他的取值返回变成了[-90,90]而已。通过这两种形式编码实现后，任意经纬度咱们都能够失去两个由0和1组成的串。
比方还是北京市核心的经纬度坐标 116.404844,39.912279，咱们先对116.404844做编码，失去其二进制为:
11010010110001101101而后咱们对维度39.912279编码失去二进制为：
10111000110000111001 2. 经纬度二进制合并
接下来咱们只须要将上述二进制交织合并成一个即可，这里留神经度占偶数位，纬度占奇数位，失去最终的二进制。
1101101110000200111100000001111011010011 3. 将合并后的二进制做base32编码
最初咱们将合并后的二进制做base32编码，将间断5位转化为一个0-31的十进制数，而后用对应的字符代替，将所有二进制位解决完后咱们就实现了base32编码。编码表如下：
最终失去geohash值wx4g0cg3vknd。
geohash是将空间一直的二分，而后将二分的门路转化为base32编码，最初保留下来，从原理能够看出，geohash示意的是一个区间，而不是一个点，geohash值越长，这个区间就越小，标识的地位也就越准确，下图是维基百科中不同长度geohash下的经纬度误差（lat:维度，lng:经度）
geohash的用处及问题
geohash胜利的将一个二维信息编码成了一个一维信息，这样编码我感觉有两个益处：1. 编码后数据长度变短，利于节俭存储。2. 利于应用前缀检索。咱们来具体说下第二点。
从上文中geohash的实现来看，只有两个坐标点的geohash有独特的前缀，你们咱们就能够必定这两个点在同一个区域内 (区域大小取决于独特前缀的长度)。这种个性给咱们带来的益处就是，咱们能够把所有坐标点按geohash做增序索引，而后查找的时候按前缀筛选，大幅晋升检索的性能。
举个例子，假如我要找北京国贸左近3公里内的餐馆，已知国贸的geohash是wx4g41，那我也很轻易就能够计算出来我须要扫描哪些区域内的点。但有个点须要留神，上文我曾经提到过，geohash值实际上是代表一个区域，而不是一个点，找到一批候选点之后还须要遍历一次计算下准确间隔。
geohash有个须要留神的问题。geohash是将二维的坐标点做了线下编码(如下图)，有时候可能会给人一个误会就是如果两个geohash之间二进制的差别越小，这两个区间间隔就越近，这齐全是谬误的，比方如下图0111和1000，这俩区间二进制只差0001但理论物理间隔比拟远。
如果上图还不显著的话，我从Wikipedia上拿到一张图，虚线是线性索引的门路，被虚线链接的两个块geohash值是十分相近的，如下图的(7,3)和(0,4)，geohash值会十分相近，但理论物理间隔十分远，这就是geohash的渐变景象，这也导致了不能间接依据geohash的值来间接断定两个区域的间隔大小。
但在理论应用geohash过程中，时常会遇到跨域搜寻的状况，比方我要在上图(3,3)这个区间内某个点上搜寻距它1个间隔单位的所有其余点集，这个点集有可能横跨(3,3)加上它四周8个邻域的9个区间，渐变的问题会导致这9个区间的geohash不是线性跳转的，但也不是没法计算，实际上能够通过非凡的位运算能够很轻易计算出某个geohash的8个邻域，具体可参考redis源码中src/geohash.c中geohashNeighbors()的具体实现，geohashNeighbors应用了geohash_move_x和geohash_move_y两个函数实现了geohash左右和高低的挪动，这样能够很容易组合出8个邻域的geohash值了。
static void geohash_move_x(GeoHashBits *hash, int8_t d) {
if (d == 0)
return;
uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
uint64_t y = hash->bits & 0x5555555555555555ULL;
uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);
if (d > 0) {
x = x + (zz + 1);
} else {
x = x | zz;
x = x - (zz + 1);
}
x &= (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
hash->bits = (x | y);
}
static void geohash_move_y(GeoHashBits *hash, int8_t d) {
if (d == 0)
return;
uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
uint64_t y = hash->bits & 0x5555555555555555ULL;
uint64_t zz = 0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2);
if (d > 0) {
y = y + (zz + 1);
} else {
y = y | zz;
y = y - (zz + 1);
}
y &= (0x5555555555555555ULL >> (64 - hash->step * 2));
hash->bits = (x | y);
}Geo in redis
上文中花了大量篇幅解说了geohash的实现，其实看到这里，你基本上曾经了解了redis中的geohash的实现了。实质上redis中的geo就是对geohash的封装，具体geohash相干的代码就不给大家列了(可自行查阅)，就给大家介绍下redis geo里的大体流程。
首先，可能大家最好奇的是geohash在redis中是怎么存储的，从geoadd命令的实现能够一窥端倪。
/* GEOADD key [CH] [NX|XX] long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
int xx = 0, nx = 0, longidx = 2;
int i;
/* 解析可选参数 */
while (longidx < c->argc) {
char *opt = c->argv[longidx]->ptr;
if (!strcasecmp(opt,"nx")) nx = 1;
else if (!strcasecmp(opt,"xx")) xx = 1;
else if (!strcasecmp(opt,"ch")) {}
else break;
longidx++;
}
if ((c->argc - longidx) % 3 || (xx && nx)) {
/* 解析所有的经纬度值和member，并对其个数做校验 */
addReplyErrorObject(c,shared.syntaxerr);
return;
}
/* 构建zadd的参数数组 */
int elements = (c->argc - longidx) / 3;
int argc = longidx+elements*2; /* ZADD key [CH] [NX|XX] score ele ... */
robj **argv = zcalloc(argc*sizeof(robj*));
argv[0] = createRawStringObject("zadd",4);
for (i = 1; i < longidx; i++) {
argv[i] = c->argv[i];
incrRefCount(argv[i]);
}
/* 以3个参数为一组，将所有的经纬度和member信息从参数列表里解析进去，并放到zadd的参数数组中 */
for (i = 0; i < elements; i++) {
double xy[2];
if (extractLongLatOrReply(c, (c->argv+longidx)+(i*3),xy) == C_ERR) {
for (i = 0; i < argc; i++)
if (argv[i]) decrRefCount(argv[i]);
zfree(argv);
return;
}
/* 将经纬度坐标转化成score信息 */
GeoHashBits hash;
geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, &hash);
GeoHashFix52Bits bits = geohashAlign52Bits(hash);
robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits));
robj *val = c->argv[longidx + i * 3 + 2];
argv[longidx+i*2] = score;
argv[longidx+1+i*2] = val;
incrRefCount(val);
}
/* 转化成zadd命令所须要的参数格局*/
replaceClientCommandVector(c,argc,argv);
zaddCommand(c);
}原来geo的存储只是zset包了一层壳(是不是有点小悲观)，对于zset的具体实现能够参考我之前写的文章redis中skiplist的实现。
咱们再来具体看下georadius的大体执行流程(代码偏长，故删除大量细节代码)。
void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
robj *storekey = NULL;
int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */
/* 依据key找找到对应的zojb */
robj *zobj = NULL;
if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
checkType(c, zobj, OBJ_ZSET)) {
return;
}
/* 解析申请中的经纬度值 */
int base_args;
GeoShape shape = {0};
if (flags & RADIUS_COORDS) {
/*
* 各种必选参数的解析，省略细节代码，次要是解析坐标点信息和半径
*/
}
/* 解析所有的可选参数. */
int withdist = 0, withhash = 0, withcoords = 0;
int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
int sort = SORT_NONE;
int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
long long count = 0; /* Max number of results to return. 0 means unlimited. */
if (c->argc > base_args) {
/*
* 各种可选参数的解析，省略细节代码
*/
}
/* Get all neighbor geohash boxes for our radius search
* 获取到要查找范畴内所有的9个geo邻域 */
GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(&shape);
/* 创立geoArray存储后果列表 */
geoArray *ga = geoArrayCreate();
/* 扫描9个区域中是否有满足条的点，有就放到geoArray中 */
membersOfAllNeighbors(zobj, georadius, &shape, ga, any ? count : 0);
/* 如果没有匹配后果，返回空对象 */
if (ga->used == 0 && storekey == NULL) {
addReply(c,shared.emptyarray);
geoArrayFree(ga);
return;
}
long result_length = ga->used;
long returned_items = (count == 0 || result_length < count) ?
result_length : count;
long option_length = 0;
/*
* 后续一些参数逻辑，比方解决排序，存储……
*/
// 开释geoArray占用的空间
geoArrayFree(ga);
}上述代码删减了大量细节，有趣味的同学能够自行查阅。不过能够看出georadius的整体流程十分清晰。
- 解析申请参数。
- 计算指标坐标所在的geohash和8个街坊。
- 在zset中查找这9个区域中满足间隔限度的所有点集。
- 解决排序等后续逻辑。
- 清理长期存储空间。
结语
因为文章篇幅无限，而且着重解说了geohash的实现，并未开展解说redis中geo相干的各种细节，如读者有趣味能够具体浏览redis中的src/geo.c理解各类细节。
参考资料
- wikipedia geohash
- Geohash算法原理及实现
本文是Redis源码分析系列博文，同时也有与之对应的Redis中文正文版，有想深刻学习Redis的同学，欢送star和关注。
Redis中文注解版仓库：https://github.com/xindoo/Redis
Redis源码分析专栏：https://zxs.io/s/1h
发表回复