Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1874942
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: NOSQL

2020-05-10 22:48:33

补个坑,最近又发现这么个家伙,拿出来写写
redis当中的使用geo这个模块来实现地理位置的搜索功能,其主要的数据结构如下:

点击(此处)折叠或打开

  1. typedef struct {
  2.     uint64_t bits; // hash值
  3.     uint8_t step;// 精度
  4. } GeoHashBits;// 根据输入的经纬度处理得来

  5. typedef struct {
  6.     double min;
  7.     double max;
  8. } GeoHashRange;

  9. typedef struct {
  10.     GeoHashBits hash;
  11.     GeoHashRange longitude;
  12.     GeoHashRange latitude;
  13. } GeoHashArea;// 以经纬度的范围以及中心点形成的圆

  14. typedef struct {
  15.     GeoHashBits north;
  16.     GeoHashBits east;
  17.     GeoHashBits west;
  18.     GeoHashBits south;
  19.     GeoHashBits north_east;
  20.     GeoHashBits south_east;
  21.     GeoHashBits north_west;
  22.     GeoHashBits south_west;
  23. } 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当中:

点击(此处)折叠或打开

  1. /* GEOADD key long lat name [long2 lat2 name2 ... longN latN nameN] */
  2. void geoaddCommand(client *c) {
  3.     /* Check arguments number for sanity. */
  4.     if ((c->argc - 2) % 3 != 0) {
  5.         /* Need an odd number of arguments if we got this far... */
  6.         addReplyError(c, "syntax error. Try GEOADD key [x1] [y1] [name1] "
  7.                          "[x2] [y2] [name2] ... ");
  8.         return;
  9.     }

  10.     int elements = (c->argc - 2) / 3;
  11.     int argc = 2+elements*2; /* ZADD key score ele ... */
  12.     robj **argv = zcalloc(argc*sizeof(robj*));
  13.     argv[0] = createRawStringObject("zadd",4);
  14.     argv[1] = c->argv[1]; /* key */
  15.     incrRefCount(argv[1]);

  16.     /* Create the argument vector to call ZADD in order to add all
  17.      * the score,value pairs to the requested zset, where score is actually
  18.      * an encoded version of lat,long. */
  19.     int i;
  20.     for (i = 0; i < elements; i++) {
  21.         double xy[2];

  22.         if (extractLongLatOrReply(c, (c->argv+2)+(i*3),xy) == C_ERR) {
  23.             for (i = 0; i < argc; i++)
  24.                 if (argv[i]) decrRefCount(argv[i]);
  25.             zfree(argv);
  26.             return;
  27.         }

  28.         /* Turn the coordinates into the score of the element. */
  29.         GeoHashBits hash;
  30.         geohashEncodeWGS84(xy[0], xy[1], GEO_STEP_MAX, &hash);
  31.         GeoHashFix52Bits bits = geohashAlign52Bits(hash);
  32.         robj *score = createObject(OBJ_STRING, sdsfromlonglong(bits));
  33.         robj *val = c->argv[2 + i * 3 + 2];
  34.         argv[2+i*2] = score;
  35.         argv[3+i*2] = val;
  36.         incrRefCount(val);
  37.     }

  38.     /* Finally call ZADD that will do the work for us. */
  39.     replaceClientCommandVector(c,argc,argv);
  40.     zaddCommand(c);
  41. }
GEORADIUS:
其命令形式:
GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
其主要的逻辑在下面的函数当中:
1.  根据其输入的半径,确定精度,根据其输入的经纬度,确定位置中心
2. 计算当前圆形覆盖面的外接矩形以及对应的9宫格
3. 遍历key对应的zset当中9宫格内的元素,满足条件的返回给客户端

(这里不得不感叹一下,这个hash真的是牛,只要直接对齐大致就能找到对应的上下左右边界范围,真的是666~~~)

点击(此处)折叠或打开

  1. void georadiusGeneric(client *c, int flags) {
  2.     robj *key = c->argv[1];
  3.     robj *storekey = NULL;
  4.     int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */

  5.     /* Look up the requested zset */
  6.     robj *zobj = NULL;
  7.     if ((zobj = lookupKeyReadOrReply(c, key, shared.emptymultibulk)) == NULL ||
  8.         checkType(c, zobj, OBJ_ZSET)) {
  9.         return;
  10.     }

  11.     /* Find long/lat to use for radius search based on inquiry type */
  12.     int base_args;
  13.     double xy[2] = { 0 };
  14.     if (flags & RADIUS_COORDS) {
  15.         base_args = 6;
  16.         if (extractLongLatOrReply(c, c->argv + 2, xy) == C_ERR)
  17.             return;
  18.     } else if (flags & RADIUS_MEMBER) {
  19.         base_args = 5;
  20.         robj *member = c->argv[2];
  21.         if (longLatFromMember(zobj, member, xy) == C_ERR) {
  22.             addReplyError(c, "could not decode requested zset member");
  23.             return;
  24.         }
  25.     } else {
  26.         addReplyError(c, "Unknown georadius search type");
  27.         return;
  28.     }

  29.     /* Extract radius and units from arguments */
  30.     double radius_meters = 0, conversion = 1;
  31.     if ((radius_meters = extractDistanceOrReply(c, c->argv + base_args - 2,
  32.                                                 &conversion)) < 0) {
  33.         return;
  34.     }

  35.     /* Discover and populate all optional parameters. */
  36.     int withdist = 0, withhash = 0, withcoords = 0;
  37.     int sort = SORT_NONE;
  38.     long long count = 0;
  39.     if (c->argc > base_args) {
  40.         int remaining = c->argc - base_args;
  41.         for (int i = 0; i < remaining; i++) {
  42.             char *arg = c->argv[base_args + i]->ptr;
  43.             if (!strcasecmp(arg, "withdist")) {
  44.                 withdist = 1;
  45.             } else if (!strcasecmp(arg, "withhash")) {
  46.                 withhash = 1;
  47.             } else if (!strcasecmp(arg, "withcoord")) {
  48.                 withcoords = 1;
  49.             } else if (!strcasecmp(arg, "asc")) {
  50.                 sort = SORT_ASC;
  51.             } else if (!strcasecmp(arg, "desc")) {
  52.                 sort = SORT_DESC;
  53.             } else if (!strcasecmp(arg, "count") && (i+1) < remaining) {
  54.                 if (getLongLongFromObjectOrReply(c, c->argv[base_args+i+1],
  55.                     &count, NULL) != C_OK) return;
  56.                 if (count <= 0) {
  57.                     addReplyError(c,"COUNT must be > 0");
  58.                     return;
  59.                 }
  60.                 i++;
  61.             } else if (!strcasecmp(arg, "store") &&
  62.                        (i+1) < remaining &&
  63.                        !(flags & RADIUS_NOSTORE))
  64.             {
  65.                 storekey = c->argv[base_args+i+1];
  66.                 storedist = 0;
  67.                 i++;
  68.             } else if (!strcasecmp(arg, "storedist") &&
  69.                        (i+1) < remaining &&
  70.                        !(flags & RADIUS_NOSTORE))
  71.             {
  72.                 storekey = c->argv[base_args+i+1];
  73.                 storedist = 1;
  74.                 i++;
  75.             } else {
  76.                 addReply(c, shared.syntaxerr);
  77.                 return;
  78.             }
  79.         }
  80.     }

  81.     /* Trap options not compatible with STORE and STOREDIST. */
  82.     if (storekey && (withdist || withhash || withcoords)) {
  83.         addReplyError(c,
  84.             "STORE option in GEORADIUS is not compatible with "
  85.             "WITHDIST, WITHHASH and WITHCOORDS options");
  86.         return;
  87.     }

  88.     /* COUNT without ordering does not make much sense, force ASC
  89.      * ordering if COUNT was specified but no sorting was requested. */
  90.     if (count != 0 && sort == SORT_NONE) sort = SORT_ASC;

  91.     /* Get all neighbor geohash boxes for our radius search */
  92.     GeoHashRadius georadius =
  93.         geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);

  94.     /* Search the zset for all matching points */
  95.     geoArray *ga = geoArrayCreate();
  96.     membersOfAllNeighbors(zobj, georadius, xy[0], xy[1], radius_meters, ga);

  97.     /* If no matching results, the user gets an empty reply. */
  98.     if (ga->used == 0 && storekey == NULL) {
  99.         addReply(c, shared.emptymultibulk);
  100.         geoArrayFree(ga);
  101.         return;
  102.     }

  103.     long result_length = ga->used;
  104.     long returned_items = (count == 0 || result_length < count) ?
  105.                           result_length : count;
  106.     long option_length = 0;

  107.     /* Process [optional] requested sorting */
  108.     if (sort == SORT_ASC) {
  109.         qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_asc);
  110.     } else if (sort == SORT_DESC) {
  111.         qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_desc);
  112.     }

  113.     if (storekey == NULL) {
  114.         /* No target key, return results to user. */

  115.         /* Our options are self-contained nested multibulk replies, so we
  116.          * only need to track how many of those nested replies we return. */
  117.         if (withdist)
  118.             option_length++;

  119.         if (withcoords)
  120.             option_length++;

  121.         if (withhash)
  122.             option_length++;

  123.         /* The multibulk len we send is exactly result_length. The result is
  124.          * either all strings of just zset members *or* a nested multi-bulk
  125.          * reply containing the zset member string _and_ all the additional
  126.          * options the user enabled for this request. */
  127.         addReplyMultiBulkLen(c, returned_items);

  128.         /* Finally send results back to the caller */
  129.         int i;
  130.         for (i = 0; i < returned_items; i++) {
  131.             geoPoint *gp = ga->array+i;
  132.             gp->dist /= conversion; /* Fix according to unit. */

  133.             /* If we have options in option_length, return each sub-result
  134.              * as a nested multi-bulk. Add 1 to account for result value
  135.              * itself. */
  136.             if (option_length)
  137.                 addReplyMultiBulkLen(c, option_length + 1);

  138.             addReplyBulkSds(c,gp->member);
  139.             gp->member = NULL;

  140.             if (withdist)
  141.                 addReplyDoubleDistance(c, gp->dist);

  142.             if (withhash)
  143.                 addReplyLongLong(c, gp->score);

  144.             if (withcoords) {
  145.                 addReplyMultiBulkLen(c, 2);
  146.                 addReplyHumanLongDouble(c, gp->longitude);
  147.                 addReplyHumanLongDouble(c, gp->latitude);
  148.             }
  149.         }
  150.     } else {
  151.         /* Target key, create a sorted set with the results. */
  152.         robj *zobj;
  153.         zset *zs;
  154.         int i;
  155.         size_t maxelelen = 0;

  156.         if
阅读(2154) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~