http://www.cnblogs.com/LBSer/p/3403933.html

深入淺出空間索引2

　　第一篇講到了傳統的索引如B樹不能很好的支援空間資料，比如點（POI等）、線（道路、河流等）、面（行政邊界、住宅區等）。本篇将對空間索引進行簡單分類，然後介紹網格索引。（深入淺出空間索引1：http://www.cnblogs.com/LBSer/p/3392491.html）

一、空間索引有哪幾種？

　　傳統索引使用哈希和樹這兩類最基本的資料結構。空間索引雖然更為複雜，但仍然發展于這兩種資料結構。是以可以将空間索引劃分為兩大類：1）基于哈希思想，如網格索引等；2）基于樹思想，有四叉樹、R樹等。

二、網格索引

　　哈希是通過一個哈希函數将關鍵字映射到記憶體或外存的資料結構，如何擴充到空間資料呢？

2.1. 網格索引原理

　　擴充方法：對地理空間進行網格劃分，劃分成大小相同的網格，每個網格對應着一塊存儲空間，索引項登記上落入該網格的空間對象。

　　舉個例子，我們将地理空間進行網格劃分，并進行編号。該空間範圍内有三個空間對象，分别是id=5的街道，23的河流和11的商圈。這時候我們可以按照哈希的資料結構存儲，每個網格對應着一個存儲桶，而桶裡放着空間對象，比如對2号網格，裡面存儲着id=5的空間對象，對35号網格，桶裡放着id=5和id=23的空間對象。

　　假如我們要查詢某一空間範圍内有哪些空間對象，比如下面的紅框就表示空間範圍，我們可以很快根據紅框的空間範圍算出它與35号和36号網格相交，然後分别到35号和36号網格中查找空間對象，最終找出id=5和id=23的空間對象。

2.2. 網格索引缺點

1）索引資料備援

　　網格與對象之間多對多關系在空間對象數量多、大小不均時造成索引資料備援。比如11号商圈這個空間對象在68，69，100，101這4個網格都有存儲，浪費了大量空間。

2）網格的大小難以确定

　　網格的劃分大小難以确定。網格劃分得越密，需要的存儲空間越多，網格劃分的越粗，查找效率可能會降低。對于圖a，這個查詢需要查詢4個網格，由于4個網格覆寫了整個空間，是以這個查找其實是将空間範圍内所有的點資料都周遊一遍，失去了索引的意義。

3）很多網格沒有資料

　　空間資料具有明顯的聚集性，比如POI隻在幾個熱點商貿區聚集，在郊區等地方很稀疏，這将導緻很多網格内沒有任何空間資料。

下一節将介紹四叉樹。

轉載請标明源位址：http://www.cnblogs.com/LBSer