婷婷综合国产,91蜜桃婷婷狠狠久久综合9色 ,九九九九九精品,国产综合av

主頁 > 知識庫 > Redis高效檢索地理位置的原理解析

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

熱門標簽:十堰營銷電銷機器人哪家便宜 北京400電話辦理收費標準 魔獸2青云地圖標注 日本中國地圖標注 山東外呼銷售系統招商 宿遷便宜外呼系統平臺 貴州電銷卡外呼系統 超呼電話機器人 鄭州人工智能電銷機器人系統

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

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

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

geohash

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

1. 轉二進制

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

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

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

11010010110001101101

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

10111000110000111001

2. 經緯度二進制合并

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

1101101110000200111100000001111011010011

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

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

最終得到geohash值wx4g0cg3vknd。

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

geohash的用途及問題

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

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

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

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

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

但在實際使用geohash過程中,時常會遇到跨域搜索的情況,比如我要在上圖(3,3)這個區間內某個點上搜索距它1個距離單位的所有其他點集,這個點集有可能橫跨(3,3)加上它周圍8個鄰域的9個區間,突變的問題會導致這9個區間的geohash不是線性跳轉的,但也不是沒法計算,實際上可以通過特殊的位運算可以很輕易計算出某個geohash的8個鄰域,具體可參考redis源碼中src/geohash.c中geohashNeighbors()的具體實現,geohashNeighbors使用了geohash_move_x和geohash_move_y兩個函數實現了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的實現,其實看到這里,你基本上已經理解了redis中的geohash的實現了。本質上redis中的geo就是對geohash的封裝,具體geohash相關的代碼就不給大家列了(可自行查閱),就給大家介紹下redis geo里的大體流程。
首先,可能大家最好奇的是geohash在redis中是怎么存儲的,從geoadd命令的實現可以一窺端倪。

/* 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的具體實現可以參考我之前寫的文章redis中skiplist的實現。

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

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) {
    /*
     * 各種必選參數的解析,省略細節代碼,主要是解析坐標點信息和半徑   
     */ 
    }

    /* 解析所有的可選參數. */
    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) {
    /*
     * 各種可選參數的解析,省略細節代碼   
     */ 
    }
    
    /* Get all neighbor geohash boxes for our radius search
     * 獲取到要查找范圍內所有的9個geo鄰域 */
    GeoHashRadius georadius = geohashCalculateAreasByShapeWGS84(shape);

    /* 創建geoArray存儲結果列表 */
    geoArray *ga = geoArrayCreate();
    /* 掃描9個區域中是否有滿足條的點,有就放到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;

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

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

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

結語

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

參考資料

wikipedia geohash

Geohash算法原理及實現

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

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

您可能感興趣的文章:
  • redis數據庫查找key在內存中的位置的方法
  • PHP redis實現超迷你全文檢索

標簽:果洛 楊凌 臺州 江蘇 北京 大慶 朝陽 吉安

巨人網絡通訊聲明:本文標題《Redis高效檢索地理位置的原理解析》,本文關鍵詞  Redis,高效,檢索,地理位置,;如發現本文內容存在版權問題,煩請提供相關信息告之我們,我們將及時溝通與處理。本站內容系統采集于網絡,涉及言論、版權與本站無關。
  • 相關文章
  • 下面列出與本文章《Redis高效檢索地理位置的原理解析》相關的同類信息!
  • 本頁收集關于Redis高效檢索地理位置的原理解析的相關信息資訊供網民參考!
  • 推薦文章
    主站蜘蛛池模板: 交口县| 瓦房店市| 鄯善县| 无锡市| 丁青县| 高雄市| 河南省| 新田县| 广河县| 西贡区| 西吉县| 晋州市| 泰宁县| 内黄县| 怀宁县| 阳泉市| 从化市| 惠州市| 洛浦县| 鄢陵县| 泰安市| 美姑县| 峨山| 安徽省| 舒城县| 甘肃省| 巴塘县| 金昌市| 兖州市| 永济市| 阜康市| 五莲县| 乃东县| 崇信县| 麻城市| 喜德县| 松桃| 基隆市| 岑溪市| 奎屯市| 万山特区|