Redis系列四 GEO附近的人

来都来了 2020-11-23 16:36:11 ⋅ 693 阅读

GEO算法

GeoHash是一种地址编码方法。将二维的空间经纬度数据编码成一个字符串

地球上的经度范围:[-180, 180],纬度范围:[-90,90]。如果以本初子午线、赤道为界,地球可以分成4个部分。

我们先将平面切割成四个正方形,然后用简单的 01 编码来标识这个四个正方形,最后按照编码的大小将四个正方形连接起来,这样整个平面就转换成了一条Z曲线,变成了一维。
我们递归对每个正方形做同样的操作,递归的层次越深,整个平面就逐渐被Z曲线填充。我们的点也会落在每个小正方形里面,小正方形越小,精度就越高。如下图所示:

第一步: 经纬度转二进制

比如这样一个点(39.923201, 116.390705)

在区间内就是1,否则就是0
依次计算得到二进制数:

39.923201 => 10111000110001111001
116.390705 => 11010010110001000100
 

第二步: 经纬度合并

经度占偶数位,纬度占奇数位,注意,0也是偶数位。

11100 11101 00100 01111 00000 01101 01011 00001
 

第三步: Base32编码

二进制=>十进制=>进行编码即可
wx4g0ec1ebpf

可以在这个网址互相转换,http://geohash.co/;

注意

geohash

  1. GeoHash表示的并不是一个点,而是一个矩形区域
  2. GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索
  3. 编码越长,表示的范围越小,位置也越精确

边缘问题

如图,如果车在红点位置,区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样,最终找到的将是黄点。这就有问题了。

要解决这个问题,很简单,只要再查找周边8个区域内的点,对比距离即可

曲线突变问题

其中0111和1000两个编码非常相近,但它们的实际距离确很远。所以编码相近的两个单位,并不一定真实距离很近,这需要实际计算两个点的距离才行。

iordis代码实现


import * as Redis from "ioredis";

const redis = new Redis();

(async function(){
const key = 'geo:zhubo';
// 1. geoadd 添加 ABC三元素&对应的经纬度
// @ts-ignore
await redis.geoadd(key, [116.48, 39.9, 'A', 116.9, 39.95, 'B', 116.83, 39.01, 'C']);
// @ts-ignore
const dist = await redis.geodist(key, 'A', 'B', 'km');
console.log(`AB之间的距离为${dist}km`);
// @ts-ignore
const pos = await redis.geopos(key, 'A');
console.log(`A的经纬度为${pos}`);
// @ts-ignore
const hash = await redis.geohash(key, 'A');
console.log(`A的hash为${hash}`);
// @ts-ignore
const GEORADIUSBYMEMBER = await redis.georadiusbymember(key, 'A', 300, 'km', 'COUNT', 4, 'asc')
// @ts-ignore
const GEORADIUSBYMEMBER1 = await redis.georadiusbymember(key, 'A', 300, 'km', 'withcoord', 'withdist', 'withhash', 'COUNT', 4, 'asc')
console.log(`A的附近300km, 距离由近到远为${GEORADIUSBYMEMBER}`);
console.log(`A的附近300km, 距离由近到远为${GEORADIUSBYMEMBER1}`);
// @ts-ignore
const GEORADIUS = await redis.georadius(key, 116.67, 39.5, 50, 'km', 'withdist', 'count', 3, 'asc');
console.log(`距离「116.67, 39.5」附近「50」km内, 距离由近到远前3位为${GEORADIUS}`);
process.exit(1);
})()
 
4附近的人 git:(main) ✗ ts-node index.ts
AB之间的距离为36.2543km
A的经纬度为116.47999852895736694,39.90000009167092543
A的hash为wx4ffxd4ke0
A的附近300km, 距离由近到远为A,B,C
A的附近300km, 距离由近到远为A,0.0000,4069885894809634,116.47999852895736694,39.90000009167092543,B,36.2543,4069982235196126,116.90000027418136597,39.9500000012600438,C,103.4539,4069174206137433,116.82999998331069946,39.01000119404034905
距离「116.67, 39.5」附近「50」km内, 距离由近到远前3位为A,47.3686
 
# GEOADD: 添加位置 hset结构 
127.0.0.1:6379> GEOADD zhubo 116.48 39.9 A
(integer) 1
127.0.0.1:6379> GEOADD zhubo 116.9 39.95 B
(integer) 1
127.0.0.1:6379> GEOADD zhubo 116.83 39.01 C
(integer) 1
127.0.0.1:6379> GEOADD zhubo 116.67 39.44 D
(integer) 1
# GEODIST 两个key 之间的距离 km m
127.0.0.1:6379> GEODIST zhubo A B km
"36.2543"
127.0.0.1:6379> GEODIST zhubo A A km
"0.0000"
# GEOPOS 输出某个key的信息
127.0.0.1:6379> GEOPOS zhubo A
1) 1) "116.47999852895736694"
2) "39.90000009167092543"
127.0.0.1:6379> GEOPOS zhubo A B
1) 1) "116.47999852895736694"
2) "39.90000009167092543"
2) 1) "116.90000027418136597"
2) "39.9500000012600438"
# GEOHASH 输出对应的hash值
127.0.0.1:6379> GEOHASH zhubo A
1) "wx4ffxd4ke0"

# GEORADIUSBYMEMBER 距离某个key xxkm,限制number个元素 生序排列
127.0.0.1:6379> GEORADIUSBYMEMBER zhubo A 300 km count 4 asc
1) "A"
2) "B"
3) "D"
4) "C"
127.0.0.1:6379> GEORADIUSBYMEMBER zhubo A 300 km count 4 desc
1) "C"
2) "D"
3) "B"
4) "A"
# GEORADIUSBYMEMBER 附加 withcoord withdist withhash
127.0.0.1:6379> GEORADIUSBYMEMBER zhubo A 300 km withcoord withdist withhash count 4 asc
1) 1) "A"
2) "0.0000"
3) (integer) 4069885894809634
4) 1) "116.47999852895736694"
2) "39.90000009167092543"
2) 1) "B"
2) "36.2543"
3) (integer) 4069982235196126
4) 1) "116.90000027418136597"
2) "39.9500000012600438"
3) 1) "D"
2) "53.6879"
3) (integer) 4069136689844544
4) 1) "116.67000085115432739"
2) "39.43999889567408701"
4) 1) "C"
2) "103.4539"
3) (integer) 4069174206137433
4) 1) "116.82999998331069946"
2) "39.01000119404034905"
# GEORADIUS 距离某个点,附近信息
127.0.0.1:6379> GEORADIUS zhubo 116.67 39.5 50 km withdist count 3 asc
1) 1) "D"
2) "6.6737"
2) 1) "A"
2) "47.3686"
 

参考

Geohash算法原理及实现


全部评论: 0

    我有话说:

    Redis系列

      本文目标 1. 熟悉乐观锁ABA概念 2. 理解掌握redis事务以及watch回滚; 3. 实战redis锁 乐观锁 乐观锁是一种不会阻塞其他线程并发机制,它不会使用数据库

    「转载」Redis 到底是怎么实现“附近”这个功能

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

    Redis系列六 Lua

      本文目标 学习lua基本语法 能够采用redis+lua lua 基本语法 Lua 是一种轻量小巧脚本语言,用标准C语言编写并以源代码形式开放, 其设计目的是为了嵌入应用

    Redis系列七 Debug Lua

      调试redis+lua 学了lua基本语法,了解了redis+lua配套用法,但是却不知道怎么断点调试。学就学全面点, 官网中有dubug相关说明。地址:Redis Lua

    Redis系列一 基本用法&应用场景

        说明 redis最基本使用方法以及使用场景。 字符串 // stringasync function stringFun() { const [key

    Redis系列八 抢红包

      本文概述 掌握红包两种常见生成算法 掌握lua+redis 实现原子性抢红包 项目中还有mysql相关内容 了解jmeter基本用法 遗留问题 redis同步DB时机问题

    Redis系列九 推荐系统-布隆过滤器

      布隆过滤器 概念 布隆过滤器是一种空间利用率较高概率型数据结构,用来测试一个元素是否在集合中。但是存在一定可能,导致结果误判。当布隆过滤器说某个值存在时,这个值可能不存在;当它说不

    Redis系列二:位图实战,实现打卡签到

    前言 如果要统计一篇文章阅读量,可以直接使用 Redis  incr 指令来完成。 如果要求阅读量必须按用户去重,那就可以使用 set 来记录阅读了这篇文章所有用户 id,获取

    为什么单线程Redis能够达到百万级QPS?

    作者:在江湖中coding链接:https://juejin.im/post/5e6097846fb9a07c9f3fe744 性能测试报告 查看了下阿里云 Redis 性能测试报告如下,能够

    Redisson 3.13.6 发布,官方推荐 Redis 客户端

    Redisson 3.13.6 已发布,这是一个 Java 编写 Redis 客户端,具备驻内存数据网格(In-Memory Data Grid)功能,并获得了 Redis 官方推荐

    React生命周期&原生通信,挺简单

    张图引发系列事件。。。。

    Redis 5.0.11、6.0.11、6.2 发布,修复 32 位系统整数溢出

    Redis 同时发布了 5.0.11、6.0.11 和 6.2 版本。对于使用 32 位 Redis 用户来说,此次更新解决了一个重要安全问题,即 32 位系统整数溢出((CVE-2021

    BAT大牛Redis客户端与服务端交互原理

    Redis实例运行在单独进程中,应用系统Redis客户端)通过Redis协议和Redis Server

    Martian框架发布 3.0.3 版本,Redis分布式锁

    项目简介 Martian 是一个声明式 API 编程(DAP)框架,可以帮助你快速开发后端服务。 以HttpServer作为 http服务,彻底脱离Tomcat这一类Web容器和Servlet

    Node&RabbitMQ系列 X场景解构

    目标 先设想购票场景:用户注册成功后,三天内未登陆,则短信提醒。 三段式场景: A-B-C可以延伸至: 发起购票—>时间+未付款—>短信提醒⏰、取消订单 发起退款—>时间+未

    商城系统 DBShop V3.0 Beta 发布

    支付、多货币;严谨安全机制,可靠稳定;方便操...

    大多数都不知道 Maven 版本号

    前言 大多数程序员或多或少会有这样苦恼经历 开发了一个公共组件 maven 版本号为: 1.0.0 然后很多项目都用了这个项目版本号 过了一段时间发现有bug,或者需要在组件中增加些代码,版本号

    JAVA实现附近范围内公交定位问题

    接上篇【前端实战篇:通过JS抓取城市所有站点与线路】获取附近定位信息

    Jedis 3.5.0 发布,Redis Java 客户端开发包

    Jedis 3.5.0 发布了。Jedis 是 Redis 官方推荐面向 Java 操作 Redis 客户端,与新版本 Redis 完全兼容。 本次更新内容包括: 增强功能 通过 COUNT