用四叉樹和希爾伯特曲線做空間索引

1、超酷算法：用四叉樹和希爾伯特曲線做空間索引閱讀四叉樹,希爾伯特曲線,空間索引,算法 Avalon探索之旅基礎(chǔ)教程- 簡單綁定 Gopher China 2015 上海大會 Android必學(xué)-異步加載 Android必學(xué)-BaseAdapter的使用與優(yōu)化本文由伯樂在線-demoZ翻譯，黃利民校稿。未經(jīng)許可，禁止轉(zhuǎn)載！英文出處：。歡迎加入翻譯組。隨著越來越多的數(shù)據(jù)和應(yīng)用和地理空間相關(guān)，空間索引變得愈加重要。然而，有效地查詢地理空間數(shù)據(jù)是相當(dāng)大的挑戰(zhàn)，因為數(shù)據(jù)是二維的（有時候更高），不能用標(biāo)準(zhǔn)的索引技術(shù)來查詢位置?？臻g索引通過各種各樣的技術(shù)來解決這個問題。在這篇博文中，我將介紹幾種：四叉樹，ge

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

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

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

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

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

7、詢并行化大大減少了返回結(jié)果需要的時間。然而，我們還可以做得更好。你可能注意到上圖中我們要查詢的所有區(qū)域都是相鄰的，但我們卻只能將其中兩個合并（選擇區(qū)域的右下角的兩個）成一個單獨的查詢，進而只要4次單獨查詢。（譯者注：這兩個區(qū)域可以合并是因為它們在geohash以Z字形遍歷區(qū)域的路徑上是相鄰的）這個后果部分是由于geohash訪問子區(qū)域的順序，在每個象限中從左到右，從上到下。從右上角象限到左下角象限的不連續(xù)性使得我們不得不將本可以使之連續(xù)的區(qū)間分裂。如果以不同的順序訪問區(qū)域，可能我們就可以最小化或者消除這些不連續(xù)性，使得更多的區(qū)域可以被看做是相鄰的，一次查詢就可得到結(jié)果。通過這樣效率上的提升，對

8、于同樣的覆蓋區(qū)域，我們可以做更少的查詢，或者相反地，同樣的查詢次數(shù)的情況下包含更少的無關(guān)區(qū)域。圖4 geohash訪問象限的順序希爾伯特曲線現(xiàn)在假設(shè)我們以U字形來訪問區(qū)域。在每個象限中，我們同樣以U字形來訪問子象限，但是要調(diào)整好U字形的朝向使得和相鄰的象限銜接起來。如果我們正確地組織了這些U字形的朝向，我們就能完全消除不連續(xù)性，不管我們選擇了什么分辨率，都能連續(xù)地訪問整個區(qū)域，可以在完全地探訪了一個區(qū)域后才移動到下一個。這個方案不僅消除了不連續(xù)性，而且提高了總體的局域性。按照這個方案得到的圖案看起來有些熟悉，沒錯，就是希爾伯特曲線。希爾伯特曲線屬于一類被稱為空間填充曲線的一維分形，因為它們雖然

9、是一維的線，卻可以填充固定區(qū)域的所有空間。它們相當(dāng)有名，部分是由于XKCD把它們用于互聯(lián)網(wǎng)地圖。如你所見，對于空間索引它們也是有用的，因為它們展現(xiàn)的正是我們需要的局域性和連續(xù)性。再看看之前用一組查詢來覆蓋圓的例子，我們發(fā)現(xiàn)（應(yīng)用希爾伯特曲線）還可以減少一次查詢：左下方的小區(qū)域現(xiàn)在和它右邊的區(qū)域連起來了（減少一次），雖然底部的兩塊區(qū)域不再連續(xù)了（增加一次），右下角的區(qū)域現(xiàn)在卻和它上方的連續(xù)了（減少一次）。圖5 希爾伯特曲線訪問象限的順序到目前為止，我們優(yōu)雅的系統(tǒng)還缺一樣?xùn)|西：將(x,y)坐標(biāo)轉(zhuǎn)換為希爾伯特曲線上相應(yīng)位置的方法。對于geohash，這是簡單而明顯的只需將x, y坐標(biāo)交錯，但沒有明顯

10、的方法修改這個方案使之對希爾伯特曲線也適用。在網(wǎng)上搜索，你很可能遇到很多關(guān)于希爾伯特曲線是怎樣畫出來的描述，但很少有關(guān)于找到任意點（在曲線上）位置的。為了搞定它，我們需要更仔細(xì)看看希爾伯特曲線是怎么遞歸構(gòu)建的。首先要注意到雖然大多數(shù)關(guān)于希爾伯特曲線的文獻都關(guān)注曲線是怎么畫出來的，卻容易讓我們忽略曲線的本質(zhì)屬性以及其重要性：曲線規(guī)定了平面上點的順序。如果我們用這順序來表達希爾伯特曲線，畫曲線就不值一提了：僅僅是把點連起來。忘記怎么把子曲線連起來吧，把注意力集中在怎么遞歸地列舉點上。圖6 希爾伯特曲線規(guī)定了二維平面上的點的順序在根這一層，列舉點很簡單：選定一個方向和一個起始點，環(huán)繞四個象限，用0到

11、3給他們編號。當(dāng)我們要確定訪問子象限的順序同時維護總體的鄰接屬性，困難就來了。通過檢查我們發(fā)現(xiàn)，子象限的曲線是原曲線的簡單變換，而且只有四種變換。自然地，這個結(jié)論也適用于子子象限，等等。對于一個給定的象限，我們在其中畫出的曲線是由象限所在大的方形的曲線以及該象限的位置決定的。只需要費一點力，我們就能構(gòu)建出如下概況所有情況的表。圖7假設(shè)我們想用這個表來確定某個點在第三層希爾伯特曲線上的位置。在這個例子中，假設(shè)點的坐標(biāo)是(5,2)。（譯者注：請參照圖8）從上圖的第一個方形開始，找到你的點所在的象限。在這個例子中，是在右上方的象限。那么點在希爾伯特曲線上的位置的第一部分是3（二進制是11）。接著我們

12、進入象限3里面的方塊，在這個例子中，它是（圖7中的）第二個方塊。重復(fù)剛才的過程：我們的點落在哪個子象限？這次是左下角，意味著位置的下一部分是1（二進制01），我們將進入的小方塊又是第二個。最后一次重復(fù)這個過程，發(fā)現(xiàn)點落在右上角的子子象限，因此位置的最后部分是3（二進制11）。把這些位置連接起來，我們得到點在曲線上的位置是二進制的110111，或者十進制的55。圖8 三階希爾伯特曲線讓我們更系統(tǒng)一些，寫出從x, y坐標(biāo)到希爾伯特曲線位置轉(zhuǎn)換的方法。首先，我們要以計算機看得懂的形式表達圖7：12345hilbert_map = a: (0, 0): (0, d), (0, 1): (1, a),

13、(1, 0): (3, b), (1, 1): (2, a), b: (0, 0): (2, b), (0, 1): (1, b), (1, 0): (3, a), (1, 1): (0, c), c: (0, 0): (2, c), (0, 1): (3, d), (1, 0): (1, c), (1, 1): (0, b), d: (0, 0): (0, a), (0, 1): (3, c), (1, 0): (1, d), (1, 1): (2, d)上面的代碼中，每個hilbert_map的元素對應(yīng)圖7四個方形中的一個。為了容易區(qū)分，我用一個字母來標(biāo)識每個方塊：a是第一個方塊，b是第二

14、個，等等。每個方塊的值是個字典，將(子)象限的x, y坐標(biāo)映射到曲線上的位置（元組值的第一部分）以及下一個用到的方塊（元組值的第二部分）。下面的代碼展示了怎么用這個來將x, y坐標(biāo)轉(zhuǎn)換成希爾伯特曲線上的位置：12345678910def point_to_hilbert(x, y, order=16):current_square = aposition = 0for i in range(order - 1, -1, -1):position = 2quad_x = 1 if x & (1 i) else 0quad_y = 1 if y & (1 point_to_hilbert(5,2,

15、3)55對了！為了進一步測試，我們可以用這個函數(shù)生成一條希爾伯特曲線的有序點的完整列表，然后用電子制表軟件把它們畫出來看我們是否真的得到了一條希爾伯特曲線。在Python交互解釋器中輸入如下代碼：123 points = (x, y) for x in range(8) for y in range(8) sorted_points = sorted(points, key=lambda k: point_to_hilbert(k0, k1, 3) print n.join(%s,%s % x for x in sorted_points)將輸出的文本粘貼到文件中，保存為hilbert.csv，用你最喜歡的電子制表軟件打開，將數(shù)據(jù)畫成一個散點圖。結(jié)果當(dāng)然是一條漂亮的希爾伯特曲線！將hilbert_map做簡單的反轉(zhuǎn)就能實現(xiàn)point_to_hilbert的