深入淺出空間索引2

　　第一篇講到了傳統(tǒng)的索引如B樹不能很好的支持空間數(shù)據(jù)，比如點（POI等）、線（道路、河流等）、面（行政邊界、住宅區(qū)等）。本篇將對空間索引進行簡單分類，然后介紹網(wǎng)格索引。（深入淺出空間索引1：http://www.cnblogs.com/LBSer/p/3392491.html）

一、空間索引有哪幾種？

　　傳統(tǒng)索引使用哈希和樹這兩類最基本的數(shù)據(jù)結(jié)構(gòu)。空間索引雖然更為復(fù)雜，但仍然發(fā)展于這兩種數(shù)據(jù)結(jié)構(gòu)。因此可以將空間索引劃分為兩大類：1）基于哈希思想，如網(wǎng)格索引等；2）基于樹思想，有四叉樹、R樹等。

?

二、網(wǎng)格索引

　　哈希是通過一個哈希函數(shù)將關(guān)鍵字映射到內(nèi)存或外存的數(shù)據(jù)結(jié)構(gòu)，如何擴展到空間數(shù)據(jù)呢？

2.1. 網(wǎng)格索引原理

　　擴展方法：對地理空間進行網(wǎng)格劃分，劃分成大小相同的網(wǎng)格，每個網(wǎng)格對應(yīng)著一塊存儲空間，索引項登記上落入該網(wǎng)格的空間對象。

　　舉個例子，我們將地理空間進行網(wǎng)格劃分，并進行編號。該空間范圍內(nèi)有三個空間對象，分別是id=5的街道，23的河流和11的商圈。這時候我們可以按照哈希的數(shù)據(jù)結(jié)構(gòu)存儲，每個網(wǎng)格對應(yīng)著一個存儲桶，而桶里放著空間對象，比如對2號網(wǎng)格，里面存儲著id=5的空間對象，對35號網(wǎng)格，桶里放著id=5和id=23的空間對象。

?

　　假如我們要查詢某一空間范圍內(nèi)有哪些空間對象，比如下面的紅框就表示空間范圍，我們可以很快根據(jù)紅框的空間范圍算出它與35號和36號網(wǎng)格相交，然后分別到35號和36號網(wǎng)格中查找空間對象，最終找出id=5和id=23的空間對象。

?

2.2. 網(wǎng)格索引缺點

1）索引數(shù)據(jù)冗余

　　網(wǎng)格與對象之間多對多關(guān)系在空間對象數(shù)量多、大小不均時造成索引數(shù)據(jù)冗余。比如11號商圈這個空間對象在68，69，100，101這4個網(wǎng)格都有存儲，浪費了大量空間。

2）網(wǎng)格的大小難以確定

　　網(wǎng)格的劃分大小難以確定。網(wǎng)格劃分得越密，需要的存儲空間越多，網(wǎng)格劃分的越粗，查找效率可能會降低。對于圖a，這個查詢需要查詢4個網(wǎng)格，由于4個網(wǎng)格覆蓋了整個空間，因此這個查找其實是將空間范圍內(nèi)所有的點數(shù)據(jù)都遍歷一遍，失去了索引的意義。

?

3）很多網(wǎng)格沒有數(shù)據(jù)

　　空間數(shù)據(jù)具有明顯的聚集性，比如POI只在幾個熱點商貿(mào)區(qū)聚集，在郊區(qū)等地方很稀疏，這將導(dǎo)致很多網(wǎng)格內(nèi)沒有任何空間數(shù)據(jù)。

?

?

?

下一節(jié)將介紹四叉樹。

總結(jié)

以上是生活随笔為你收集整理的深入浅出空间索引：2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。