LBS資料庫的架構是怎樣的？
基於坐標的信息，是如何做索引和搜索的？
何提高緩存命中率？
架構的話有很多嘗試，傳統的Oracle和 Postgre用的比較廣泛, 很多架構在此基礎上同時應用 NoSQL。因為大多數LBS並不涉及更複雜的空間數據存儲，例如多邊形或者三維數據，因此，大多數generic的資料庫架構都可以應用。但是，從產品核心的設計以及發展來看，如果像FourSquare(4SQ)進行數據挖掘並提供收費的數據分析服務，那麼基於空間的利用文件數據結構，以空間POI為基礎的NoSQL，是比較好的選擇。除了其他人介紹的很多LBS，比如街旁和4SQ，應用的Mongo DB， 還有Couch DB, 根據之前來講課的澳洲政府的一個大型空間資料庫項目(集成了多種現有的空間資料庫)的構架師介紹，這個項目應用了Couch DB。雖然理論上Graphic的NoSQL對於存儲空間數據也有很大優勢，但是畢竟相對不成熟，所以實際應用中的NoSQL還是以doc結構的Mongo和Couch為主。
如何提高命中率關鍵是對存儲的空間數據認識程度和對用戶query的類型的統計分析，並在此基礎上開發出適合的演算法，建立緩存或者對傳統的空間索引進行組合，例如應用一些refine-filter策略。空間數據的索引與傳統的索引不同，但是又部分基於傳統索引的基礎之上的。這裡只介紹一些簡單的空間索引入門演算法，最後簡單談一下緩存建立的策略。
-----------------------------------索引------------------------------------------------------------------------
----簡略介紹一下作為空間索引基礎的一般索引,並由此為基礎應用部分B tree思想並組合其他一些方法進行空間索引。
B-Tree/B+Tree 定義的話學過資料庫應該都了解。這是常用的一般性索引。從0-100 這一百個數找到40這個，可以用過100 -&> (0-50), (51-100) 在（1-50）裡面查詢，然後再從（1-25）（26-50）裡面的（26-50）裡面查詢。通過它的平衡性，每次減少一半的數據，所以查詢時間是O(log n)。1-&>100是一個一維的線性關係。
----從一維到二維（當然也有三維但是那個更複雜，不在這裡討論之列）
因為空間的每個object的首先是表現在二維空間的點，線或者多邊形。這個帖子因為問的是LBS,因此主要的目的是存儲points的POI(Points of interesting)以及它附屬的屬性。二維空間的索引為什麼傳統的B tree 不可以呢？看下圖：
------二維的順序。
好的二維排序方法應該兼顧順序和空間遠近的相對關係，就是上個例子中點1和5的順序應該是點1和2，這樣就保存了空間相似行和順序的正相關。可以應用的空間order 總結下來有如下：
(Hanan Samet, Foundations of Multidimensional and Metric Data Structures,p199)
這些方式有利有弊，例如圖a,第一行最右邊的點8和第二行最右邊的點16空間關係很近，但是，序號卻相差8。但是，在同一行空間關係保持的與序號相關性保持的很好。----柵格結構
從以上的order中發現，這都是基於柵格結構把空間分割成柵格，從而編號成為index的。柵格的存儲點的空間object的index，常用的方式是Region Quadtrees。 什麼是Quadtrees的存儲方式呢？
1. Point Quadtree
見圖：
2.2D-Tree
與Point Quadtree類似。但是它不把空間分隔成4個部分而是兩個。如圖：
當然，更複雜的地理信息資料庫中，線，多邊形和三維objects都會有存儲，因此他們的index方法也不同於點。一般來說，越複雜的object index的方法也越複雜，
-----------------------------------緩存------------------------------------------------------------------------
下面簡單說明一下緩存的建立思路。這個無法進行詳細說明，因為往往都是要根據業務需求進行設計的。簡單流程是分析業務主流的query類型-》根據query類型設計緩存。只有理解query類型，才能理解查詢過程中應用的演算法。這麼做目的有2個：1是盡量避免用計算量大耗時長的演算法來取得query結果，2是如果避免不了就進行預計算。
所以首先是要理解空間query的類型，按照計算量從小到大順序排列的query類型是。1.空間選擇查詢.例如，找到距離火車站200米以內的5星評價的飯店。2.最近鄰居查詢.例如，距離火車站最近的2個飯店/火車站到北京飯店的駕車距離是多少
3.拓撲關係查詢。例如，王府井是否在北京市。這裡如果都是LBS的話， 其實簡單很多，因為點與線或者多邊形的距離和拓撲結構的演算法是很簡單的，而多邊形和多邊形就複雜得多。
假設，LBS的query，是大眾點評式的。用戶最多的query應該是類似：
距離我現在的位置最近的的港式餐廳按評價排序結果。這個是一個典型的空間選擇查詢。那麼，緩存的策略可以按照用戶集中地地區，預先查詢出一些常用的餐廳類型的文件，做成緩存。相對於其他的地理信息查詢，LBS的緩存還是好做的。
大家可以感受一下這個query：找到所有國內的城市，它最近的河流全部是在這個城市所在的省之外。這個query涉及了線和多邊形的拓撲結構查詢（省之外）和最近鄰居查詢（最近的河流）的組合查詢，
如果用戶都是這種query，那麼做緩存的策略人就要蛋疼了！！！！具體操作就要考慮預先計算省的多邊形的最小bounding box了。之後這裡涉及比較複雜的緩存策略就省略..寫起來就不是幾句話能講清楚得了。----------------------------------------------------------------------------------------------------------------最後感謝我的資料庫老師Matt Duckham，也就是多次截取圖片的原書作者。（1）
空間索引（Spatial Index）。主流資料庫（MySQL 5.0+、Oracle、PostgreSQL、SQL Server） 都在不同程度上支持歐空間索引，其中有一個類型就是 Point，可以用於存儲 POI 的經緯度。
至於檢索效率的提高，可以採用資料庫廠家提供的 OpenGIS 函數，比如 DISTANCE 什麼的。
（2）即使不支持空間索引也沒關係，傳統的坐標存儲也可以實現，會稍微複雜點，同時在經緯度上建立好複合索引。全球最大的LBS應用4sq用的MongoDB，國內的街旁也用的MongoDB。
安利一個我們實驗室做的基於Apache Spark的分散式GIS處理框架，現在主要由我在進行日常維護： DataSystemsLab/GeoSpark 源碼host在GitHub上面，Jar包host在Maven Central Repository。Apache Spark的Third Party Project頁面也把GeoSpark列為Infrastructure Project：Third-Party Projects | Apache Spark
GeoSpark支持分散式空間索引例如R-Tree Quad-Tree 空間查詢 Range query，KNN query， Distance Join query，Range Join Query.
用戶可以把GeoSpark輕鬆地導入他自己的GIS項目程序裡面，然後用分散式集群對大規模空間數據進行坐標轉換，處理，查詢和可視化。用戶亦可直接使用Scala shell直接導入GeoSpark，進行互動式處理。
現在有一些中小型GIS公司用在他們的生產和測試環境裡面，還有兩家FLAG級別的公司在用（由於隱私控制的原因暫時不能透露）。
歡迎大家使用，貢獻代碼，或者提出意見！
rtee，geohash
像微信的搖一搖，臨時定位搜索的功能 如果用mysql 的memery引擎 性能能否跟得上
推薦閱讀：