最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

Redis高效檢索地理位置的原理解析

 更新時間:2021年06月16日 14:12:12   作者:xindoo  
這篇文章主要介紹了Redis是如何高效檢索地理位置,通過geo相關的命令,可以很容易在redis中存儲和使用經緯度坐標信息,具體實現(xiàn)方法跟隨小編一起看看吧

Redis GEO 用做存儲地理位置信息,并對存儲的信息進行操作。通過geo相關的命令,可以很容易在redis中存儲和使用經緯度坐標信息。Redis中提供的Geo命令有如下幾個:

  • geoadd:添加經緯度坐標和對應地理位置名稱。
  • geopos:獲取地理位置的經緯度坐標。
  • geodist:計算兩個地理位置的距離。
  • georadius:根據用戶給定的經緯度坐標來獲取指定范圍內的地理位置集合。
  • georadiusbymember:根據儲存在位置集合里面的某個地點獲取指定范圍內的地理位置集合。
  • geohash:計算一個或者多個經緯度坐標點的geohash值。

要理解Redis的GEO相關的命令是如何實現(xiàn)了,就得先理解geohash的原理,本質上這些命令就是對geohash數據的封裝而已。

geohash

geohash是2008年Gustavo Niemeye發(fā)明用來編碼經緯度信息的一種編碼方式,比如北京市中心的經緯度坐標是116.404844,39.912279,通過12位geohash編碼后就變成了wx4g0cg3vknd,它究竟是如何實現(xiàn)的?其實原理非常簡單,就是二分,整個編碼過程可以分為如下幾步。

1. 轉二進制

上過初中地理的我們都知道,地球上如何一個點就可以標識為某個經緯度坐標,經度的取值范圍是東經0-180度和西經0-180度,維度的取值范圍是北緯0到90和南緯0-90度。去掉東西南北,可以分別認為經度和維度的取值范圍為[-180,180]和[-90,90]。

我們先來看經度,[-180,180]可以簡單分成兩個部分[-180,0]和[0,180],對于給定的一個具體值,我們用一個bit來標識是在[-180,0]還是[0,180]區(qū)間里。然后我們可以對這兩個子區(qū)間繼續(xù)細分,用更多的bit來標識是這個值是在哪個子區(qū)間里。就好比用二分查找,記錄下每次查找的路徑,往左就是0往右是1,查找完后我們就會得到一個0101的串,這個串就可以用來標識這個經度值。

同理維度也是一樣,只不過他的取值返回變成了[-90,90]而已。通過這兩種方式編碼完成后,任意經緯度我們都可以得到兩個由0和1組成的串。
比如還是北京市中心的經緯度坐標 116.404844,39.912279,我們先對116.404844做編碼,得到其二進制為:

11010010110001101101

然后我們對維度39.912279編碼得到二進制為:

10111000110000111001

2. 經緯度二進制合并

接下來我們只需要將上述二進制交錯合并成一個即可,這里注意經度占偶數位,緯度占奇數位,得到最終的二進制。

1101101110000200111100000001111011010011

3. 將合并后的二進制做base32編碼

最后我們將合并后的二進制做base32編碼,將連續(xù)5位轉化為一個0-31的十進制數,然后用對應的字符代替,將所有二進制位處理完后我們就完成了base32編碼。編碼表如下:

在這里插入圖片描述

最終得到geohash值wx4g0cg3vknd。

在這里插入圖片描述

geohash是將空間不斷的二分,然后將二分的路徑轉化為base32編碼,最后保存下來,從原理可以看出,geohash表示的是一個區(qū)間,而不是一個點,geohash值越長,這個區(qū)間就越小,標識的位置也就越精確,下圖是維基百科中不同長度geohash下的經緯度誤差(lat:維度,lng:經度)

在這里插入圖片描述

geohash的用途及問題

geohash成功的將一個二維信息編碼成了一個一維信息,這樣編碼我覺得有兩個好處:1. 編碼后數據長度變短,利于節(jié)省存儲。2. 利于使用前綴檢索。我們來詳細說下第二點。

從上文中geohash的實現(xiàn)來看,只要兩個坐標點的geohash有共同的前綴,你們我們就可以肯定這兩個點在同一個區(qū)域內 (區(qū)域大小取決于共同前綴的長度)。這種特性給我們帶來的好處就是,我們可以把所有坐標點按geohash做增序索引,然后查找的時候按前綴篩選,大幅提升檢索的性能。

舉個例子,假設我要找北京國貿附近3公里內的餐館,已知國貿的geohash是wx4g41,那我也很輕易就可以計算出來我需要掃描哪些區(qū)域內的點。但有個點需要注意,上文我已經提到過,geohash值實際上是代表一個區(qū)域,而不是一個點,找到一批候選點之后還需要遍歷一次計算下精確距離。

在這里插入圖片描述

geohash有個需要注意的問題。geohash是將二維的坐標點做了線下編碼(如下圖),有時候可能會給人一個誤解就是如果兩個geohash之間二進制的差異越小,這兩個區(qū)間距離就越近,這完全是錯誤的,比如如下圖0111和1000,這倆區(qū)間二進制只差0001但實際物理距離比較遠。

在這里插入圖片描述

如果上圖還不明顯的話,我從Wikipedia上拿到一張圖,虛線是線性索引的路徑,被虛線鏈接的兩個塊geohash值是非常相近的,如下圖的(7,3)和(0,4),geohash值會非常相近,但實際物理距離非常遠,這就是geohash的突變現(xiàn)象,這也導致了不能直接根據geohash的值來直接判定兩個區(qū)域的距離大小。

在這里插入圖片描述

但在實際使用geohash過程中,時常會遇到跨域搜索的情況,比如我要在上圖(3,3)這個區(qū)間內某個點上搜索距它1個距離單位的所有其他點集,這個點集有可能橫跨(3,3)加上它周圍8個鄰域的9個區(qū)間,突變的問題會導致這9個區(qū)間的geohash不是線性跳轉的,但也不是沒法計算,實際上可以通過特殊的位運算可以很輕易計算出某個geohash的8個鄰域,具體可參考redis源碼中src/geohash.c中geohashNeighbors()的具體實現(xiàn),geohashNeighbors使用了geohash_move_x和geohash_move_y兩個函數實現(xiàn)了geohash左右和上下的移動,這樣可以很容易組合出8個鄰域的geohash值了。

static void geohash_move_x(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits & 0x5555555555555555ULL;

    uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);

    if (d > 0) {
        x = x + (zz + 1);
    } else {
        x = x | zz;
        x = x - (zz + 1);
    }

    x &= (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

static void geohash_move_y(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits & 0x5555555555555555ULL;

    uint64_t zz = 0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2);
    if (d > 0) {
        y = y + (zz + 1);
    } else {
        y = y | zz;
        y = y - (zz + 1);
    }
    y &= (0x5555555555555555ULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}

Geo in redis

上文中花了大量篇幅講解了geohash的實現(xiàn),其實看到這里,你基本上已經理解了redis中的geohash的實現(xiàn)了。本質上redis中的geo就是對geohash的封裝,具體geohash相關的代碼就不給大家列了(可自行查閱),就給大家介紹下redis geo里的大體流程。
首先,可能大家最好奇的是geohash在redis中是怎么存儲的,從geoadd命令的實現(xiàn)可以一窺端倪。

/* GEOADD key [CH] [NX|XX] long lat name [long2 lat2 name2 ... longN latN nameN] */
void geoaddCommand(client *c) {
    int xx = 0, nx = 0, longidx = 2;
    int i;

    /* 解析可選參數 */
    while (longidx < c->argc) {
        char *opt = c->argv[longidx]->ptr;
        if (!strcasecmp(opt,"nx")) nx = 1;
        else if (!strcasecmp(opt,"xx")) xx = 1;
        else if (!strcasecmp(opt,"ch")) {}
        else break;
        longidx++;
    }

    if ((c->argc - longidx) % 3 || (xx && nx)) {
        /* 解析所有的經緯度值和member,并對其個數做校驗 */
            addReplyErrorObject(c,shared.syntaxerr);
        return;
    }

    /* 構建zadd的參數數組 */
    int elements = (c->argc - longidx) / 3;
    int argc = longidx+elements*2; /* ZADD key [CH] [NX|XX] score ele ... */
    robj **argv = zcalloc(argc*sizeof(robj*));
    argv[0] = createRawStringObject("zadd",4);
    for (i = 1; i < longidx; i++) {
        argv[i] = c->argv[i];
        incrRefCount(argv[i]);
    }

    /* 以3個參數為一組,將所有的經緯度和member信息從參數列表里解析出來,并放到zadd的參數數組中 */
    for (i = 0; i < elements; i++) {
        double xy[2];

        if (extractLongLatOrReply(c, (c->argv+longidx)+(i*3),xy) == C_ERR) {
            for (i = 0; i < argc; i++)
                if (argv[i]) decrRefCount(argv[i]);
            zfree(argv);
            return;
        }

        /* 將經緯度坐標轉化成score信息 */
        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[longidx + i * 3 + 2];
        argv[longidx+i*2] = score;
        argv[longidx+1+i*2] = val;
        incrRefCount(val);
    }

    /* 轉化成zadd命令所需要的參數格式*/
    replaceClientCommandVector(c,argc,argv);
    zaddCommand(c);
}

原來geo的存儲只是zset包了一層殼(是不是有點小失望),關于zset的具體實現(xiàn)可以參考我之前寫的文章redis中skiplist的實現(xiàn)。

我們再來詳細看下georadius的大體執(zhí)行流程(代碼偏長,故刪除大量細節(jié)代碼)。

void georadiusGeneric(client *c, int srcKeyIndex, int flags) {
    robj *storekey = NULL;
    int storedist = 0; /* 0 for STORE, 1 for STOREDIST. */

    /* 根據key找找到對應的zojb */
    robj *zobj = NULL;
    if ((zobj = lookupKeyReadOrReply(c, c->argv[srcKeyIndex], shared.emptyarray)) == NULL ||
        checkType(c, zobj, OBJ_ZSET)) {
        return;
    }

    /* 解析請求中的經緯度值 */
    int base_args;
    GeoShape shape = {0};
    if (flags & RADIUS_COORDS) {
    /*
     * 各種必選參數的解析,省略細節(jié)代碼,主要是解析坐標點信息和半徑   
     */ 
    }

    /* 解析所有的可選參數. */
    int withdist = 0, withhash = 0, withcoords = 0;
    int frommember = 0, fromloc = 0, byradius = 0, bybox = 0;
    int sort = SORT_NONE;
    int any = 0; /* any=1 means a limited search, stop as soon as enough results were found. */
    long long count = 0;  /* Max number of results to return. 0 means unlimited. */
    if (c->argc > base_args) {
    /*
     * 各種可選參數的解析,省略細節(jié)代碼   
     */ 
    }
    
    /* Get all neighbor geohash boxes for our radius search
     * 獲取到要查找范圍內所有的9個geo鄰域 */
    GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(&shape);

    /* 創(chuàng)建geoArray存儲結果列表 */
    geoArray *ga = geoArrayCreate();
    /* 掃描9個區(qū)域中是否有滿足條的點,有就放到geoArray中 */
    membersOfAllNeighbors(zobj, georadius, &shape, ga, any ? count : 0);

    /* 如果沒有匹配結果,返回空對象 */
    if (ga->used == 0 && storekey == NULL) {
        addReply(c,shared.emptyarray);
        geoArrayFree(ga);
        return;
    }

    long result_length = ga->used;
    long returned_items = (count == 0 || result_length < count) ?
                          result_length : count;
    long option_length = 0;

    /* 
     * 后續(xù)一些參數邏輯,比如處理排序,存儲……
     */
    // 釋放geoArray占用的空間 
    geoArrayFree(ga);
}

上述代碼刪減了大量細節(jié),有興趣的同學可以自行查閱。不過可以看出georadius的整體流程非常清晰。

解析請求參數。計算目標坐標所在的geohash和8個鄰居。在zset中查找這9個區(qū)域中滿足距離限制的所有點集。處理排序等后續(xù)邏輯。清理臨時存儲空間。

結語

由于文章篇幅有限,而且著重講解了geohash的實現(xiàn),并未展開講解redis中geo相關的各種細節(jié),如讀者有興趣可以詳細閱讀redis中的src/geo.c了解各類細節(jié)。

參考資料

wikipedia geohash

Geohash算法原理及實現(xiàn)

本文是Redis源碼剖析系列博文,同時也有與之對應的Redis中文注釋版,有想深入學習Redis的同學,歡迎star和關注。
Redis中文注解版?zhèn)}庫:https://github.com/xindoo/Redis
Redis源碼剖析專欄:https://zxs.io/s/1h

以上就是Redis是如何高效檢索地理位置的詳細內容,更多關于Redis檢索地理位置的資料請關注腳本之家其它相關文章!

相關文章

  • 使用redis分布式鎖解決并發(fā)線程資源共享問題

    使用redis分布式鎖解決并發(fā)線程資源共享問題

    這篇文章主要介紹了使用redis分布式鎖解決并發(fā)線程資源共享問題,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07
  • redis中熱key問題該如何解決

    redis中熱key問題該如何解決

    這篇文章主要給大家介紹了關于redis中熱key問題該如何解決的相關資料,文中通過示例代碼介紹的非常詳細,對大家學習或者使用redis具有一定的參考學習價值,需要的朋友們下面來一起學習學習吧
    2019-05-05
  • Redis教程(十四):內存優(yōu)化介紹

    Redis教程(十四):內存優(yōu)化介紹

    這篇文章主要介紹了Redis教程(十四):內存優(yōu)化介紹,本文講解了特殊編碼、BIT和Byte級別的操作、盡可能使用Hash等內容,需要的朋友可以參考下
    2015-05-05
  • 淺談Redis如何應對并發(fā)訪問

    淺談Redis如何應對并發(fā)訪問

    本文主要介紹了Redis如何應對并發(fā)訪問,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-08-08
  • Redis哨兵機制的使用詳解

    Redis哨兵機制的使用詳解

    文章講解了Redis哨兵機制的基本原理、主庫和從庫自動切換的過程、如何減少誤判、哨兵集群的組成和通信機制,以及哨兵在故障發(fā)生時如何選舉Leader進行主從切換
    2025-01-01
  • Redis集群部署Windows版本的過程詳解

    Redis集群部署Windows版本的過程詳解

    本文介紹了如何在Windows系統(tǒng)上部署Redis集群,包括從GitHub下載Windows版本的Redis、配置文件的創(chuàng)建、啟動腳本的編寫以及集群的啟動和配置過程,感興趣的朋友一起看看吧
    2025-03-03
  • Redis中Scan命令的基本使用教程

    Redis中Scan命令的基本使用教程

    這篇文章主要給大家介紹了關于Redis中Scan命令的基本使用教程,文中通過示例代碼介紹的非常詳細,對大家學習或者使用Redis具有一定的參考學習價值,需要的朋友們下面來一起學習學習吧
    2019-06-06
  • Redis 對過期數據的處理方法

    Redis 對過期數據的處理方法

    這篇文章主要介紹了Redis 對過期數據的處理,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-10-10
  • Windows下Redis的安裝使用教程

    Windows下Redis的安裝使用教程

    這篇文章主要以圖文結合的方式為大家詳細介紹了Windows下Redis的安裝使用,Redis的出現(xiàn),很大程度補償了memcached這類key/value存儲的不足,在部分場合可以對關系數據庫起到很好的補充作用,對Redis感興趣的小伙伴們可以參考一下
    2016-05-05
  • 了解redis中RDB結構_動力節(jié)點Java學院整理

    了解redis中RDB結構_動力節(jié)點Java學院整理

    這篇文章主要為大家詳細介紹了redis中RDB結構,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-08-08

最新評論

时尚| 青河县| 韩城市| 麻阳| 郓城县| 宝应县| 宝应县| 华容县| 浦江县| 岚皋县| 武平县| 郁南县| 集贤县| 时尚| 通许县| 盘山县| 千阳县| 济南市| 县级市| 南雄市| 文安县| 乌兰察布市| 宜昌市| 梁平县| 凭祥市| 禄劝| 浮梁县| 营口市| 雷波县| 安宁市| 夏邑县| 婺源县| 东乡县| 遂昌县| 庆阳市| 万全县| 文化| 温泉县| 新建县| 河北省| 会东县|