## 附近地點搜索 ### 題目詳情 找一個點集中與給定點距離最近的點，同時，給定的二維點集都是固定的，查詢可能有很多次，時間復雜度O(n)無法接受，請設計數據結構和相應的算法。 ### 分析與解法 此題是去年微軟的三面題，類似于一朋友@陳利人出的這題：附近地點搜索，就是搜索用戶附近有哪些地點。隨著GPS和帶有GPS功能的移動設備的普及，附近地點搜索也變得炙手可熱。在龐大的地理數據庫中搜索地點，索引是很重要的。但是，我們的需求是搜索附近地點，例如，坐標(39.91, 116.37)附近500米內有什么餐館，那么讓你來設計，該怎么做？  #### 解法一：R樹二維搜索 假定只允許你初中數學知識，那么你可能建一個X-Y坐標系，即以坐標(39.91, 116.37)為圓心，以500的長度為半徑，畫一個園，然后一個一個坐標點的去查找。此法看似可行，但復雜度可想而知，即便你自以為聰明的說把整個平面劃分為四個象限，一個一個象限的查找，此舉雖然優化程度不夠，但也說明你一步步想到點子上去了。 即不一個一個坐標點的查找，而是一個一個區域的查找，相對來說，其平均查找速度和效率會顯著提升。如此，便自然而然的想到了有沒有一種一次查找定位于一個區域的數據結構呢？ 若看過博客內之前介紹R樹的[這篇文章](http://blog.csdn.net/v_JULY_v/article/details/6530142#t2)的讀者立馬便能意識到，R樹就是解決這個區域查找繼而不斷縮小規模的問題。特直接引用原文： >**R樹的數據結構** > R樹是B樹在高維空間的擴展，是一棵平衡樹。每個R樹的葉子結點包含了多個指向不同數據的指針，這些數據可以是存放在硬盤中的，也可以是存在內存中。根據R樹的這種數據結構，當我們需要進行一個高維空間查詢時，我們只需要遍歷少數幾個葉子結點所包含的指針，查看這些指針指向的數據是否滿足要求即可。這種方式使我們不必遍歷所有數據即可獲得答案，效率顯著提高。下圖1是R樹的一個簡單實例：  >我們在上面說過，R樹運用了空間分割的理念，這種理念是如何實現的呢？R樹采用了一種稱為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結點開始用矩形（rectangle）將空間框起來，結點越往上，框住的空間就越大，以此對空間進行分割。有點不懂？沒關系，繼續往下看。在這里我還想提一下，R樹中的R應該代表的是Rectangle（此處參考wikipedia上關于[R樹](http://en.wikipedia.org/wiki/R-tree)的介紹），而不是大多數國內教材中所說的Region（很多書把R樹稱為區域樹，這是有誤的）。我們就拿二維空間來舉例。下圖是Guttman論文中的一幅圖：  我來詳細解釋一下這張圖。 1. 先來看圖（b），首先我們假設所有數據都是二維空間下的點，圖中僅僅標志了R8區域中的數據，也就是那個shape of data object。別把那一塊不規則圖形看成一個數據，我們把它看作是多個數據圍成的一個區域。為了實現R樹結構，我們用一個最小邊界矩形恰好框住這個不規則區域，這樣，我們就構造出了一個區域：R8。R8的特點很明顯，就是正正好好框住所有在此區域中的數據。 2. 其他實線包圍住的區域，如R9，R10，R12等都是同樣的道理。這樣一來，我們一共得到了12個最最基本的最小矩形。這些矩形都將被存儲在子結點中。 3. 下一步操作就是進行高一層次的處理。我們發現R8，R9，R10三個矩形距離最為靠近，因此就可以用一個更大的矩形R3恰好框住這3個矩形。 4. 同樣道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形。 我想大家都應該理解這個數據結構的特征了。用地圖的例子來解釋，就是所有的數據都是餐廳所對應的地點，先把相鄰的餐廳劃分到同一塊區域，劃分好所有餐廳之后，再把鄰近的區域劃分到更大的區域，劃分完畢后再次進行更高層次的劃分，直到劃分到只剩下兩個最大的區域為止。要查找的時候就方便了。 下面就可以把這些大大小小的矩形存入我們的R樹中去了。根結點存放的是兩個最大的矩形，這兩個最大的矩形框住了所有的剩余的矩形，當然也就框住了所有的數據。下一層的結點存放了次大的矩形，這些矩形縮小了范圍。每個葉子結點都是存放的最小的矩形，這些矩形中可能包含有n個數據。 **地圖查找的實例** 講完了基本的數據結構，我們來講個實例，如何查詢特定的數據。又以餐廳為例，假設我要查詢廣州市天河區天河城附近一公里的所有餐廳地址怎么辦？ 1. 打開地圖（也就是整個R樹），先選擇國內還是國外（也就是根結點）； 2. 然后選擇華南地區（對應第一層結點），選擇廣州市（對應第二層結點）， 3. 再選擇天河區（對應第三層結點）； 4. 最后選擇天河城所在的那個區域（對應葉子結點，存放有最小矩形）； 遍歷所有在此區域內的結點，看是否滿足我們的要求即可。怎么樣，其實R樹的查找規則跟查地圖很像吧？對應下圖：  **一棵R樹滿足如下的性質：** 1. 除非它是根結點之外，所有葉子結點包含有m至M個記錄索引（條目）。作為根結點的葉子結點所具有的記錄個數可以少于m。通常，m=M/2。 2. 對于所有在葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴展到高維空間的）。 3. 每一個非葉子結點擁有m至M個孩子結點，除非它是根結點。 4. 對于在非葉子結點上的每一個條目，i是最小的可以在空間上完全覆蓋這些條目所代表的店的矩形（同性質2）。 5. 所有葉子結點都位于同一層，因此R樹為平衡樹。 **葉子結點的結構** 先來探究一下葉子結點的結構。葉子結點所保存的數據形式為：(I, tuple-identifier)。 其中，tuple-identifier表示的是一個存放于數據庫中的tuple，也就是一條記錄，它是n維的。I是一個n維空間的矩形，并可以恰好框住這個葉子結點中所有記錄代表的n維空間中的點。I=(I0,I1,…,In-1)。其結構如下圖所示：  下圖描述的就是在二維空間中的葉子結點所要存儲的信息。  在這張圖中，I所代表的就是圖中的矩形，其范圍是a<=I0<=b，c<=I1<=d。有兩個tuple-identifier，在圖中即表示為那兩個點。這種形式完全可以推廣到高維空間。大家簡單想想三維空間中的樣子就可以了。這樣，葉子結點的結構就介紹完了。 **非葉子結點** 非葉子結點的結構其實與葉子結點非常類似。想象一下B樹就知道了，B樹的葉子結點存放的是真實存在的數據，而非葉子結點存放的是這些數據的“邊界”，或者說也算是一種索引（有疑問的讀者可以回顧一下上述第一節中講解B樹的部分）。 同樣道理，R樹的非葉子結點存放的數據結構為：(I, child-pointer)。 其中，child-pointer是指向孩子結點的指針，I是覆蓋所有孩子結點對應矩形的矩形。這邊有點拗口，但我想不是很難懂？給張圖：  D,E,F,G為孩子結點所對應的矩形。A為能夠覆蓋這些矩形的更大的矩形。這個A就是這個非葉子結點所對應的矩形。這時候你應該悟到了吧？無論是葉子結點還是非葉子結點，它們都對應著一個矩形。樹形結構上層的結點所對應的矩形能夠完全覆蓋它的孩子結點所對應的矩形。根結點也唯一對應一個矩形，而這個矩形是可以覆蓋所有我們擁有的數據信息在空間中代表的點的。 我個人感覺這張圖畫的不那么精確，應該是矩形A要恰好覆蓋D,E,F,G，而不應該再留出這么多沒用的空間了。但為尊重原圖的繪制者，特不作修改。 但R樹有些什么問題呢？如@宋梟_CD所說：“單純用R樹來作索引，搜索附近的地點，可能會遍歷樹的很多個分支。而且當全國的地圖或者全省的地圖時候，樹的葉節點數目很多，樹的深度也會是一個問題。一般會把地理位置上附近的節點（二維地圖中點線面）預處理成page(大小為4K的倍數)，在這些page上建立R樹的索引。” #### 解法二：GeoHash算法索引地理位置信息 我在微博上跟一些朋友討論這個附近點搜索的問題時，除了談到R樹，有幾個朋友都指出GeoHash算法可以解決，故才了解了下GeoHash算法，[此文](http://blog.nosqlfan.com/html/1811.html) 清晰闡述了MongoDB借助GeoHash算法實現地理位置索引的原理，特引用其內容加以說明，如下： 支持地理位置索引是MongoDB的一大亮點，這也是全球最流行的LBS服務foursquare 選擇MongoDB的原因之一。我們知道，通常的數據庫索引結構是B+ Tree，如何將地理位置轉化為可建立B+Tree的形式。首先假設我們將需要索引的整個地圖分成16×16的方格，如下圖（左下角為坐標0,0 右上角為坐標16,16）：  單純的［x，y］的數據是無法建立索引的，所以MongoDB在建立索引的時候，會根據相應字段的坐標計算一個可以用來做索引的hash值，這個值叫做geohash，下面我們以地圖上坐標為［4，6］的點（圖中紅叉位置）為例。我們第一步將整個地圖分成等大小的四塊，如下圖：  劃分成四塊后我們可以定義這四塊的值，如下（左下為00，左上為01，右下為10，右上為11）：  這樣［4，6］點的geohash值目前為 00然后再將四個小塊每一塊進行切割，如下：  這時［4，6］點位于右上區域，右上的值為11，這樣［4，6］點的geohash值變為：0011繼續往下做兩次切分：   最終得到［4，6］點的geohash值為：00110100 這樣我們用這個值來做索引，則地圖上同一個分塊內相近的點就可以轉化成有相同前綴的geohash值了。 我們可以看到，這個geohash值的精確度是與劃分地圖的次數成正比的，上例對地圖劃分了四次。而MongoDB默認是進行26次劃分，這個值在建立索引時是可控的。具體建立二維地理位置索引的命令如下： db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4}) 其中的bits參數就是劃分幾次，默認為26次。 讀者點評@yuotulck：首先多謝博主的文章，不過如果是新手（例如我）看到geohash那里可能會有誤解：是否相鄰可以靠前綴來比較？其實這是錯的，例如邊界那一塊的相鄰區域編碼的前綴從第一個就不一樣了，也就是說在geohash里相近的點hash值不一定相近。 上面的知識點了解自[這篇文章](http://www.cnblogs.com/step1/archive/2009/04/22/1441689.html)，而geohash的進一步用法在[這里](http://tech.idv2.com/2011/07/05/geohash-intro/)可以了解到。 本章完。