乐趣区

IM里附近的人功能实现原理是什么如何高效率地实现它

jiezi

1、引言

基本上以陌生人社交为主的 IM 产品里，都会增加“附近的人”、“附近的 xxx”这种以 LBS（地理位置）为导向的产品特色（微信这个熟人社交产品里为啥也有“附近的人”？这当然是历史原因了，微信当初还不是想借此引流嘛。。。），因为“附近的 xxx”这种类似功能在产品运营早期，对于种子用户的积累有很大帮助（必竟某种需求，对于人类来说，是上帝赋予的最原始冲动，你懂的 …）。

比如下图中的几款主流移动端 IM 中的“附近的 xxx”功能：

那么，对于很多即时通讯（IM）的开发者初学者来说，“附近的人”或者类似功能，在技术实现上还有点摸不着头脑。本文将简要的为你讲解“附近的人”的基本理论原理，并以 Redis 的 GEO 系列地理位置操作指令为例，理论联系实际地为你讲解它们是如何被高效实现的。

阅读提示：本文适合有一定 Redis 使用经验的服务器后端开发人员阅读，IM 移动客户端开发人员没有太多阅读的必要（理论原理倒是可以知道一下），必竟“附近的 xxx”功能主要工作在服务端，而不在客户端。

学习交流：

– 即时通讯 / 推送技术开发交流 5 群：215477170[推荐]
– 移动端 IM 开发入门文章：《新手入门一篇就够：从零开发移动端 IM》

（本文同步发布于：http://www.52im.net/thread-2827-1-1.html）

2、IM 开发干货系列文章

本文是系列文章中的第 19 篇，总目录如下：

《IM 消息送达保证机制实现 (一)：保证在线实时消息的可靠投递》
《IM 消息送达保证机制实现(二)：保证离线消息的可靠投递》
《如何保证 IM 实时消息的“时序性”与“一致性”？》
《IM 单聊和群聊中的在线状态同步应该用“推”还是“拉”？》
《IM 群聊消息如此复杂，如何保证不丢不重？》
《一种 Android 端 IM 智能心跳算法的设计与实现探讨（含样例代码）》
《移动端 IM 登录时拉取数据如何作到省流量？》
《通俗易懂：基于集群的移动端 IM 接入层负载均衡方案分享》
《浅谈移动端 IM 的多点登陆和消息漫游原理》
《IM 开发基础知识补课(一)：正确理解前置 HTTP SSO 单点登陆接口的原理》
《IM 开发基础知识补课(二)：如何设计大量图片文件的服务端存储架构？》
《IM 开发基础知识补课(三)：快速理解服务端数据库读写分离原理及实践建议》
《IM 开发基础知识补课(四)：正确理解 HTTP 短连接中的 Cookie、Session 和 Token》
《IM 群聊消息的已读回执功能该怎么实现？》
《IM 群聊消息究竟是存 1 份(即扩散读) 还是存多份(即扩散写)？》
《IM 开发基础知识补课(五)：通俗易懂，正确理解并用好 MQ 消息队列》
《一个低成本确保 IM 消息时序的方法探讨》
《IM 开发基础知识补课(六)：数据库用 NoSQL 还是 SQL？读这篇就够了！》
《IM 里“附近的人”功能实现原理是什么？如何高效率地实现它？》（本文）

3、“附近的人”功能原理

其实，“附近的人”功能原理并不复杂。

它需要做以下两件事情：

1）所有使用该 IM 产品的人，在使用“附近的人”功能前提交自已的地理位置；
2）根据“我”的地理位置，计算出别人跟我的距离；
3）将第 2 步中计算出的距离由近及远，进行排序。

具体在产品技术上的实现原理，也很容易理解：

1）现在移动端（ios、android 等），通过系统的 API 很容易抓到用户当前的位置（即经纬度数据）；
2）根据第 1 步中的经纬度数据，很容易计算出两个点之间的距离（计算公式原理，可以百度一下，我的几何和数学知识都还给老师了，给你讲不了）；
3）对第 2 步中的计算结果排序就更简单了，没什么好提的。

对于 IM 新手来说，可能对于第 2 步中的根据经纬度数据计算出两点距离，觉得有点难度，实际上根据数据公式（自已百度一下吧，有点复杂，哥不贴了），用代码来实现，只有短短的十来行代码。

下面是一个简单的 Java 版实现：

/**
 * 计算地球上任意两点 (经纬度) 距离    
 *     
 * @param long1 第一点经度    
 * @param lat1 第一点纬度    
 * @param long2 第二点经度    
 * @param lat2 第二点纬度    
 * @return 返回距离 单位：米
 */
public static double Distance(double long1, double lat1, double long2, double lat2)
{
    double a, b, R;
    R = 6378137; // 地球半径        
    lat1 = lat1 * Math.PI / 180.0;
    lat2 = lat2 * Math.PI / 180.0;
    a = lat1 – lat2;
    b = (long1 – long2) * Math.PI / 180.0;
    double d;
    double sa2, sb2;
    sa2 = Math.sin(a / 2.0);
    sb2 = Math.sin(b / 2.0);
    d = 2* R * Math.asin(Math.sqrt(sa2 * sa2 + Math.cos(lat1) * Math.cos(lat2) * sb2 * sb2));
    return d;
}

在进行代码测试的时候，可以结合这个在线工具网页进行结果检验：http://www.hhlink.com/%E7%BB%8F%E7%BA%AC%E5%BA%A6/

嗯，看起来好简单！

4、自已从零实现的话，没有难度吗？

嗯，通过上一节的原理讲解，目前为止，看起来确实很简单。

但，如果自已从零实现的话，对于 IM 这种高性能、高并发场景来说，确实有一点难度，难不在移动客户端，而是在服务端。

技术难点主要包括：

1）如何高效地进行两点距离的计算，对于高并发服务端来说，像上一节中的代码那样，一个一个计算，还是有点不高效；
2）如何高效地进行地理围栏的圈定（难道是把所有当前在线的用户，离我的距离都一一算一遍，然后按距离进行筛选？那性能岂不是噩梦？）。

那，有救吗？答案是有！继续看下一节。

5、Redis 里的 GEO 地理位置相关指令，就能很好的上述问题

针对“附近的人”这一位置服务领域的应用场景，服务端高性能场景下，常见的可使用 PG、MySQL 和 MongoDB 等多种 DB 的空间索引进行实现。

而 Redis 另辟蹊径，结合其有序队列 zset 以及 geohash 编码，实现了空间搜索功能，且拥有极高的运行效率。

要提供完整的“附近的人”这样的功能或服务，最基本的是要实现“增”、“删”、“查”的功能。本文余下的文字，以下将分别进行介绍，其中会重点对查询功能进行解析。并将从 Redis 源码角度对其算法原理进行解析，并推算查询时间复杂度。

Redis 相关资源：

1）Redis 官网：https://redis.io
2）Redis 的 GEO 指令说明（英文）：https://redis.io/commands
3）Redis 的 GEO 指令说明（中文）：http://redisdoc.com/geo/geoadd.html

6、Redis 的 GEO 地理位置操作指令

自 Redis 3.2 版 开始，Redis 基于 geohash 和有序集合提供了地理位置相关功能。

Redis 中的 6 个地理位置相关操作指令（见官方文档）：

Redis Geo 模块的 6 个指令用途说明：

1）GEOADD：将给定的位置对象（纬度、经度、名字）添加到指定的 key；
2）GEOPOS：从 key 里面返回所有给定位置对象的位置（经度和纬度）；
3）GEODIST：返回两个给定位置之间的距离；
4）GEOHASH：返回一个或多个位置对象的 Geohash 表示；
5）GEORADIUS：以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象；
6）GEORADIUSBYMEMBER：以给定的位置对象为中心，返回与其距离不超过给定最大距离的所有位置对象。

其中，组合使用 GEOADD 和 GEORADIUS 可实现“附近的人”中“增”和“查”的基本功能。要实现类似于微信中“附近的人”功能，可直接使用 GEORADIUSBYMEMBER 命令。

其中“给定的位置对象”即为用户本人，搜索的对象为其他用户。不过本质上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，即先查找用户位置再通过该位置搜索附近满足位置相互距离条件的其他用户对象。

使用时的注意点：

1）Redis GEO 操作中只包含了“增”和“查”的操作，并无专门“删除”命令。主要是因为 Redis 内部使用有序集合 (zset) 保存位置对象，可用 zrem 删除；
2）在 Redis 源码 geo.c 的文件注释中，只说明了该文件为 GEOADD、GEORADIUS 和 GEORADIUSBYMEMBER 的实现；
3）从侧面看出其他三个命令为辅助命令。

本文的余下内容，将会从源码角度入手，着生理地对 GEOADD 和 GEORADIUS 命令进行分析，剖析其算法原理。

7、Redis 的 GEOADD 指令是如何高效实现的

7.1 使用方式

GEOADD key longitude latitude member [longitude latitude member …]

以上命令，将给定的位置对象（纬度、经度、名字）添加到指定的 key。

其中，key 为集合名称，member 为该经纬度所对应的对象。在实际运用中，当所需存储的对象数量过多时，可通过设置多 key(如一个省一个 key)的方式对对象集合变相做 sharding，避免单集合数量过多。

成功插入后的返回值：

(integer) N

其中 N 为成功插入的个数。

7.2 源码分析

/* 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;
    }
// 参数提取 Redis
    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;
        }
    // 将经纬度转换为 52 位的 geohash 作为分值 & 提取对象名称
        /* 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);
    }
// 调用 zadd 命令，存储转化好的对象
    /* Finally call ZADD that will do the work for us. */
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

通过 Redis 源码分析可以看出，Redis 内部使用有序集合 (zset) 保存位置对象，有序集合中每个元素都是一个带位置的对象，元素的 score 值为其经纬度对应的 52 位的 geohash 值：

1）double 类型精度为 52 位；

2）geohash 是以 base32 的方式编码，52bits 最高可存储 10 位 geohash 值，对应地理区域大小为 0.6*0.6 米的格子。换句话说经 Redis geo 转换过的位置理论上会有约 0.3*1.414=0.424 米的误差。

7.3 算法小结

简单总结下 GEOADD 命令都干了啥：

1）参数提取和校验；

2）将入参经纬度转换为 52 位的 geohash 值（score）；

3）调用 ZADD 命令将 member 及其对应的 score 存入集合 key 中。

8、Redis 的 GEORADIUS 指令是如何高效实现的

8.1 使用方式

1GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]

以上指令，将以给定的经纬度为中心，返回目标集合中与中心的距离不超过给定最大距离的所有位置对象。

范围单位：m | km | ft | mi –> 米 | 千米 | 英尺 | 英里
额外参数：
– WITHDIST：在返回位置对象的同时，将位置对象与中心之间的距离也一并返回。距离的单位和用户给定的范围单位保持一致。
– WITHCOORD：将位置对象的经度和维度也一并返回。
– WITHHASH：以 52 位有符号整数的形式，返回位置对象经过原始 geohash 编码的有序集合分值。这个选项主要用于底层应用或者调试，实际中的作用并不大。
– ASC|DESC：从近到远返回位置对象元素 | 从远到近返回位置对象元素。
– COUNT count：选取前 N 个匹配位置对象元素。（不设置则返回所有元素）
– STORE key：将返回结果的地理位置信息保存到指定 key。
– STORedisT key：将返回结果离中心点的距离保存到指定 key。

由于 STORE 和 STORedisT 两个选项的存在，GEORADIUS 和 GEORADIUSBYMEMBER 命令在技术上会被标记为写入命令，从而只会查询（写入）主实例，QPS 过高时容易造成主实例读写压力过大。

为解决这个问题，在 Redis 3.2.10 和 Redis 4.0.0 中，分别新增了 GEORADIUS_RO 和 GEORADIUSBYMEMBER_RO 两个只读命令。

不过，在实际开发中笔者发现 在 java package Redis.clients.jedis.params.geo 的 GeoRadiusParam 参数类中并不包含 STORE 和 STORedisT 两个参数选项，在调用 georadius 时是否真的只查询了主实例，还是进行了只读封装。感兴趣的朋友可以自己研究下。

成功查询后的返回值：

不带 WITH 限定，返回一个 member list，如：[“member1″,”member2″,”member3”]

带 WITH 限定，member list 中每个 member 也是一个嵌套 list，如：

[
        [“member1”, distance1, [longitude1, latitude1]]
        [“member2”, distance2, [longitude2, latitude2]]
]

8.2 源码分析

此段源码较长，看不下去的可直接看中文注释，或直接跳到小结部分。

/* GEORADIUS key x y radius unit [WITHDIST] [WITHHASH] [WITHCOORD] [ASC|DESC]
 *                               [COUNT count] [STORE key] [STORedisT key]
 * GEORADIUSBYMEMBER key member radius unit … options … */
voidgeoradiusGeneric(client *c, intflags) {
    robj *key = c->argv[1];
    robj *storekey = NULL;
    int stoRedist = 0; /* 0 for STORE, 1 for STORedisT. */
// 根据 key 获取有序集合
    robj *zobj = NULL;
    if((zobj = lookupKeyReadOrReply(c, key, shared.null[c->resp])) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }
// 根据用户输入（经纬度 /member）确认中心点经纬度
    int base_args;
    double xy[2] = {0};
    if(flags & RADIUS_COORDS) {
                ……
    }
// 获取查询范围距离
    double radius_meters = 0, conversion = 1;
    if((radius_meters = extractDistanceOrReply(c, c->argv + base_args – 2,
                                                &conversion)) < 0) {
        return;
    }
// 获取可选参数（withdist、withhash、withcoords、sort、count）
    int withdist = 0, withhash = 0, withcoords = 0;
    int sort = SORT_NONE;
    long long count = 0;
    if(c->argc > base_args) {
        … …
    }
// 获取 STORE 和 STORedisT 参数
    if(storekey && (withdist || withhash || withcoords)) {
        addReplyError(c,
            “STORE option in GEORADIUS is not compatible with “
            “WITHDIST, WITHHASH and WITHCOORDS options”);
        return;
    }
// 设定排序
    if(count != 0 && sort == SORT_NONE) sort = SORT_ASC;
// 利用中心点和半径计算目标区域范围
    GeoHashRadius georadius =
        geohashGetAreasByRadiusWGS84(xy[0], xy[1], radius_meters);
// 对中心点及其周围 8 个 geohash 网格区域进行查找，找出范围内元素对象
    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) {
        addReplyNull(c);
        geoArrayFree(ga);
        return;
    }
// 一些返回值的设定和返回
    ……
    geoArrayFree(ga);
}

上文代码中最核心的步骤有两个：

一是“计算中心点范围；
二是“对中心点及其周围 8 个 geohash 网格区域进行查找”。

对应的是 geohashGetAreasByRadiusWGS84 和 membersOfAllNeighbors 两个函数。

我们依次来看。

计算中心点范围：

// geohash_helper.c
GeoHashRadius geohashGetAreasByRadiusWGS84(double longitude, double latitude,
                                           double radius_meters) {
    return geohashGetAreasByRadius(longitude, latitude, radius_meters);
}
// 返回能够覆盖目标区域范围的 9 个 geohashBox
GeoHashRadius geohashGetAreasByRadius(double longitude, double latitude, double radius_meters) {
// 一些参数设置
    GeoHashRange long_range, lat_range;
    GeoHashRadius radius;
    GeoHashBits hash;
    GeoHashNeighbors neighbors;
    GeoHashArea area;
    double min_lon, max_lon, min_lat, max_lat;
    double bounds[4];
    int steps;
// 计算目标区域外接矩形的经纬度范围（目标区域为：以目标经纬度为中心，半径为指定距离的圆）
    geohashBoundingBox(longitude, latitude, radius_meters, bounds);
    min_lon = bounds[0];
    min_lat = bounds[1];
    max_lon = bounds[2];
    max_lat = bounds[3];
// 根据目标区域中心点纬度和半径，计算带查询的 9 个搜索框的 geohash 精度（位）
// 这里用到 latitude 主要是针对极地的情况对精度进行了一些调整（纬度越高，位数越小）
    steps = geohashEstimateStepsByRadius(radius_meters,latitude);
// 设置经纬度最大最小值：-180<=longitude<=180, -85<=latitude<=85
    geohashGetCoordRange(&long_range,&lat_range);
// 将待查经纬度按指定精度（steps）编码成 geohash 值
    geohashEncode(&long_range,&lat_range,longitude,latitude,steps,&hash);
// 将 geohash 值在 8 个方向上进行扩充，确定周围 8 个 Box（neighbors）
    geohashNeighbors(&hash,&neighbors);
// 根据 hash 值确定 area 经纬度范围
    geohashDecode(long_range,lat_range,hash,&area);
// 一些特殊情况处理
    ……
// 构建并返回结果   
    radius.hash = hash;
    radius.neighbors = neighbors;
    radius.area = area;
    return radius;
}

对中心点及其周围 8 个 geohash 网格区域进行查找:

// geo.c
// 在 9 个 hashBox 中获取想要的元素
int membersOfAllNeighbors(robj *zobj, GeoHashRadius n, double lon, double lat, double radius, geoArray *ga) {
    GeoHashBits neighbors[9];
    unsigned int i, count = 0, last_processed = 0;
    int debugmsg = 0;
// 获取 9 个搜索 hashBox
    neighbors[0] = n.hash;
    ……
    neighbors[8] = n.neighbors.south_west;
// 在每个 hashBox 中搜索目标点
    for(i = 0; i < sizeof(neighbors) / sizeof(*neighbors); i++) {
        if(HASHISZERO(neighbors[i])) {
            if(debugmsg) D(“neighbors[%d] is zero”,i);
            continue;
        }
        // 剔除可能的重复 hashBox (搜索半径 >5000KM 时可能出现)
        if(last_processed &&
            neighbors[i].bits == neighbors[last_processed].bits &&
            neighbors[i].step == neighbors[last_processed].step)
        {
            continue;
        }
        // 搜索 hashBox 中满足条件的对象   
        count += membersOfGeoHashBox(zobj, neighbors[i], ga, lon, lat, radius);
        last_processed = i;
    }
    returncount;
}
int membersOfGeoHashBox(robj *zobj, GeoHashBits hash, geoArray *ga, double lon, double lat, double radius) {
// 获取 hashBox 内的最大、最小 geohash 值（52 位）
    GeoHashFix52Bits min, max;
    scoresOfGeoHashBox(hash,&min,&max);
// 根据最大、最小 geohash 值筛选 zobj 集合中满足条件的点
    return geoGetPointsInRange(zobj, min, max, lon, lat, radius, ga);
}
int geoGetPointsInRange(robj *zobj, double min, double max, double lon, double lat, double radius, geoArray *ga) {
// 搜索 Range 的参数边界设置（即 9 个 hashBox 其中一个的边界范围）
    zrangespec range = {.min = min, .max = max, .minex = 0, .maxex = 1};
    size_torigincount = ga->used;
    sds member;
// 搜索集合 zobj 可能有 ZIPLIST 和 SKIPLIST 两种编码方式，这里以 SKIPLIST 为例，逻辑是一样的
    if(zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        ……
    } else if(zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplist *zsl = zs->zsl;
        zskiplistNode *ln;
        // 获取在 hashBox 范围内的首个元素（跳表数据结构，效率可比拟于二叉查找树），没有则返 0
        if((ln = zslFirstInRange(zsl, &range)) == NULL) {
            /* Nothing exists starting at our min.  No results. */
            return 0;
        }
        // 从首个元素开始遍历集合
        while(ln) {
            sds ele = ln->ele;
                // 遍历元素超出 range 范围则 break
            /* Abort when the node is no longer in range. */
            if(!zslValueLteMax(ln->score, &range))
                break;
                // 元素校验（计算元素与中心点的距离）
            ele = sdsdup(ele);
            if(geoAppendIfWithinRadius(ga,lon,lat,radius,ln->score,ele)
                == C_ERR) sdsfree(ele);
            ln = ln->level[0].forward;
        }
    }
    returnga->used – origincount;
}
int geoAppendIfWithinRadius(geoArray *ga, double lon, double lat, double radius, double score, sds member) {
    double distance, xy[2];
// 解码错误, 返回 error
    if(!decodeGeohash(score,xy)) returnC_ERR; /* Can’t decode. */
// 最终距离校验(计算球面距离 distance 看是否小于 radius)
    if(!geohashGetDistanceIfInRadiusWGS84(lon,lat, xy[0], xy[1],
                                           radius, &distance))
    {
        return C_ERR;
    }
// 构建并返回满足条件的元素
    geoPoint *gp = geoArrayAppend(ga);
    gp->longitude = xy[0];
    gp->latitude = xy[1];
    gp->dist = distance;
    gp->member = member;
    gp->score = score;
    return C_OK;
}

8.3 算法小结

抛开众多可选参数不谈，简单总结下 GEORADIUS 命令是怎么利用 geohash 获取目标位置对象的：

1）参数提取和校验；

2）利用中心点和输入半径计算待查区域范围。这个范围参数包括满足条件的最高的 geohash 网格等级(精度) 以及 对应的能够覆盖目标区域的九宫格位置；（后续会有详细说明）

3）对九宫格进行遍历，根据每个 geohash 网格的范围框选出位置对象。进一步找出与中心点距离小于输入半径的对象，进行返回。

直接描述不太好理解，我们通过如下两张图在对算法进行简单的演示：

如上图所示，令左图的中心为搜索中心，绿色圆形区域为目标区域，所有点为待搜索的位置对象，红色点则为满足条件的位置对象。

在实际搜索时, 首先会根据搜索半径计算 geohash 网格等级（即右图中网格大小等级），并确定九宫格位置（即红色九宫格位置信息）；再依次查找计算九宫格中的点（蓝点和红点）与中心点的距离，最终筛选出距离范围内的点（红点）。

8.4 算法分析

为什么要用这种算法策略进行查询，或者说这种策略的优势在哪，让我们以问答的方式进行分析说明。

为什么要找到满足条件的最高的 geohash 网格等级？为什么用九宫格？

这其实是一个问题，本质上是对所有的元素对象进行了一次初步筛选。在多层 geohash 网格中，每个低等级的 geohash 网格都是由 4 个高一级的网格拼接而成（如下图）。

换句话说，geohash 网格等级越高，所覆盖的地理位置范围就越小。当我们根据输入半径和中心点位置计算出的能够覆盖目标区域的最高等级的九宫格（网格）时，就已经对九宫格外的元素进行了筛除。这里之所以使用九宫格，而不用单个网格，主要原因还是为了避免边界情况，尽可能缩小查询区域范围。试想以 0 经纬度为中心，就算查 1 米范围，单个网格覆盖的话也得查整个地球区域。而向四周八个方向扩展一圈可有效避免这个问题。

如何通过 geohash 网格的范围框选出元素对象？效率如何？

首先在每个 geohash 网格中的 geohash 值都是连续的，有固定范围。所以只要找出有序集合中，处在该范围的位置对象即可。以下是有序集合的跳表数据结构：

其拥有类似二叉查找树的查询效率，操作平均时间复杂性为 O(log(N))。且最底层的所有元素都以链表的形式按序排列。所以在查询时，只要找到集合中处在目标 geohash 网格中的第一个值，后续依次对比即可，不用多次查找。九宫格不能一起查，要一个个遍历的原因也在于九宫格各网格对应的 geohash 值不具有连续性。只有连续了，查询效率才会高，不然要多做许多距离运算。

9、本文小结

综合上述章节，我们从源码角度解析了 Redis Geo 模块中“增（GEOADD）”和“查（GEORADIUS）”的详细过程。并可推算出 Redis 中 GEORADIUS 查找附近的人功能，时间复杂度为：O(N+log(M))。

其中：

1）N 为九宫格范围内的位置元素数量（要算距离）；

2）M 是指定层级格子的数量；

3）log(M)是跳表结构中找到每个格子首元素的时间复杂度（这个过程一般会进行 9 次）。

结合 Redis 本身基于内存的存储特性，在实际使用过程中有非常高的运行效率。

以上，就是本文的全部答案，不知是否对你有帮助！

附录：更多 IM 开发综合文章

《新手入门一篇就够：从零开发移动端 IM》
《移动端 IM 开发者必读(一)：通俗易懂，理解移动网络的“弱”和“慢”》
《移动端 IM 开发者必读(二)：史上最全移动弱网络优化方法总结》
《从客户端的角度来谈谈移动端 IM 的消息可靠性和送达机制》
《现代移动端网络短连接的优化手段总结：请求速度、弱网适应、安全保障》
《腾讯技术分享：社交网络图片的带宽压缩技术演进之路》
《小白必读：闲话 HTTP 短连接中的 Session 和 Token》
《IM 开发基础知识补课：正确理解前置 HTTP SSO 单点登陆接口的原理》
《移动端 IM 中大规模群消息的推送如何保证效率、实时性？》
《移动端 IM 开发需要面对的技术问题》
《开发 IM 是自己设计协议用字节流好还是字符流好？》
《请问有人知道语音留言聊天的主流实现方式吗？》
《通俗易懂：基于集群的移动端 IM 接入层负载均衡方案分享》
《微信对网络影响的技术试验及分析（论文全文）》
《即时通讯系统的原理、技术和应用（技术论文）》
《开源 IM 工程“蘑菇街 TeamTalk”的现状：一场有始无终的开源秀》
《QQ 音乐团队分享：Android 中的图片压缩技术详解（上篇）》
《QQ 音乐团队分享：Android 中的图片压缩技术详解（下篇）》
《腾讯原创分享(一)：如何大幅提升移动网络下手机 QQ 的图片传输速度和成功率》
《腾讯原创分享(二)：如何大幅压缩移动网络下 APP 的流量消耗（上篇）》
《腾讯原创分享(三)：如何大幅压缩移动网络下 APP 的流量消耗（下篇）》
《如约而至：微信自用的移动端 IM 网络层跨平台组件库 Mars 已正式开源》
《基于社交网络的 Yelp 是如何实现海量用户图片的无损压缩的？》
《腾讯技术分享：腾讯是如何大幅降低带宽和网络流量的(图片压缩篇)》
《腾讯技术分享：腾讯是如何大幅降低带宽和网络流量的(音视频技术篇)》
《字符编码那点事：快速理解 ASCII、Unicode、GBK 和 UTF-8》
《全面掌握移动端主流图片格式的特点、性能、调优等》
《子弹短信光鲜的背后：网易云信首席架构师分享亿级 IM 平台的技术实践》
《IM 开发基础知识补课(五)：通俗易懂，正确理解并用好 MQ 消息队列》
《微信技术分享：微信的海量 IM 聊天消息序列号生成实践（算法原理篇）》
《自已开发 IM 有那么难吗？手把手教你自撸一个 Andriod 版简易 IM (有源码)》
《融云技术分享：解密融云 IM 产品的聊天消息 ID 生成策略》
《适合新手：从零开发一个 IM 服务端（基于 Netty，有完整源码）》
《拿起键盘就是干：跟我一起徒手开发一套分布式 IM 系统》
>> 更多同类文章 ……

（本文同步发布于：http://www.52im.net/thread-2827-1-1.html）

退出移动版