先看幾個需要空間索引技術(shù)的場景：

如何根據(jù)給定位置來查詢附近1000米的poi？

如何查找給定位置的最近poi?

如何查找給定矩形框內(nèi)所有l(wèi)ink和面數(shù)據(jù)？

1.用B-tree、B tree或者h(yuǎn)ash算法對空間數(shù)據(jù)建索引可以嗎？

B-tree是平衡多路查找樹，在節(jié)點(diǎn)上及其子節(jié)點(diǎn)上存放有序的關(guān)鍵字，非葉子節(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)等于指向子樹指針數(shù)減1；查找從根節(jié)點(diǎn)開始，葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都有可能命中。

B tree的非葉子節(jié)點(diǎn)子樹指針數(shù)和關(guān)鍵字?jǐn)?shù)相等，所有關(guān)鍵字都存儲在葉子節(jié)點(diǎn)中，非葉子節(jié)點(diǎn)不存儲數(shù)據(jù)，只存儲關(guān)鍵字，為葉子節(jié)點(diǎn)增加鏈表指針；查找也從根節(jié)點(diǎn)開始搜索，到葉子節(jié)點(diǎn)才能命中。性能等價于對關(guān)鍵字全集做一次二分查找。更適合做文件索引系統(tǒng)。

hash索引用hash值指針指向關(guān)鍵字位置；

這三種索引都是基于關(guān)鍵字，不能滿足二維及多維空間信息索引。

2.根據(jù)空間點(diǎn)數(shù)據(jù)特性，我設(shè)計了一種基于二分查找的一種簡單快速查找最近poi的算法

對每個poi計算一個到原點(diǎn)的距離，按地區(qū)編碼adcode和這個原點(diǎn)距離兩個字段排序，并計算出每個adcode的開始索引和結(jié)束索引，當(dāng)根據(jù)給定位置查找最近poi時，先按adcode查找到這個adcode的開始索引和結(jié)束索引，再根據(jù)原點(diǎn)距離，查找到其buffer內(nèi)的記錄，然后向兩頭分別查找，當(dāng)超出buffer范圍時跳出，通過比較找到最近poi。也可以通過這種方法計算出附近范圍內(nèi)的所有poi。

這個算法預(yù)先處理出基于數(shù)組的數(shù)據(jù)，有效劃分了數(shù)據(jù)集合，時間復(fù)雜度接近略高于二分查找，有較高的查找性能。

優(yōu)點(diǎn)：編程實現(xiàn)簡單，比較適合點(diǎn)數(shù)據(jù)

缺點(diǎn)：當(dāng)沒有adcode字段時查找性能會大幅下降，線、面、圓、多邊形等數(shù)據(jù)類型基本不可用。傳統(tǒng)的這幾種數(shù)據(jù)結(jié)構(gòu)不能滿足多類型多場景查詢空間數(shù)據(jù)的索引！

3.幾種高級空間索引算法：網(wǎng)格空間索引、四叉樹、R樹、kd-tree

1)網(wǎng)格空間索引

將平面等分成網(wǎng)格，是一種平均劃分，用哈希數(shù)據(jù)結(jié)構(gòu)，索引項上記錄落入該網(wǎng)格的空間對象，用下圖方式將相應(yīng)空間對象記錄到每個索引網(wǎng)格中，建立索引。

查找某個矩形框內(nèi)空間對象時，確定所畫矩形左上角和右下角所在的網(wǎng)格數(shù)組元素；即可得到這個矩形所關(guān)聯(lián)覆蓋的所有網(wǎng)格集合，然后即可通過索引獲取到其中的空間對象。

網(wǎng)格越多查找性能越好，但是空間冗余度越高，網(wǎng)格太少，劃分就越少，就降低了查找性能。

優(yōu)點(diǎn)：在點(diǎn)數(shù)據(jù)建網(wǎng)格索引，沒有數(shù)據(jù)冗余，有廣泛應(yīng)用

缺點(diǎn)：在線、面等空間數(shù)據(jù)有很大數(shù)據(jù)冗余，查詢效率也明顯下降。

2)四叉樹

Quadtree

將已知范圍的空間等分成四個相等的子空間，當(dāng)空間對象分布比較均勻時，具有較高的插入和查詢效率，但同樣存在一個空間元素被多個區(qū)域所索引，相應(yīng)存儲在多個葉子節(jié)點(diǎn)上，也存在索引的冗余。R樹是對四叉樹的優(yōu)化。

優(yōu)點(diǎn)：通過將數(shù)據(jù)空間逐層細(xì)分來組織數(shù)據(jù)，結(jié)構(gòu)和操作比較簡單，實現(xiàn)比較方便。

缺點(diǎn)：有索引冗余，一旦索引建立樹層次被固定，無法根據(jù)數(shù)據(jù)空間對象的變化調(diào)整樹高，可調(diào)節(jié)性差。

3)R樹

主要采用空間分割的理念，采用MBR最小邊界矩形的方法，從葉子節(jié)點(diǎn)開始用矩形將空間框起來，節(jié)點(diǎn)越往上，框住的空間就越大。

以此對空間進(jìn)行分割：所有原始空間元素都是葉子節(jié)點(diǎn)，這樣就不會出現(xiàn)網(wǎng)格索引和四叉樹空間要素被多個索引指引的情況，從而避免了大量索引冗余的問題。所有葉子節(jié)點(diǎn)都是空間對象。查找時候從根節(jié)點(diǎn)開始，找到哪些矩形區(qū)域與檢索矩形相交，一層一層查找到檢索矩形內(nèi)的空間對象。

優(yōu)點(diǎn)：有很強(qiáng)靈活性和可調(diào)節(jié)性，建樹無須預(yù)知整個空間對象所在空間范圍，也有較高的執(zhí)行效率。

缺點(diǎn)：索引空間經(jīng)常重疊，造成樹深度和存儲空間的增加，導(dǎo)致遍歷時間增加，查詢效率下降。

4)Kdtree

K-dimensional (k-維樹的簡稱)，是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要用于多維數(shù)據(jù)的搜索和數(shù)據(jù)挖掘中高維數(shù)據(jù)范圍查詢和k近鄰查詢。kd樹是個二叉樹，每個子節(jié)點(diǎn)是一個空間范圍，這種劃分空間沒有重疊。

kd樹中每個節(jié)點(diǎn)的數(shù)據(jù)類型如下：

根據(jù)方差確定split值，根據(jù)中值計算data-node值，左子空間和右子空間重復(fù)根節(jié)點(diǎn)過程，就可以得到下一級子節(jié)點(diǎn)。

假設(shè)有6個二維數(shù)據(jù)點(diǎn){（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，數(shù)據(jù)點(diǎn)位于二維空間內(nèi)。

由于此例簡單，數(shù)據(jù)維度只有2維，所以可以簡單地給x，y兩個方向軸編號為0,1，也即split={0,1}。

（1）確定split域的首先該取的值。分別計算x，y方向上數(shù)據(jù)的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向；

（2）確定Node-data的域值。根據(jù)x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data = （7,2）。這樣，該節(jié)點(diǎn)的分割超平面就是通過（7,2）并垂直于split = 0（x軸）的直線x = 7；

（3）確定左子空間和右子空間。分割超平面x = 7將整個空間分為兩部分，如圖2所示。x < = 7的部分為左子空間，包含3個節(jié)點(diǎn){（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節(jié)點(diǎn){（9,6），（8,1）}。

查找最近鄰：比如要搜索圖4中星號點(diǎn)(2.1,3.1)，從根節(jié)點(diǎn)開始，通過二叉搜索順著搜索路徑很快就能找到最近鄰的近似點(diǎn),也就是葉子節(jié)點(diǎn)(2,3)，該葉子節(jié)點(diǎn)不一定是最近鄰節(jié)點(diǎn)，需要沿搜索路徑再回溯計算最近鄰點(diǎn)，看其父節(jié)點(diǎn)的其他子節(jié)點(diǎn)是否是更近鄰節(jié)點(diǎn)。

優(yōu)點(diǎn)：空間二維或多維點(diǎn)數(shù)據(jù)構(gòu)建索引和查詢效率較高，在矩形范圍查詢場景也有較高效率（通過二叉樹節(jié)點(diǎn)數(shù)據(jù)的比較即可查到數(shù)據(jù)）。

缺點(diǎn)：線、面等復(fù)雜空間數(shù)據(jù)類型不太適用。

4.應(yīng)用場景

link按行駛方向的連接、

道路分層靜態(tài)數(shù)據(jù)處理、

線上實時矩形框內(nèi)poi查詢、

最近鄰poi點(diǎn)查找

5.JAVA第三方組件JTS中的空間索引類

上邊說到的空間索引算法自己編程實現(xiàn)有一定難度，JTS較好支持了這幾種空間索引算法，使用起來較為方便。

四叉樹Quadtree類:org.vividsolutions.jts.index.quadtree;

Kdtree類:com.vividsolutions.jts.index.kdtree.KdTree;

Rtree類:com.vividsolutions.jts.index.strtree.STRtree;