Chinaunix首页 | 论坛 | 博客

猫尾八

首页　| 　博文目录　| 　关于我

StolennnXB

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

90后空巢老码农

文章分类

全部博文（184）

文章存档

2021年（26）

2020年（56）

2019年（54）

2018年（47）

2017年（1）

我的朋友
最近访客
推荐博文
相关博文
redis当中的geohash——空间搜索

分类： NOSQL

2020-05-10 22:48:33

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

点击(此处)折叠或打开

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

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

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

  17. typedef struct {
  18.     GeoHashBits north;
  19.     GeoHashBits east;
  20.     GeoHashBits west;
  21.     GeoHashBits south;
  22.     GeoHashBits north_east;
  23.     GeoHashBits south_east;
  24.     GeoHashBits north_west;
  25.     GeoHashBits south_west;
  26. } 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.     }

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

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

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

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

  43.     /* Finally call ZADD that will do the work for us. */
  44.     replaceClientCommandVector(c,argc,argv);
  45.     zaddCommand(c);
  46. }
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. */

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

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

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

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

  86.     /* Trap options not compatible with STORE and STOREDIST. */
  87.     if (storekey && (withdist || withhash || withcoords)) {
  88.         addReplyError(c,
  89.             "STORE option in GEORADIUS is not compatible with "
  90.             "WITHDIST, WITHHASH and WITHCOORDS options");
  91.         return;
  92.     }

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

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

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

  106.     /* If no matching results, the user gets an empty reply. */
  107.     if (ga->used == 0 && storekey == NULL) {
  108.         addReply(c, shared.emptymultibulk);
  109.         geoArrayFree(ga);
  110.         return;
  111.     }

  113.     long result_length = ga->used;
  114.     long returned_items = (count == 0 || result_length < count) ?
  115.                           result_length : count;
  116.     long option_length = 0;

  118.     /* Process [optional] requested sorting */
  119.     if (sort == SORT_ASC) {
  120.         qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_asc);
  121.     } else if (sort == SORT_DESC) {
  122.         qsort(ga->array, result_length, sizeof(geoPoint), sort_gp_desc);
  123.     }

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

  128.         /* Our options are self-contained nested multibulk replies, so we
  129.          * only need to track how many of those nested replies we return. */
  130.         if (withdist)
  131.             option_length++;

  133.         if (withcoords)
  134.             option_length++;

  136.         if (withhash)
  137.             option_length++;

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

  145.         /* Finally send results back to the caller */
  146.         int i;
  147.         for (i = 0; i < returned_items; i++) {
  148.             geoPoint *gp = ga->array+i;
  149.             gp->dist /= conversion; /* Fix according to unit. */

  151.             /* If we have options in option_length, return each sub-result
  152.              * as a nested multi-bulk. Add 1 to account for result value
  153.              * itself. */
  154.             if (option_length)
  155.                 addReplyMultiBulkLen(c, option_length + 1);

  157.             addReplyBulkSds(c,gp->member);
  158.             gp->member = NULL;

  160.             if (withdist)
  161.                 addReplyDoubleDistance(c, gp->dist);

  163.             if (withhash)
  164.                 addReplyLongLong(c, gp->score);

  166.             if (withcoords) {
  167.                 addReplyMultiBulkLen(c, 2);
  168.                 addReplyHumanLongDouble(c, gp->longitude);
  169.                 addReplyHumanLongDouble(c, gp->latitude);
  170.             }
  171.         }
  172.     } else {
  173.         /* Target key, create a sorted set with the results. */
  174.         robj *zobj;
  175.         zset *zs;
  176.         int i;
  177.         size_t maxelelen = 0;

  179.         if
阅读(2165) | 评论(0) | 转发(0) |
0

上一篇：redis当中的布隆过滤器

下一篇：gdb相关调试命令

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6