搜索智能提示suggestion，附近地点搜索
題目詳情：百度搜索框中，輸入“北京”，搜索框下面會(huì)以北京為前綴，展示“北京愛(ài)情故事”、“北京公交”、“北京醫(yī)院”等等搜索詞，輸入“結(jié)構(gòu)之”，會(huì)提示“結(jié)構(gòu)之法”，“結(jié)構(gòu)之法 算法之道”等搜索詞。
請(qǐng)問(wèn)，如何設(shè)計(jì)此系統(tǒng)，使得空間和時(shí)間復(fù)雜度盡量低。
題目分析：本題來(lái)源于去年2012年百度的一套實(shí)習(xí)生筆試題中的系統(tǒng)設(shè)計(jì)題（為尊重愿題，本章主要使用百度搜索引擎展開(kāi)論述，而不是google等其它搜索引擎，但原理不會(huì)差太多。然脫離本題，平時(shí)搜的時(shí)候，鼓勵(lì)用...），題目比較開(kāi)放，考察的目的在于看應(yīng)聘者解決問(wèn)題的思路是否清晰明確，其次便是看能考慮到多少細(xì)節(jié)。
我去年整理此題的時(shí)候，曾簡(jiǎn)單解析過(guò)，提出的方法是：
直接上Trie樹(shù)「Trie樹(shù)的介紹見(jiàn)：從Trie樹(shù)（字典樹(shù)）談到后綴樹(shù)」 + ?TOP K「hashmap+堆，hashmap+堆 統(tǒng)計(jì)出如10個(gè)近似的熱詞，也就是說(shuō)，只存與關(guān)鍵詞近似的比如10個(gè)熱詞」
方法就是這樣子的：Trie樹(shù)+TOP K算法，但在實(shí)際中，真的只要Trie樹(shù) + TOP K算法就夠了么，有什么需要考慮的細(xì)節(jié)？OK，請(qǐng)看下文娓娓道來(lái)。
解法一、Trie樹(shù) + TOP K
步驟一、trie樹(shù)存儲(chǔ)前綴后綴
若看過(guò)博客內(nèi)這篇介紹Trie樹(shù)和后綴樹(shù)的文章http://blog.csdn.net/v_july_v/article/details/6897097的話(huà)，應(yīng)該就能對(duì)trie樹(shù)有個(gè)大致的了解，為示本文完整性，引用下原文內(nèi)容，如下：
“1.1、什么是Trie樹(shù)
?Trie樹(shù)，即字典樹(shù)，又稱(chēng)單詞查找樹(shù)或鍵樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希表高。
?Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢(xún)時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。
它有3個(gè)基本性質(zhì)：
根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
1.2、樹(shù)的構(gòu)建
舉個(gè)在網(wǎng)上流傳頗廣的例子，如下：
題目：給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個(gè)位置。
分析：這題當(dāng)然可以用hash來(lái)解決，但是本文重點(diǎn)介紹的是trie樹(shù)，因?yàn)樵谀承┓矫嫠挠猛靖蟆１热缯f(shuō)對(duì)于某一個(gè)單詞，我們要詢(xún)問(wèn)它的前綴是否出現(xiàn)過(guò)。這樣hash就不好搞了，而用trie還是很簡(jiǎn)單。
現(xiàn)在回到例子中，如果我們用最傻的方法，對(duì)于每一個(gè)單詞，我們都要去查找它前面的單詞中是否有它。那么這個(gè)算法的復(fù)雜度就是O(n^2)。顯然對(duì)于100000的范圍難以接受。現(xiàn)在我們換個(gè)思路想。假設(shè)我要查詢(xún)的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類(lèi)開(kāi)頭的我顯然不必考慮。而只要找以a開(kāi)頭的中是否存在abcd就可以了。同樣的，在以a開(kāi)頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的，一次次縮小范圍和提高針對(duì)性，這樣一個(gè)樹(shù)的模型就漸漸清晰了。
好比假設(shè)有b，abc，abd，bcd，abcd，efg，hii 這6個(gè)單詞，我們構(gòu)建的樹(shù)就是如下圖這樣的：
當(dāng)時(shí)第一次看到這幅圖的時(shí)候，便立馬感到此樹(shù)之不凡構(gòu)造了。單單從上幅圖便可窺知一二，好比大海搜人，立馬就能確定東南西北中的到底哪個(gè)方位，如此迅速縮小查找的范圍和提高查找的針對(duì)性，不失為一創(chuàng)舉。
ok，如上圖所示，對(duì)于每一個(gè)節(jié)點(diǎn)，從根遍歷到他的過(guò)程就是一個(gè)單詞，如果這個(gè)節(jié)點(diǎn)被標(biāo)記為紅色，就表示這個(gè)單詞存在，否則不存在。
那么，對(duì)于一個(gè)單詞，我只要順著他從根走到對(duì)應(yīng)的節(jié)點(diǎn)，再看這個(gè)節(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過(guò)了。把這個(gè)節(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。”
借用上面的圖，當(dāng)用戶(hù)輸入前綴a的時(shí)候，搜索框可能會(huì)展示以a為前綴的“abcd”，“abd”等關(guān)鍵詞，再當(dāng)用戶(hù)輸入前綴b的時(shí)候，搜索框下面可能會(huì)提示以b為前綴的“bcd”等關(guān)鍵詞，如此，實(shí)現(xiàn)搜索引擎智能提示suggestion的第一個(gè)步驟便清晰了，即用trie樹(shù)存儲(chǔ)大量字符串，當(dāng)前綴固定時(shí)，存儲(chǔ)相對(duì)來(lái)說(shuō)比較熱的后綴。那又如何統(tǒng)計(jì)熱詞呢？請(qǐng)看下文步驟二、TOP K算法統(tǒng)計(jì)熱詞。
?步驟二、TOP K算法統(tǒng)計(jì)熱詞
當(dāng)每個(gè)搜索引擎輸入一個(gè)前綴時(shí)，下面它只會(huì)展示0~10個(gè)候選詞，但若是碰到那種候選詞很多的時(shí)候，如何取舍，哪些展示在前面，哪些展示在后面？這就是一個(gè)搜索熱度的問(wèn)題。
如本題描述所說(shuō)，在去年的這個(gè)時(shí)候，當(dāng)我在搜索框內(nèi)搜索“北京”時(shí)，它下面會(huì)提示以“北京”為前綴的諸如“北京愛(ài)情故事”，“北京公交”，“北京醫(yī)院”，且“ 北京愛(ài)情故事”展示在第一個(gè)：
為何輸入“北京”，會(huì)首先提示“北京愛(ài)情故事”呢？因?yàn)槿ツ甑倪@個(gè)時(shí)候，正是《北京愛(ài)情故事》這部電影上映正火的時(shí)候（其上映日期為2012年1月8日，火了至少一年），那個(gè)時(shí)候大家都一個(gè)勁的搜索這部電影的相關(guān)信息，當(dāng)10個(gè)人中輸入“北京”后，其中有8個(gè)人會(huì)繼續(xù)敲入“愛(ài)情故事”（連起來(lái)就是“北京愛(ài)情故事”）的時(shí)候，搜索引擎對(duì)此當(dāng)然不會(huì)無(wú)動(dòng)于衷。
也就是說(shuō)，搜索引擎知道了這個(gè)時(shí)間段，大家都在瘋狂查找北京愛(ài)情故事，故當(dāng)用戶(hù)輸入以“北京”為前綴的時(shí)候，搜索引擎猜測(cè)用戶(hù)有80%的機(jī)率是要查找“北京愛(ài)情故事”，故把“北京愛(ài)情故事”在下面提示出來(lái)，并放在第一個(gè)位置上。
但為何今年這個(gè)時(shí)候再次搜索“北京”的時(shí)候，它展示出來(lái)的詞不同了呢？
原因在于隨著時(shí)間變化，人們對(duì)北京愛(ài)情故事這部影片的關(guān)注度逐漸下降，與此同時(shí)，又出現(xiàn)了新的熱詞，新的電影，故現(xiàn)在雖然同樣是輸入“北京”，后面提示的詞也相應(yīng)跟著起了變化。那解決這個(gè)問(wèn)題的辦法是什么呢？如開(kāi)頭所說(shuō)：定期分析某段時(shí)間內(nèi)的人們搜索的關(guān)鍵詞，統(tǒng)計(jì)出搜索次數(shù)比較多的熱詞，繼而當(dāng)用戶(hù)輸入某個(gè)前綴時(shí)，優(yōu)先展示熱詞。
故說(shuō)白了，這個(gè)問(wèn)題的第二個(gè)步驟便是統(tǒng)計(jì)熱詞，我們把統(tǒng)計(jì)熱詞的方法稱(chēng)為T(mén)OP K算法，此算法的應(yīng)用場(chǎng)景便是此文http://blog.csdn.net/v_july_v/article/details/7382693中的第2個(gè)問(wèn)題，再次原文引用：
“尋找熱門(mén)查詢(xún)，300萬(wàn)個(gè)查詢(xún)字符串中統(tǒng)計(jì)最熱門(mén)的10個(gè)查詢(xún)
原題：搜索引擎會(huì)通過(guò)日志文件把用戶(hù)每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢(xún)串的長(zhǎng)度為1-255字節(jié)。假設(shè)目前有一千萬(wàn)個(gè)記錄（這些查詢(xún)串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢(xún)串的重復(fù)度越高，說(shuō)明查詢(xún)它的用戶(hù)越多，也就是越熱門(mén)），請(qǐng)你統(tǒng)計(jì)最熱門(mén)的10個(gè)查詢(xún)串，要求使用的內(nèi)存不能超過(guò)1G。
解答：由上面第1題，我們知道，數(shù)據(jù)大則劃為小的，如一億個(gè)Ip求Top 10，可先%1000將ip分到1000個(gè)小文件中去，并保證一種ip只出現(xiàn)在一個(gè)文件中，再對(duì)每個(gè)小文件中的ip進(jìn)行hashmap計(jì)數(shù)統(tǒng)計(jì)并按數(shù)量排序，最后歸并或者最小堆依次處理每個(gè)小文件的top10以得到最后的結(jié)果。
但如果數(shù)據(jù)規(guī)模本身就比較小，能一次性裝入內(nèi)存呢？比如這第2題，雖然有一千萬(wàn)個(gè)Query，但是由于重復(fù)度比較高，因此事實(shí)上只有300萬(wàn)的Query，每個(gè)Query255Byte，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去（300萬(wàn)個(gè)字符串假設(shè)沒(méi)有重復(fù)，都是最大長(zhǎng)度，那么最多占用內(nèi)存3M*1K/4=0.75G。所以可以將所有字符串都存放在內(nèi)存中進(jìn)行處理），而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，在這里，HashTable絕對(duì)是我們優(yōu)先的選擇。
所以我們放棄分而治之/hash映射的步驟，直接上hash統(tǒng)計(jì)，然后排序。So，針對(duì)此類(lèi)典型的TOP K問(wèn)題，采取的對(duì)策往往是：hashmap + 堆。如下所示：
hashmap統(tǒng)計(jì)：先對(duì)這批海量數(shù)據(jù)預(yù)處理。具體方法是：維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable，即hash_map(Query，Value)，每次讀取一個(gè)Query，如果該字串不在Table中，那么加入該字串，并且將Value值設(shè)為1；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可。最終我們?cè)贠(N)的時(shí)間復(fù)雜度內(nèi)用Hash表完成了統(tǒng)計(jì)；
堆排序：第二步、借助堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，找出Top K，時(shí)間復(fù)雜度為N‘logK。即借助堆結(jié)構(gòu)，我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此，維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷300萬(wàn)的Query，分別和根元素進(jìn)行對(duì)比。所以，我們最終的時(shí)間復(fù)雜度是：O（N） + N' * O（logK），（N為1000萬(wàn)，N’為300萬(wàn)）。
別忘了這篇文章中所述的堆排序思路：‘維護(hù)k個(gè)元素的最小堆，即用容量為k的最小堆存儲(chǔ)最先遍歷到的k個(gè)數(shù)，并假設(shè)它們即是最大的k個(gè)數(shù)，建堆費(fèi)時(shí)O（k），并調(diào)整堆(費(fèi)時(shí)O（logk）)后，有k1>k2>...kmin（kmin設(shè)為小頂堆中最小元素）。繼續(xù)遍歷數(shù)列，每次遍歷一個(gè)元素x，與堆頂元素比較，若x>kmin，則更新堆（x入堆，用時(shí)logk），否則不更新堆。這樣下來(lái)，總費(fèi)時(shí)O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各項(xiàng)操作時(shí)間復(fù)雜度均為logk。’--第三章續(xù)、Top K算法問(wèn)題的實(shí)現(xiàn)。
當(dāng)然，你也可以采用trie樹(shù)，關(guān)鍵字域存該查詢(xún)串出現(xiàn)的次數(shù)，沒(méi)有出現(xiàn)為0。最后用10個(gè)元素的最小推來(lái)對(duì)出現(xiàn)頻率進(jìn)行排序。”
相信，如此，也就不難理解開(kāi)頭所提出的方法了：Trie樹(shù)+ ?TOP K「hashmap+堆，hashmap+堆 統(tǒng)計(jì)出如10個(gè)近似的熱詞，也就是說(shuō)，只存與關(guān)鍵詞近似的比如10個(gè)熱詞」。
而且你以后就可以告訴你身邊的伙伴們，為何輸入“結(jié)構(gòu)之”，會(huì)提示出來(lái)一堆以“結(jié)構(gòu)之”為前綴的詞拉：
? ??
方法貌似成型了，但有哪些需要注意的細(xì)節(jié)呢？如@江申_Johnson所說(shuō)：“實(shí)際工作里，比如當(dāng)前綴很短的時(shí)候，候選詞很多的時(shí)候，查詢(xún)和排序性能可能有問(wèn)題，也許可以加一層索引trie（這層索引可以只索引頻率高于某一個(gè)閾值的詞，很短的時(shí)候查這個(gè)就可以了。數(shù)量不夠的話(huà)再去查索引了全部詞的trie樹(shù)）；而且有時(shí)候不能根據(jù)query頻率來(lái)排，而要引導(dǎo)用戶(hù)輸入信息量更全面的query，或者或不僅僅是前綴匹配這么簡(jiǎn)單。”
擴(kuò)展閱讀
除了上文提到的trie樹(shù)，三叉樹(shù)或許也是一個(gè)不錯(cuò)的解決方案：http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/。此外，StackOverflow上也有兩個(gè)討論帖子，大家可以看看：①http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete，②http://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c。
附近地點(diǎn)搜索
題目詳情：找一個(gè)點(diǎn)集中與給定點(diǎn)距離最近的點(diǎn)，同時(shí)，給定的二維點(diǎn)集都是固定的，查詢(xún)可能有很多次，時(shí)間復(fù)雜度O(n)無(wú)法接受，請(qǐng)?jiān)O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的算法。
題目分析：此題是去年微軟的三面題，類(lèi)似于一朋友@陳利人 出的這題：附近地點(diǎn)搜索，就是搜索用戶(hù)附近有哪些地點(diǎn)。隨著GPS和帶有GPS功能的移動(dòng)設(shè)備的普及，附近地點(diǎn)搜索也變得炙手可熱。在龐大的地理數(shù)據(jù)庫(kù)中搜索地點(diǎn)，索引是很重要的。但是，我們的需求是搜索附近地點(diǎn)，例如，坐標(biāo)(39.91, 116.37)附近500米內(nèi)有什么餐館，那么讓你來(lái)設(shè)計(jì)，該怎么做？
解法一、R樹(shù)二維搜索
假定只允許你初中數(shù)學(xué)知識(shí)，那么你可能建一個(gè)X-Y坐標(biāo)系，即以坐標(biāo)(39.91, 116.37)為圓心，以500的長(zhǎng)度為半徑，畫(huà)一個(gè)園，然后一個(gè)一個(gè)坐標(biāo)點(diǎn)的去查找。此法看似可行，但復(fù)雜度可想而知，即便你自以為聰明的說(shuō)把整個(gè)平面劃分為四個(gè)象限，一個(gè)一個(gè)象限的查找，此舉雖然優(yōu)化程度不夠，但也說(shuō)明你一步步想到點(diǎn)子上去了。
即不一個(gè)一個(gè)坐標(biāo)點(diǎn)的查找，而是一個(gè)一個(gè)區(qū)域的查找，相對(duì)來(lái)說(shuō)，其平均查找速度和效率會(huì)顯著提升。如此，便自然而然的想到了有沒(méi)有一種一次查找定位于一個(gè)區(qū)域的數(shù)據(jù)結(jié)構(gòu)呢？
若看過(guò)博客內(nèi)之前介紹R樹(shù)的這篇文章http://blog.csdn.net/v_JULY_v/article/details/6530142#t2?的讀者立馬便能意識(shí)到，R樹(shù)就是解決這個(gè)區(qū)域查找繼而不斷縮小規(guī)模的問(wèn)題。特直接引用原文：
“R樹(shù)的數(shù)據(jù)結(jié)構(gòu)
R樹(shù)是B樹(shù)在高維空間的擴(kuò)展，是一棵平衡樹(shù)。每個(gè)R樹(shù)的葉子結(jié)點(diǎn)包含了多個(gè)指向不同數(shù)據(jù)的指針，這些數(shù)據(jù)可以是存放在硬盤(pán)中的，也可以是存在內(nèi)存中。根據(jù)R樹(shù)的這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們需要進(jìn)行一個(gè)高維空間查詢(xún)時(shí)，我們只需要遍歷少數(shù)幾個(gè)葉子結(jié)點(diǎn)所包含的指針，查看這些指針指向的數(shù)據(jù)是否滿(mǎn)足要求即可。這種方式使我們不必遍歷所有數(shù)據(jù)即可獲得答案，效率顯著提高。下圖1是R樹(shù)的一個(gè)簡(jiǎn)單實(shí)例：
我們?cè)谏厦嬲f(shuō)過(guò)，R樹(shù)運(yùn)用了空間分割的理念，這種理念是如何實(shí)現(xiàn)的呢？R樹(shù)采用了一種稱(chēng)為MBR(Minimal Bounding Rectangle)的方法，在此我把它譯作“最小邊界矩形”。從葉子結(jié)點(diǎn)開(kāi)始用矩形（rectangle）將空間框起來(lái)，結(jié)點(diǎn)越往上，框住的空間就越大，以此對(duì)空間進(jìn)行分割。有點(diǎn)不懂？沒(méi)關(guān)系，繼續(xù)往下看。在這里我還想提一下，R樹(shù)中的R應(yīng)該代表的是Rectangle（此處參考wikipedia上關(guān)于R樹(shù)的介紹），而不是大多數(shù)國(guó)內(nèi)教材中所說(shuō)的Region（很多書(shū)把R樹(shù)稱(chēng)為區(qū)域樹(shù)，這是有誤的）。我們就拿二維空間來(lái)舉例。下圖是Guttman論文中的一幅圖：
?
? ? 我來(lái)詳細(xì)解釋一下這張圖。
先來(lái)看圖（b），首先我們假設(shè)所有數(shù)據(jù)都是二維空間下的點(diǎn)，圖中僅僅標(biāo)志了R8區(qū)域中的數(shù)據(jù)，也就是那個(gè)shape of data object。別把那一塊不規(guī)則圖形看成一個(gè)數(shù)據(jù)，我們把它看作是多個(gè)數(shù)據(jù)圍成的一個(gè)區(qū)域。為了實(shí)現(xiàn)R樹(shù)結(jié)構(gòu)，我們用一個(gè)最小邊界矩形恰好框住這個(gè)不規(guī)則區(qū)域，這樣，我們就構(gòu)造出了一個(gè)區(qū)域：R8。R8的特點(diǎn)很明顯，就是正正好好框住所有在此區(qū)域中的數(shù)據(jù)。
其他實(shí)線(xiàn)包圍住的區(qū)域，如R9，R10，R12等都是同樣的道理。這樣一來(lái)，我們一共得到了12個(gè)最最基本的最小矩形。這些矩形都將被存儲(chǔ)在子結(jié)點(diǎn)中。
下一步操作就是進(jìn)行高一層次的處理。我們發(fā)現(xiàn)R8，R9，R10三個(gè)矩形距離最為靠近，因此就可以用一個(gè)更大的矩形R3恰好框住這3個(gè)矩形。
同樣道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形。
我想大家都應(yīng)該理解這個(gè)數(shù)據(jù)結(jié)構(gòu)的特征了。用地圖的例子來(lái)解釋，就是所有的數(shù)據(jù)都是餐廳所對(duì)應(yīng)的地點(diǎn)，先把相鄰的餐廳劃分到同一塊區(qū)域，劃分好所有餐廳之后，再把鄰近的區(qū)域劃分到更大的區(qū)域，劃分完畢后再次進(jìn)行更高層次的劃分，直到劃分到只剩下兩個(gè)最大的區(qū)域?yàn)橹埂Ｒ檎业臅r(shí)候就方便了。
下面就可以把這些大大小小的矩形存入我們的R樹(shù)中去了。根結(jié)點(diǎn)存放的是兩個(gè)最大的矩形，這兩個(gè)最大的矩形框住了所有的剩余的矩形，當(dāng)然也就框住了所有的數(shù)據(jù)。下一層的結(jié)點(diǎn)存放了次大的矩形，這些矩形縮小了范圍。每個(gè)葉子結(jié)點(diǎn)都是存放的最小的矩形，這些矩形中可能包含有n個(gè)數(shù)據(jù)。
地圖查找的實(shí)例
講完了基本的數(shù)據(jù)結(jié)構(gòu)，我們來(lái)講個(gè)實(shí)例，如何查詢(xún)特定的數(shù)據(jù)。又以餐廳為例，假設(shè)我要查詢(xún)廣州市天河區(qū)天河城附近一公里的所有餐廳地址怎么辦？
打開(kāi)地圖（也就是整個(gè)R樹(shù)），先選擇國(guó)內(nèi)還是國(guó)外（也就是根結(jié)點(diǎn)）；
然后選擇華南地區(qū)（對(duì)應(yīng)第一層結(jié)點(diǎn)），選擇廣州市（對(duì)應(yīng)第二層結(jié)點(diǎn)），
再選擇天河區(qū)（對(duì)應(yīng)第三層結(jié)點(diǎn)）；
最后選擇天河城所在的那個(gè)區(qū)域（對(duì)應(yīng)葉子結(jié)點(diǎn)，存放有最小矩形）；
遍歷所有在此區(qū)域內(nèi)的結(jié)點(diǎn)，看是否滿(mǎn)足我們的要求即可。怎么樣，其實(shí)R樹(shù)的查找規(guī)則跟查地圖很像吧？對(duì)應(yīng)下圖：
? ? ? ??
一棵R樹(shù)滿(mǎn)足如下的性質(zhì)：
除非它是根結(jié)點(diǎn)之外，所有葉子結(jié)點(diǎn)包含有m至M個(gè)記錄索引（條目）。作為根結(jié)點(diǎn)的葉子結(jié)點(diǎn)所具有的記錄個(gè)數(shù)可以少于m。通常，m=M/2。
對(duì)于所有在葉子中存儲(chǔ)的記錄（條目），I是最小的可以在空間中完全覆蓋這些記錄所代表的點(diǎn)的矩形（注意：此處所說(shuō)的“矩形”是可以擴(kuò)展到高維空間的）。
每一個(gè)非葉子結(jié)點(diǎn)擁有m至M個(gè)孩子結(jié)點(diǎn)，除非它是根結(jié)點(diǎn)。
對(duì)于在非葉子結(jié)點(diǎn)上的每一個(gè)條目，i是最小的可以在空間上完全覆蓋這些條目所代表的店的矩形（同性質(zhì)2）。
所有葉子結(jié)點(diǎn)都位于同一層，因此R樹(shù)為平衡樹(shù)。
葉子結(jié)點(diǎn)的結(jié)構(gòu)
先來(lái)探究一下葉子結(jié)點(diǎn)的結(jié)構(gòu)。葉子結(jié)點(diǎn)所保存的數(shù)據(jù)形式為：(I, tuple-identifier)。
其中，tuple-identifier表示的是一個(gè)存放于數(shù)據(jù)庫(kù)中的tuple，也就是一條記錄，它是n維的。I是一個(gè)n維空間的矩形，并可以恰好框住這個(gè)葉子結(jié)點(diǎn)中所有記錄代表的n維空間中的點(diǎn)。I=(I0,I1,…,In-1)。其結(jié)構(gòu)如下圖所示：
下圖描述的就是在二維空間中的葉子結(jié)點(diǎn)所要存儲(chǔ)的信息。
?
在這張圖中，I所代表的就是圖中的矩形，其范圍是a<=I0<=b，c<=I1<=d。有兩個(gè)tuple-identifier，在圖中即表示為那兩個(gè)點(diǎn)。這種形式完全可以推廣到高維空間。大家簡(jiǎn)單想想三維空間中的樣子就可以了。這樣，葉子結(jié)點(diǎn)的結(jié)構(gòu)就介紹完了。
非葉子結(jié)點(diǎn)
非葉子結(jié)點(diǎn)的結(jié)構(gòu)其實(shí)與葉子結(jié)點(diǎn)非常類(lèi)似。想象一下B樹(shù)就知道了，B樹(shù)的葉子結(jié)點(diǎn)存放的是真實(shí)存在的數(shù)據(jù)，而非葉子結(jié)點(diǎn)存放的是這些數(shù)據(jù)的“邊界”，或者說(shuō)也算是一種索引（有疑問(wèn)的讀者可以回顧一下上述第一節(jié)中講解B樹(shù)的部分）。
同樣道理，R樹(shù)的非葉子結(jié)點(diǎn)存放的數(shù)據(jù)結(jié)構(gòu)為：(I, child-pointer)。
其中，child-pointer是指向孩子結(jié)點(diǎn)的指針，I是覆蓋所有孩子結(jié)點(diǎn)對(duì)應(yīng)矩形的矩形。這邊有點(diǎn)拗口，但我想不是很難懂？給張圖：
?
D,E,F,G為孩子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。A為能夠覆蓋這些矩形的更大的矩形。這個(gè)A就是這個(gè)非葉子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。這時(shí)候你應(yīng)該悟到了吧？無(wú)論是葉子結(jié)點(diǎn)還是非葉子結(jié)點(diǎn)，它們都對(duì)應(yīng)著一個(gè)矩形。樹(shù)形結(jié)構(gòu)上層的結(jié)點(diǎn)所對(duì)應(yīng)的矩形能夠完全覆蓋它的孩子結(jié)點(diǎn)所對(duì)應(yīng)的矩形。根結(jié)點(diǎn)也唯一對(duì)應(yīng)一個(gè)矩形，而這個(gè)矩形是可以覆蓋所有我們擁有的數(shù)據(jù)信息在空間中代表的點(diǎn)的。
我個(gè)人感覺(jué)這張圖畫(huà)的不那么精確，應(yīng)該是矩形A要恰好覆蓋D,E,F,G，而不應(yīng)該再留出這么多沒(méi)用的空間了。但為尊重原圖的繪制者，特不作修改。”
但R樹(shù)有些什么問(wèn)題呢？如@宋梟_CD所說(shuō)：“單純用R樹(shù)來(lái)作索引，搜索附近的地點(diǎn)，可能會(huì)遍歷樹(shù)的很多個(gè)分支。而且當(dāng)全國(guó)的地圖或者全省的地圖時(shí)候，樹(shù)的葉節(jié)點(diǎn)數(shù)目很多，樹(shù)的深度也會(huì)是一個(gè)問(wèn)題。一般會(huì)把地理位置上附近的節(jié)點(diǎn)（二維地圖中點(diǎn)線(xiàn)面）預(yù)處理成page(大小為4K的倍數(shù))，在這些page上建立R樹(shù)的索引。”
解法二、GeoHash算法索引地理位置信息
我在微博上跟一些朋友討論這個(gè)附近點(diǎn)搜索的問(wèn)題時(shí)，除了談到R樹(shù)，有幾個(gè)朋友都指出GeoHash算法可以解決，故才了解了下GeoHash算法，此文http://blog.nosqlfan.com/html/1811.html?清晰闡述了MongoDB借助GeoHash算法實(shí)現(xiàn)地理位置索引的原理，特引用其內(nèi)容加以說(shuō)明，如下：
“支持地理位置索引是MongoDB的一大亮點(diǎn)，這也是全球最流行的LBS服務(wù)foursquare?選擇MongoDB的原因之一。我們知道，通常的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)是B+?Tree，如何將地理位置轉(zhuǎn)化為可建立B+Tree的形式。首先假設(shè)我們將需要索引的整個(gè)地圖分成16×16的方格，如下圖（左下角為坐標(biāo)0,0?右上角為坐標(biāo)16,16）：
單純的［x，y］的數(shù)據(jù)是無(wú)法建立索引的，所以MongoDB在建立索引的時(shí)候，會(huì)根據(jù)相應(yīng)字段的坐標(biāo)計(jì)算一個(gè)可以用來(lái)做索引的hash值，這個(gè)值叫做geohash，下面我們以地圖上坐標(biāo)為［4，6］的點(diǎn)（圖中紅叉位置）為例。我們第一步將整個(gè)地圖分成等大小的四塊，如下圖：
劃分成四塊后我們可以定義這四塊的值，如下（左下為00，左上為01，右下為10，右上為11）：
這樣［4，6］點(diǎn)的geohash值目前為?00然后再將四個(gè)小塊每一塊進(jìn)行切割，如下：
這時(shí)［4，6］點(diǎn)位于右上區(qū)域，右上的值為11，這樣［4，6］點(diǎn)的geohash值變?yōu)?#xff1a;0011繼續(xù)往下做兩次切分：
最終得到［4，6］點(diǎn)的geohash值為：00110100
這樣我們用這個(gè)值來(lái)做索引，則地圖上點(diǎn)相近的點(diǎn)就可以轉(zhuǎn)化成有相同前綴的geohash值了。
我們可以看到，這個(gè)geohash值的精確度是與劃分地圖的次數(shù)成正比的，上例對(duì)地圖劃分了四次。而MongoDB默認(rèn)是進(jìn)行26次劃分，這個(gè)值在建立索引時(shí)是可控的。具體建立二維地理位置索引的命令如下：
? ? 其中的bits參數(shù)就是劃分幾次，默認(rèn)為26次。?”
本章完。
作者：July
來(lái)源：http://www.cnblogs.com/v-July-v/p/3320869.html
-----------------
明明共同關(guān)注公眾號(hào)，彼此卻互不認(rèn)識(shí)；
明明具有相同的愛(ài)好，卻無(wú)緣相識(shí)；
有沒(méi)有覺(jué)得這就是上帝給我們的一個(gè)bug！
想不想認(rèn)識(shí)更多寫(xiě)程序的小伙伴？
C++，Java，VB……應(yīng)有盡有。
還等什么？趕快上車(chē)加入我們吧！
(･??･?)っ算法與數(shù)學(xué)之美-計(jì)算機(jī)粉絲群
我們?cè)谶@里等你喲
算法數(shù)學(xué)之美微信公眾號(hào)歡迎賜稿
稿件涉及數(shù)學(xué)、物理、算法、計(jì)算機(jī)、編程等相關(guān)領(lǐng)域。
稿件一經(jīng)采用，我們將奉上稿酬。
投稿郵箱：math_alg@163.com
商務(wù)合作：微信號(hào)hengzi5809
總結(jié)
以上是生活随笔為你收集整理的搜索智能提示suggestion，附近地点搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： android web 访问数据库,We
- 下一篇： np.triu