补个坑,最近又发现这么个家伙,拿出来写写
redis当中的使用geo这个模块来实现地理位置的搜索功能,其主要的数据结构如下:
-
typedef struct {
-
uint64_t bits; // hash值
-
uint8_t step;// 精度
-
} GeoHashBits;// 根据输入的经纬度处理得来
-
-
typedef struct {
-
double min;
-
double max;
-
} GeoHashRange;
-
-
typedef struct {
-
GeoHashBits hash;
-
GeoHashRange longitude;
-
GeoHashRange latitude;
-
} GeoHashArea;// 以经纬度的范围以及中心点形成的圆
-
-
typedef struct {
-
GeoHashBits north;
-
GeoHashBits east;
-
GeoHashBits west;
-
GeoHashBits south;
-
GeoHashBits north_east;
-
GeoHashBits south_east;
-
GeoHashBits north_west;
-
GeoHashBits south_west;
-
} GeoHashNeighbors;// 中心点九宫格的8个邻居
其主要的命令有如下几个:
GEOADD:将给定的位置对象(经、纬度)存入指定的key
GEOPOS:从key里面返回所有给定位置对象的位置
GEODIST:返回两个给定位置之间的距离
GEOHASH:返回一个或多个位置对象的Geoash表示
GEORADIUS:以给定的经纬度为中心,返回目标集合中与中心距离不超过半径的对象的位置
GEORADIUSBYMEMBER:以给定的位置对象为中心,返回与其距离不超过半径的对象的位置
这篇文章主要分析GEOADD以及GEORADIUS两个命令是如何实现空间上的查找的:
GEOADD:
其命令形式:
GEOADD key longitude latitude member [longitude latitude member...]
其主要源代码如下,主要思想就是将输入近来的经纬度求hash,并且以hash值为score,member为key,存入key指代的zset当中:
-
/* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
-
void geoaddCommand(client *c) {
-
/* Check arguments number for sanity. */
-
if ((c->argc - 2) % 3 != 0) {
-
/* Need an odd number of arguments if we got this far... */
-
addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] "
-
"[x2] [y2] [name2] ... ");
-
return;
-
}
-
-
int elements = (c->argc - 2) / 3;
-
int argc = 2+elements*2; /* ZADD key score ele ... */
-
robj **argv = zcalloc(argc*sizeof(robj*));
-
argv[0] = createRawStringObject("zadd",4);
-
argv[1] = c->argv[1]; /* key */
-
incrRefCount(argv[1]);
-
-
/* Create the argument vector to call ZADD in order to add all
-
* the score,value pairs to the requested zset, where score is actually
-
* an encoded version of lat,long. */
-
int i;
-
for (i = 0; i < elements; i++) {
-
double xy[2];
-
-
if (extractLongLatOrReply(c, (c->argv+2)+(i*3),xy) == C_ERR) {
-
for (i = 0; i < argc; i++)
-
if (argv[i]) decrRefCount(argv[i]);
-
zfree(argv);
-
return;
-
}
-
-
/* Turn the coordinates into the score of the element. */
-
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[2 + i * 3 + 2];
-
argv[2+i*2] = score;
-
argv[3+i*2] = val;
-
incrRefCount(val);
-
}
-
-
/* Finally call ZADD that will do the work for us. */
-
replaceClientCommandVector(c,argc,argv);
-
zaddCommand(c);
-
}
GEORADIUS:
其命令形式:
GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
其主要的逻辑在下面的函数当中:
1. 根据其输入的半径,确定精度,根据其输入的经纬度,确定位置中心
2. 计算当前圆形覆盖面的外接矩形以及对应的9宫格
3. 遍历key对应的zset当中9宫格内的元素,满足条件的返回给客户端
(这里不得不感叹一下,这个hash真的是牛,只要直接对齐大致就能找到对应的上下左右边界范围,真的是666~~~)
-
void georadiusGeneric(client *c, int flags) {
-
robj *key = c->argv[1];
-
robj *storekey = NULL;
-
int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */
-
-
/* Look up the requested zset */
-
robj *zobj = NULL;
-
if ((zobj = lookupKeyReadOrReply(c, key, shared.emptymultibulk)) == NULL ||
-
checkType(c, zobj, OBJ_ZSET)) {
-
return;
-
}
-
-
/* Find long/lat to use for radius search based on inquiry type */
-
int base_args;
-
double xy[2] = { 0 };
-
if (flags & RADIUS_COORDS) {
-
base_args = 6;
-
if (extractLongLatOrReply(c, c->argv + 2, xy) == C_ERR)
-
return;
-
} else if (flags & RADIUS_MEMBER) {
-
base_args = 5;
-
robj *member = c->argv[2];
-
if (longLatFromMember(zobj, member, xy) == C_ERR) {
-
addReplyError(c, "could not decode requested zset member");
-
return;
-
}
-
} else {
-
addReplyError(c, "Unknown georadius search type");
-
return;
-
}
-
-
/* Extract radius and units from arguments */
-
double radius_meters = 0, conversion = 1;
-
if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
-
&conversion)) < 0) {
-
return;
-
}
-
-
/* Discover and populate all optional parameters. */
-
int withdist = 0, withhash = 0, withcoords = 0;
-
int sort = SORT_NONE;
-
long long count = 0;
-
if (c->argc > base_args) {
-
int remaining = c->argc - base_args;
-
for (int i = 0; i < remaining; i++) {
-
char *arg = c->argv[base_args + i]->ptr;
-
if (!strcasecmp(arg, "withdist")) {
-
withdist = 1;
-
} else if (!strcasecmp(arg, "withhash")) {
-
withhash = 1;
-
} else if (!strcasecmp(arg, "withcoord")) {
-
withcoords = 1;
-
} else if (!strcasecmp(arg, "asc")) {
-
sort = SORT_ASC;
-
} else if (!strcasecmp(arg, "desc")) {
-
sort = SORT_DESC;
-
} else if (!strcasecmp(arg, "count") && (i+1) < remaining) {
-
if (getLongLongFromObjectOrReply(c, c->argv[base_args+i+1],
-
&count, NULL) != C_OK) return;
-
if (count <= 0) {
-
addReplyError(c,"COUNT must be > 0");
-
return;
-
}
-
i++;
-
} else if (!strcasecmp(arg, "store") &&
-
(i+1) < remaining &&
-
!(flags & RADIUS_NOSTORE))
-
{
-
storekey = c->argv[base_args+i+1];
-
storedist = 0;
-
i++;
-
} else if (!strcasecmp(arg, "storedist") &&
-
(i+1) < remaining &&
-
!(flags & RADIUS_NOSTORE))
-
{
-
storekey = c->argv[base_args+i+1];
-
storedist = 1;
-
i++;
-
} else {
-
addReply(c, shared.syntaxerr);
-
return;
-
}
-
}
-
}
-
-
/* Trap options not compatible with STORE and STOREDIST. */
-
if (storekey && (withdist || withhash || withcoords)) {
-
addReplyError(c,
-
"STORE option in GEORADIUS is not compatible with "
-
"WITHDIST, WITHHASH and WITHCOORDS options");
-
return;
-
}
-
-
/* COUNT without ordering does not make much sense, force ASC
-
* ordering if COUNT was specified but no sorting was requested. */
-
if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;
-
-
/* Get all neighbor geohash boxes for our radius search */
-
GeoHashRadius georadius =
-
geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
-
-
/* Search the zset for all matching points */
-
geoArray *ga = geoArrayCreate();
-
membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);
-
-
/* If no matching results, the user gets an empty reply. */
-
if (ga->used == 0 && storekey == NULL) {
-
addReply(c, shared.emptymultibulk);
-
geoArrayFree(ga);
-
return;
-
}
-
-
long result_length = ga->used;
-
long returned_items = (count == 0 || result_length < count) ?
-
result_length : count;
-
long option_length = 0;
-
-
/* Process [optional] requested sorting */
-
if (sort == SORT_ASC) {
-
qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_asc);
-
} else if (sort == SORT_DESC) {
-
qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_desc);
-
}
-
-
if (storekey == NULL) {
-
/* No target key, return results to user. */
-
-
/* Our options are self-contained nested multibulk replies, so we
-
* only need to track how many of those nested replies we return. */
-
if (withdist)
-
option_length++;
-
-
if (withcoords)
-
option_length++;
-
-
if (withhash)
-
option_length++;
-
-
/* The multibulk len we send is exactly result_length. The result is
-
* either all strings of just zset members *or* a nested multi-bulk
-
* reply containing the zset member string _and_ all the additional
-
* options the user enabled for this request. */
-
addReplyMultiBulkLen(c, returned_items);
-
-
/* Finally send results back to the caller */
-
int i;
-
for (i = 0; i < returned_items; i++) {
-
geoPoint *gp = ga->array+i;
-
gp->dist /= conversion; /* Fix according to unit. */
-
-
/* If we have options in option_length, return each sub-result
-
* as a nested multi-bulk. Add 1 to account for result value
-
* itself. */
-
if (option_length)
-
addReplyMultiBulkLen(c, option_length + 1);
-
-
addReplyBulkSds(c,gp->member);
-
gp->member = NULL;
-
-
if (withdist)
-
addReplyDoubleDistance(c, gp->dist);
-
-
if (withhash)
-
addReplyLongLong(c, gp->score);
-
-
if (withcoords) {
-
addReplyMultiBulkLen(c, 2);
-
addReplyHumanLongDouble(c, gp->longitude);
-
addReplyHumanLongDouble(c, gp->latitude);
-
}
-
}
-
} else {
-
/* Target key, create a sorted set with the results. */
-
robj *zobj;
-
zset *zs;
-
int i;
-
size_t maxelelen = 0;
-
-
if
阅读(2154) | 评论(0) | 转发(0) |