基于地球空間網格的基礎地理信息數據庫空間索引方法

王乃生 吳 鑫 龐曉峰 勾會杰

(1.自然資源部陜西基礎地理信息中心 陜西西安 710054；2.西安市水利規劃勘測設計院 陜西西安 710054)

基礎地理信息是國家空間數據基礎設施的重要組成部分，是國家信息化的權威、統一的定位基準和空間載體，是國家經濟建設、社會發展和生態保護中不可或缺的基礎性和戰略性信息資源[1]，具有通用性強、共享需求大、行業應用廣泛等特點。隨著社會經濟的加速發展，一方面基礎地理信息數據的動態更新和全面更新已逐步覆蓋了各級比例尺，另一方面基礎地理信息數據的數據量呈爆發式增長。

傳統的基礎地理信息數據庫以關系型數據庫為主，數據的空間檢索主要借助空間關系運算和數據庫索引來實現，對海量異構數據的檢索效率低。如何科學、高效地管理基礎地理信息數據庫，提高海量異構數據的空間檢索效率，進而提升地理信息數據庫的管理能力，是業內學者一直關注的研究方向。

徐道柱等[2]提出了一種適應分布式環境下的分層+分塊的矢量數據存儲組織模型，實現了高并發條件下的數據高效訪問；于亮和宋明明等[3-4]對基于R-樹的空間索引技術進行了探討，提出了一種改進型的R-樹索引結構，在一定程度上提升了空間數據的檢索效率；余冬梅[5]對空間索引及其發展分類、空間數據查詢及其與傳統關系數據庫的區別進行了研究。這些研究從不同視角研究了空間數據索引，但并未提出針對基礎地理信息數據庫有效管理的完整解決方案。

地球空間網格[6]編碼規則的提出為基礎地理信息數據庫的空間索引提供了一種新的思路。本文在研究地球空間網格編碼規則等關鍵技術的基礎上，設計了基礎地理信息數據庫的空間索引算法及對應的數據空間檢索算法，以解決基礎地理信息數據庫的空間檢索問題。

1 數據空間索引關鍵技術

1.1 地球空間網格編碼規則

地球空間網格是為了滿足地球空間區域位置結構化表達和統一標識，將地球空間剖分成不同尺度單元的空間參考系統。地球空間網格按照四叉樹遞歸剖分方案，以地球參考橢球面、本初子午面與赤道面3個面的交點為起始位置，在經度(L)、緯度(B)和大地高(H)3個方向逐級遞歸二分，在地球參考橢球面形成地球表面剖分，加大地高方向形成立體剖分。

地球空間網格編碼是為地球空間上的任意網格賦予唯一可識別的編碼。地球空間網格編碼采用四進制1位變長編碼，編碼順序采用Z序進行，即每一級網格編碼在上一級網格編碼基礎上采用Z序繼續編碼，將地球表面空間區域劃分為32級的網格。

1.2 基礎地理數據存儲管理

基礎地理信息數據庫中的數據主要包括矢量數據、柵格數據、文檔數據及元數據。矢量數據以空間數據集進行存儲管理，地理要素都有相應的空間信息和屬性信息；柵格數據以鑲嵌數據集或文件形式進行存儲，空間信息和屬性信息管理主要通過對應的元數據來實現；文檔數據以文件形式進行存儲，空間信息和屬性信息管理也是通過對應的元數據來關聯實現。

1.3 空間關系

根據空間對象間的拓撲關系，多邊形與網格的空間關系可歸納為以下3種：

1)相離關系，網格完全不在多邊形內部；

2)相交關系，網格部分在多邊形內部或多邊形完全在網格內部；

3)包含關系，網格完全在多邊形內部。

1.4 完全容納數據的最小網格

空間索引是一種依據基礎地理信息數據的位置、形狀或空間實體之間的某種空間關系，按一定順序排列的數據結構?；诘厍蚩臻g網格實現基礎地理信息數據的空間索引，就是以地球空間網格的方式重新組織基礎地理信息數據的位置，建立數據和網格的關系，為數據庫的高效檢索提供支撐。

能夠完全容納數據的最小網格，是建立數據和網格關系的一種直觀有效的方式。對于矢量數據，其數據內容由一個個地理要素構成，當地理要素的最小外接矩形與第m級網格的相交個數為1、與第m+1級網格的相交個數大于1時，則認為第m級網格是能夠完全容納當前要素數據的最小網格。對于通過元數據進行管理的柵格數據和文檔數據，可將元數據的范圍看作是一個面要素，按矢量數據中的面要素計算最小網格。

2 數據空間索引算法

基于地球空間網格實現基礎地理信息數據的空間索引，實際上就是計算數據對應的最小網格并進行編碼的過程。計算完全容納數據的最小網格算法流程為：

第1步：根據要素實體的左、右、上、下經緯度坐標和所在空間區域，計算上下緯度和左右經度坐標差dL、dW，若dL大于dW，則將dL作為長邊、dW作為短邊，得到要素實體的最小外接矩形。

第2步：若dL的邊長小于某一級網格邊長Dm且大于下一級網格邊長Dm+1，則可確定描述該要素實體對應的網格層級為m。

第3步：若數據所在空間范圍的最小外接矩形與第m級網格的相交個數為1，與第m+1級網格的相交個數大于1時，則認為第m級網格是能夠完全容納當前數據的最小網格。

第4步：若最小外接矩形與第m級網格的相交個數大于1，則m=m- 1，繼續第3步。

第5步：若最小外接矩形與第m級網格的相交個數等于1，則m=m+ 1，繼續第3步。

在計算最小網格時會存在一些同時跨越多個網格的數據，如果跨網格數據采用最小網格作為其所在的空間網格，則這些數據最小網格的層級過高，不利于后續數據檢索。因此，需要對這些跨網格數據進行特殊處理，選擇與跨網格數據相交的指定層級的網格作為這些數據所在的空間網格。為了判斷數據是否為跨網格數據并確定其所在空間網格的層級，設計算法流程為：

1)獲取數據外接矩形的左下角點PLB和右上角點PRT。

2)獲取PLB和PRT坐標(X，Y)的整數值(XLB，YLB)和(XRT，YRT)。

3)若XRT-XLB>0或者YRT-YLB>0，則認定該數據是跨網格數據；反之，則進行下一步判斷。

4)根據外接矩形的長邊計算跨網格數據所在的層級m。

5)根據最小網格算法計算跨網格數據最小網格所在的層級n。

6)若m-n≥4，則認定該數據是跨網格數據；反之，則不是跨網格數據。

7)m為該數據所在空間網格的指定層級。

計算數據所在地球空間網格后，按照地球空間網格編碼規則計算空間網格的編碼，如果數據所在的空間網格有多個，則以“，”作為分隔符，以“編碼1，編碼2，…，編碼n”的格式進行編碼。

3 數據空間檢索算法實現

基于地球空間網格建立的空間索引進行數據空間檢索時，需要自頂向下逐級判斷多邊形檢索范圍以及與不同級別網格的空間關系，最后計算多邊形范圍內相應的地球空間網格，算法實現如圖1所示。

圖1 空間檢索流程

由圖1可知，當多邊形與網格為相離關系時，該網格及其子網格均被過濾掉。當多邊形與網格為相交關系時，該網格則需要遞歸判斷其子級網格與多邊形的關系，直至其子級網格被多邊形包含或網格級別達到空間索引時計算的網格最深層級。當多邊形與網格為包含關系時，多邊形與該網格及其下級網格中的數據均為包含關系。

計算多邊形檢索范圍對應的地球空間網格后，需要根據不同的空間關系進行相應的屬性查詢。

首先，當多邊形與網格為包含關系時，由于網格編碼之間存在上下級關系，即網格第n+1級網格編碼的前n位是上一級網格的編碼，因此在定位具體數據時，通過屬性查詢只需查找到前n位編碼相同，即可查找到該網格及其所有下級網格中的數據。

其次，當多邊形與網格為相交關系時，只需要定位網格對應的每個數據。如查找交疊的m級，其網格編碼為s的網格a中的數據，將查詢條件設為“位置編碼=s”，通過屬性查詢查出的數據即為m級網格a中的數據。為驗證上述算法，選取陜西省某區域的1∶10 000 基礎地理信息要素和地理國情要素數據進行了數據試驗，同時，基于地球空間網格的空間索引編碼，對比測試了基于地球空間網格空間索引后的空間檢索與傳統空間檢索的效率，試驗數據統計信息見表1。

表1 空間檢索統計信息Tab.1 Statistics Data in Spatial Retrieval圖層名稱要素/個檢索結果/個傳統空間檢索時間/s基于網格的檢索時間/s 效率比/%CPTP2 2659700.130.121.04HFCL35 34812 6460.490.421.17LFCL385 945124 4984.972.641.88RESP397 22876 2103.142.051.53LRDL705 18514 5400.780.810.96VEGA831 041358 23637.148.644.30LRDA7 5872 2210.340.331.04UV_SFCP22 7422 4810.260.261.00UV_HYDL122 4415 2950.690.421.64UV_HYDA32 8183 5250.640.401.61UV_LCRA7 190 715387 57340.6314.922.72

從表 1可知，基于地球空間網格空間索引的空間檢索時間與傳統空間檢索時間相比，在所有圖層其效率均高于傳統空間檢索，檢索效率平均提升1.5倍，部分圖層可提升4倍以上。

4 結 語

本文提出的基于地球空間網格的基礎地理信息數據庫空間索引方法，可以在不改變已有數據模型和存儲模式的基礎上，快速為已有的基礎地理信息數據庫構建擴展索引，大幅提升了空間數據的檢索效率。

本文的研究成果已在陜西省基礎地理信息數據庫中得到應用，與傳統的空間檢索方法相比，檢索效率平均提升1.5倍，部分圖層可提升4倍以上。