继夫的玩弄H辣文的小说|女人与拘性猛交视频|精品欧美高清不卡高清|一起做亏亏的事情的视频|啦啦啦在线视频观看|望月直播下载ios版本|国产日韩欧美一区二区三区

  1. 首頁(yè) > 生活 > >

5 搜索引擎入門—空間索引

生活百科編碼轉(zhuǎn)換

在點(diǎn)評(píng)口碑上，經(jīng)常有類似的場(chǎng)景，搜索 “1公里以內(nèi)的美食”，那么這個(gè)1公里怎么實(shí)現(xiàn)呢？
在數(shù)據(jù)庫(kù)中可以通過(guò)暴力計(jì)算、矩形過(guò)濾、以及B樹對(duì)經(jīng)度和維度建索引，但這性能仍然很慢(可參考 為什么需要空間索引 ) 。搜索里用了一個(gè)很巧妙的方法，Geo Hash 。
如上圖，表示根據(jù)對(duì)北京幾個(gè)區(qū)域生成的字符串，有幾個(gè)特點(diǎn)：
【5 搜索引擎入門—空間索引】Geo Hash 如何編碼？
地球上任何一個(gè)位置都可以用經(jīng)緯度表示 ， 緯度的區(qū)間是 [-90, 90]，經(jīng)度的區(qū)間 [-180, 180] 。比如天安門的坐標(biāo)是 39.908,116.397 ， 整體編碼過(guò)程如下：
一、對(duì)緯度 39.908 的編碼如下：
將緯度劃分2個(gè)區(qū)間，左區(qū)間 [-90, 0) 用 0 表示，右區(qū)間 [0, 90] 用 1 表示，39.908 處在右區(qū)間 ， 故第一位編碼是 1；在將 [0, 90] 劃分2個(gè)區(qū)間，左區(qū)間 [0, 45) 用 0 表示mysql索引類型都有哪些，右區(qū)間 [45, 90] 用 1 表示，39.908處在左區(qū)間，故第二位編碼是 0；同1、2的計(jì)算步驟，39.908 的最后10位編碼是 “10111 00011”
二、對(duì)經(jīng)度 116.397 的編碼如下：
將經(jīng)度劃分2個(gè)區(qū)間，左區(qū)間 [-180, 0) 用 0 表示 ， 右區(qū)間 [0, 180] 用 1 表示，116.397處在右區(qū)間 ，  故第一位編碼是 1；在將 [0, 180] 劃分2個(gè)區(qū)間，左區(qū)間 [0, 90) 用 0 表示，右區(qū)間 [90, 180] 用 1 表示 ， 116.397處在右區(qū)間，故第二位編碼是 1；同1、2的計(jì)算步驟，116.397 的最后6位編碼是 “11010 01011”
三、合并組碼
將奇數(shù)位放經(jīng)度，偶數(shù)位放緯度，把2串編碼組合生成新串：“11100 11101 00100 01111”；通過(guò)編碼，每5個(gè)二進(jìn)制編碼一個(gè)數(shù)，“28 29 04 15”根據(jù)表，得到 Geo Hash 為：“WX4G”
即最后天安門的4位 Geo Hash 為 “WX4G”，如果需要經(jīng)度更準(zhǔn)確，在對(duì)應(yīng)的經(jīng)緯度編碼粒度再往下追溯即可 。
附： 編碼圖
Geo Hash 如何用于地理搜索？
舉個(gè)例子，搜索天安門附近 200 米的景點(diǎn)，如下是天安門附近的Geo編碼
搜索過(guò)程如下：
首先確定天安門的Geo Hash為，（6位區(qū)域碼約 0.34平分千米，約為長(zhǎng)寬600米區(qū)域)而6位編碼表示 600 米，半徑 300 米 > 要求的 200 米，搜索所有編碼為的景點(diǎn)即可但是由于天安門處于的邊緣位置 ， 并不一定處在正中心 。這就需要將附近的8個(gè)區(qū)域同時(shí)納入搜索，故搜索 、、 一共9個(gè)編碼的景點(diǎn)第3步已經(jīng)將范圍縮小到很小的一個(gè)區(qū)間，但是得到的景點(diǎn)距離并不是準(zhǔn)確的，需要在通過(guò)距離計(jì)算過(guò)濾出小于 200 米的景點(diǎn)，得到最終結(jié)果 。
由上面步驟可以看出，Geo Hash 將原本大量的距離計(jì)算 ， 變成一個(gè)字符串檢索縮小范圍后，再進(jìn)行小范圍的距離計(jì)算 ， 及快速又準(zhǔn)確的進(jìn)行距離搜索 。
Geo Hash 依據(jù)的數(shù)學(xué)原理
如圖所示，我們將二進(jìn)制編碼的結(jié)果填寫到空間中，當(dāng)將空間劃分為四塊時(shí)候mysql索引類型都有哪些，編碼的順序分別是左下角00，左上角01，右下腳10，右上角11，也就是類似于Z的曲線 。當(dāng)我們遞歸的將各個(gè)塊分解成更小的子塊時(shí)，編碼的順序是自相似的（分形），每一個(gè)子快也形成Z曲線，這種類型的曲線被稱為Peano空間填充曲線 。
這種類型的空間填充曲線的優(yōu)點(diǎn)是將二維空間轉(zhuǎn)換成一維曲線（事實(shí)上是分形維），對(duì)大部分而言，編碼相似的距離也相近 ，  但Peano空間填充曲線最大的缺點(diǎn)就是突變性，有些編碼相鄰但距離卻相差很遠(yuǎn)，比如0111與1000，編碼是相鄰的，但距離相差很大 。
除Peano空間填充曲線外 ， 還有很多空間填充曲線，如圖所示，其中效果公認(rèn)較好是空間填充曲線 ， 相較于Peano曲線而言，曲線沒(méi)有較大的突變 。為什么不選擇空間填充曲線呢？可能是Peano曲線思路以及計(jì)算上比較簡(jiǎn)單吧 ， 事實(shí)上，Peano曲線就是一種四叉樹線性編碼方式 。
本文到此結(jié)束 ， 希望對(duì)大家有所幫助 。