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

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

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

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

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

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

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

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

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

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

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

12、進入象限3里面的方塊，在這個例子中，它是（圖7中的）第二個方塊。重復剛才的過程：我們的點落在哪個子象限？這次是左下角，意味著位置的下一部分是1（二進制01），我們將進入的小方塊又是第二個。最后一次重復這個過程，發現點落在右上角的子子象限，因此位置的最后部分是3（二進制11）。把這些位置連接起來，我們得到點在曲線上的位置是二進制的110111，或者十進制的55。圖8 三階希爾伯特曲線讓我們更系統一些，寫出從x, y坐標到希爾伯特曲線位置轉換的方法。首先，我們要以計算機看得懂的形式表達圖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的元素對應圖7四個方形中的一個。為了容易區分，我用一個字母來標識每個方塊：a是第一個方塊，b是第二

14、個，等等。每個方塊的值是個字典，將(子)象限的x, y坐標映射到曲線上的位置（元組值的第一部分）以及下一個用到的方塊（元組值的第二部分）。下面的代碼展示了怎么用這個來將x, y坐標轉換成希爾伯特曲線上的位置：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對了！為了進一步測試，我們可以用這個函數生成一條希爾伯特曲線的有序點的完整列表，然后用電子制表軟件把它們畫出來看我們是否真的得到了一條希爾伯特曲線。在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，用你最喜歡的電子制表軟件打開，將數據畫成一個散點圖。結果當然是一條漂亮的希爾伯特曲線！將hilbert_map做簡單的反轉就能實現point_to_hilbert的