超酷算法用四叉樹和希爾伯特曲線做空間索引.docx

《超酷算法用四叉樹和希爾伯特曲線做空間索引.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、超酷算法：用四叉樹和希爾伯特曲線做空間索引2014/12/18·?IT技術(shù)?·?四叉樹,?希爾伯特曲線,?空間索引,?算法分享到：36本文由?伯樂在線?-?demoZ?翻譯，黃利民?校稿。未經(jīng)許可，禁止轉(zhuǎn)載！英文出處：blog.notdot.net。歡迎加入翻譯組。隨著越來越多的數(shù)據(jù)和應(yīng)用和地理空間相關(guān)，空間索引變得愈加重要。然而，有效地查詢地理空間數(shù)據(jù)是相當(dāng)大的挑戰(zhàn)，因?yàn)閿?shù)據(jù)是二維的（有時(shí)候更高），不能用標(biāo)準(zhǔn)的索引技術(shù)來查詢位置?？臻g索引通過各種各樣的技術(shù)來解決這個(gè)問題。在這篇博文中，我將介紹幾種：四叉樹，geohash（不要和geohashing混淆）以及空間填充曲線，并揭示它們是怎樣

2、相互關(guān)聯(lián)的。四叉樹四叉樹是種很直接的空間索引技術(shù)。在四叉樹中，每個(gè)節(jié)點(diǎn)表示覆蓋了部分進(jìn)行索引的空間的邊界框，根節(jié)點(diǎn)覆蓋了整個(gè)區(qū)域。每個(gè)節(jié)點(diǎn)要么是葉節(jié)點(diǎn)，有包含一個(gè)或多個(gè)索引點(diǎn)的列表，沒有孩子。要么是內(nèi)部節(jié)點(diǎn)，有四個(gè)孩子，每個(gè)孩子對應(yīng)將區(qū)域沿兩根軸對半分得到的四個(gè)象限中的一個(gè)，四叉樹也因此得名。圖1???展示四叉樹是怎樣劃分索引區(qū)域的來源：維基百科將數(shù)據(jù)插入四叉樹很簡單：從根節(jié)點(diǎn)開始，判斷你的數(shù)據(jù)點(diǎn)屬于哪個(gè)象限。遞歸到相應(yīng)的節(jié)點(diǎn)，重復(fù)步驟，直到到達(dá)葉節(jié)點(diǎn)，然后將該點(diǎn)加入節(jié)點(diǎn)的索引點(diǎn)列表中。如果列表中的元素個(gè)數(shù)超出了預(yù)設(shè)的最大數(shù)目，則將節(jié)點(diǎn)分裂，將其中的索引點(diǎn)移動(dòng)到相應(yīng)的子節(jié)點(diǎn)中去。圖2???

3、四叉樹的內(nèi)部結(jié)構(gòu)查詢四叉樹時(shí)從根節(jié)點(diǎn)開始，檢查每個(gè)子節(jié)點(diǎn)看是否與查詢的區(qū)域相交。如果是，則遞歸進(jìn)入該子節(jié)點(diǎn)。當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)時(shí)，檢查點(diǎn)列表中的每一個(gè)項(xiàng)看是否與查詢區(qū)域相交，如果是則返回此項(xiàng)。注意四叉樹是非常規(guī)則的，事實(shí)上它是一種字典樹，因?yàn)闃涔?jié)點(diǎn)的值不依賴于插入的數(shù)據(jù)。因此我們可以用直接的方式給節(jié)點(diǎn)編號(hào)：用二進(jìn)制給每個(gè)象限編號(hào)（左上是00，右上是10等等?譯者注：第一個(gè)比特位為0表示在左半平面，為1在右半平面。第二個(gè)比特位為0表示在上半平面，為1在下半平面），任一節(jié)點(diǎn)的編號(hào)是由從根開始，它的各祖先的象限號(hào)碼串接而成的。在這個(gè)編號(hào)系統(tǒng)中，圖2中右下角節(jié)點(diǎn)的編號(hào)是1101。如果我們定義了樹的最大深

4、度，不需通過樹就可以計(jì)算數(shù)據(jù)點(diǎn)所在節(jié)點(diǎn)的編號(hào)：只要把節(jié)點(diǎn)的坐標(biāo)標(biāo)準(zhǔn)化到適當(dāng)?shù)恼麛?shù)區(qū)間中（比如32位整數(shù)），然后把轉(zhuǎn)化后x,y坐標(biāo)的比特位交錯(cuò)組合。每對比特指定了假想的四叉樹中的一個(gè)象限。（譯者注：不了解的讀者可看看Z-order，它和下文的希爾伯特曲線都是將二維的點(diǎn)映射到一維的方法）Geohash上述編號(hào)系統(tǒng)可能看起來有些熟悉，沒錯(cuò)，就是geohash！此刻，你可以把四叉樹扔掉了。節(jié)點(diǎn)編號(hào)，或者說geohash，包含了對于節(jié)點(diǎn)在樹中位置我們需要的全部信息。全高樹中的每個(gè)葉節(jié)點(diǎn)是個(gè)完整的geohash，每個(gè)內(nèi)部節(jié)點(diǎn)代表從它最小的葉節(jié)點(diǎn)到最大的葉節(jié)點(diǎn)的區(qū)間。因此，通過查詢所需的節(jié)點(diǎn)覆蓋的數(shù)值區(qū)

5、間中的一切（在geohash上索引），你可以有效地定位任意內(nèi)部節(jié)點(diǎn)下的所有數(shù)據(jù)點(diǎn)。一旦我們丟掉了四叉樹，查詢就變得復(fù)雜一點(diǎn)了。我們需要事先構(gòu)建搜索集合而不是在樹中遞歸地精煉搜索集合。首先，找到完全覆蓋查詢區(qū)域的最小前綴（或者說四叉樹節(jié)點(diǎn)??譯者注：注意在我們的編號(hào)系統(tǒng)中節(jié)點(diǎn)由比特串表示）。在最壞情況下，這可能遠(yuǎn)大于實(shí)際的查詢區(qū)域，比如對于在索引區(qū)域中心、和四個(gè)象限都相交的小塊地方，查詢將要從根節(jié)點(diǎn)開始?，F(xiàn)在的目標(biāo)是構(gòu)建一組完全包含查詢區(qū)域的前綴，并且盡可能少包含區(qū)域外的部分。如果沒有其他約束，我們可以簡單地選擇與查詢區(qū)域相交的葉節(jié)點(diǎn)，但這會(huì)造成大量的查詢。所以要加一個(gè)約束：使得要查詢的不同

6、區(qū)間最少。一種達(dá)到這個(gè)目的的方法是先設(shè)置我們愿意承受的查詢區(qū)間的最大數(shù)目。構(gòu)建一組區(qū)間，最開始都設(shè)為我們之前指定的前綴。從中選擇可以再分裂而不超出最大區(qū)間數(shù)并將從查詢區(qū)域刪除最不受歡迎區(qū)域的節(jié)點(diǎn)。重復(fù)這個(gè)過程直到集合中再?zèng)]有區(qū)間可以細(xì)分。最后，檢查得到的集合，如果可能的話合并相鄰的區(qū)間。下面的圖說明了這對于查詢一個(gè)圓形區(qū)域且限制最大5個(gè)查詢區(qū)間是如何工作的。圖3???一個(gè)對區(qū)域的查詢是怎樣分解成一連串geohash前綴/區(qū)間的這個(gè)方法工作地很好，它使我們避免了遞歸查找。我們執(zhí)行的一整套區(qū)間查找都可以并行完成。由于每次查找都預(yù)期要一次硬盤搜索，將查詢并行化大大減少了返回結(jié)果需要的時(shí)間。然而，

7、我們還可以做得更好。你可能注意到上圖中我們要查詢的所有區(qū)域都是相鄰的，但我們卻只能將其中兩個(gè)合并（選擇區(qū)域的右下角的兩個(gè)）成一個(gè)單獨(dú)的查詢，進(jìn)而只要4次單獨(dú)查詢。（譯者注：這兩個(gè)區(qū)域可以合并是因?yàn)樗鼈冊趃eohash以Z字形遍歷區(qū)域的路徑上是相鄰的）這個(gè)后果部分是由于geohash訪問子區(qū)域的順序，在每個(gè)象限中從左到右，從上到下。從右上角象限到左下角象限的不連續(xù)性使得我們不得不將本可以使之連續(xù)的區(qū)間分裂。如果以不同的順序