王彥佐， 周 偉， 馮 磊

(中國(guó)國(guó)土資源航空物探遙感中心，北京 100083)

0 引言

資源一號(hào)02C(ZY1-02C)衛(wèi)星數(shù)據(jù)應(yīng)用過(guò)程中，為了保障礦產(chǎn)資源調(diào)查評(píng)價(jià)、地質(zhì)災(zāi)害環(huán)境調(diào)查與監(jiān)測(cè)等業(yè)務(wù)對(duì)數(shù)據(jù)時(shí)效性和準(zhǔn)確性的要求，需要針對(duì)所產(chǎn)生的數(shù)百萬(wàn)景原始影像及數(shù)據(jù)產(chǎn)品實(shí)現(xiàn)快速檢索?？臻g數(shù)據(jù)檢索操作的對(duì)象為矢量格式的空間分布圖層。傳統(tǒng)的空間數(shù)據(jù)檢索架構(gòu)大多基于關(guān)系型數(shù)據(jù)庫(kù)(如Oracle)及空間數(shù)據(jù)引擎(如ArcSDE)[1]。該架構(gòu)在I/O速率和存儲(chǔ)結(jié)構(gòu)等方面的限制對(duì)空間檢索的效率有一定影響，并且會(huì)隨數(shù)據(jù)量增大而變得更顯著。針對(duì)ZY1-02C海量空間數(shù)據(jù)檢索的應(yīng)用特點(diǎn)，以及傳統(tǒng)空間數(shù)據(jù)檢索架構(gòu)的限制，采用了基于Key-Value型內(nèi)存數(shù)據(jù)庫(kù)的新型空間檢索架構(gòu)，該架構(gòu)的主要優(yōu)勢(shì)[2-3]有： ①讀寫(xiě)速度快，內(nèi)存數(shù)據(jù)庫(kù)中所有數(shù)據(jù)均存儲(chǔ)于內(nèi)存中，其讀寫(xiě)速度比存儲(chǔ)于磁盤(pán)中的數(shù)據(jù)高出幾個(gè)數(shù)量級(jí)，可大大減少I(mǎi)/O操作的時(shí)間，從而顯著提升檢索速度； ②復(fù)雜數(shù)據(jù)結(jié)構(gòu)適應(yīng)性強(qiáng)，由于空間分布圖層為矢量格式，其數(shù)據(jù)結(jié)構(gòu)比二維數(shù)據(jù)表復(fù)雜，因此使用關(guān)系型數(shù)據(jù)庫(kù)存儲(chǔ)需要經(jīng)過(guò)較復(fù)雜的數(shù)據(jù)類型轉(zhuǎn)換，而Key-Value型數(shù)據(jù)庫(kù)架構(gòu)靈活，可以很好地適應(yīng)復(fù)雜數(shù)據(jù)結(jié)構(gòu)； ③受內(nèi)存容量限制小，內(nèi)存數(shù)據(jù)庫(kù)可存儲(chǔ)管理的數(shù)據(jù)量受內(nèi)存容量限制，遠(yuǎn)遠(yuǎn)小于關(guān)系型數(shù)據(jù)庫(kù)的可用容量，但由于ZY1-02C數(shù)據(jù)空間分布圖層為矢量格式，記錄數(shù)多而單條記錄占用量小，總數(shù)據(jù)量有限(GB級(jí))，不受該限制因素影響； ④性能的影響因素少，關(guān)系型數(shù)據(jù)庫(kù)對(duì)事務(wù)的要求非常嚴(yán)格，在保證數(shù)據(jù)一致性的同時(shí)，對(duì)數(shù)據(jù)讀寫(xiě)效率也有一定影響； 在ZY1-02C數(shù)據(jù)空間檢索中，不存在復(fù)雜的多表間數(shù)據(jù)關(guān)系，對(duì)數(shù)據(jù)原子性及一致性等要求也不高，因此選用靈活性較強(qiáng)的內(nèi)存數(shù)據(jù)庫(kù)可以在一定程度上提高性能。依據(jù)該架構(gòu)，本文選用了互聯(lián)網(wǎng)行業(yè)廣泛使用的Redis數(shù)據(jù)庫(kù)為基礎(chǔ)平臺(tái)，研究并設(shè)計(jì)了矢量數(shù)據(jù)在Redis中的存儲(chǔ)結(jié)構(gòu)，從而實(shí)現(xiàn)了基于Key-Value型存儲(chǔ)結(jié)構(gòu)的空間R樹(shù)索引，有效提升了ZY1-02C海量空間數(shù)據(jù)檢索的性能。

1 Key-Value型內(nèi)存數(shù)據(jù)庫(kù)Redis

1.1 Key-Value型存儲(chǔ)結(jié)構(gòu)

Key-Value型存儲(chǔ)結(jié)構(gòu)[4]是一種存儲(chǔ)管理數(shù)據(jù)的范式，與之相對(duì)的是關(guān)系型存儲(chǔ)結(jié)構(gòu)，它們之間有非常大的區(qū)別。

關(guān)系型存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)以“記錄-字段”的形式存儲(chǔ)于預(yù)定義好的二維數(shù)據(jù)結(jié)構(gòu)中，記錄中每個(gè)字段的類型都必須符合預(yù)定義的要求，且無(wú)法更改。

Key-Value型存儲(chǔ)結(jié)構(gòu)則通過(guò)鍵-值對(duì)的形式存儲(chǔ)數(shù)據(jù)，每一個(gè)唯一的鍵名(Key)對(duì)應(yīng)一個(gè)唯一的值(Value)，存取時(shí)通過(guò)鍵名來(lái)查找對(duì)應(yīng)的值，值的類型和格式可任意定義，擁有較大的靈活性。同時(shí)，由于其靈活性較強(qiáng)，該結(jié)構(gòu)占用的內(nèi)存遠(yuǎn)小于關(guān)系型數(shù)據(jù)結(jié)構(gòu)，因此內(nèi)存數(shù)據(jù)庫(kù)大多采用Key-Value型存儲(chǔ)結(jié)構(gòu)。

1.2 Redis內(nèi)存數(shù)據(jù)庫(kù)

Redis[5]是一款開(kāi)源的Key-Value型內(nèi)存數(shù)據(jù)庫(kù)，自發(fā)布以來(lái)已被Twitter及新浪微博等多家知名互聯(lián)網(wǎng)公司使用，功能強(qiáng)大，運(yùn)行穩(wěn)定，本研究采用該數(shù)據(jù)庫(kù)作為海量數(shù)據(jù)檢索的基礎(chǔ)平臺(tái)。由于存儲(chǔ)方式的巨大差異，傳統(tǒng)關(guān)系型存儲(chǔ)結(jié)構(gòu)中的矢量數(shù)據(jù)存儲(chǔ)方法及索引算法均無(wú)法應(yīng)用于Key-Value型存儲(chǔ)結(jié)構(gòu)中，需要根據(jù)Key-Value型存儲(chǔ)結(jié)構(gòu)的組織形式進(jìn)行重新設(shè)計(jì)及實(shí)現(xiàn)。

2 矢量數(shù)據(jù)在Redis中的存儲(chǔ)結(jié)構(gòu)

2.1 基于Key-Value型存儲(chǔ)結(jié)構(gòu)的矢量數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)

對(duì)海量數(shù)據(jù)進(jìn)行空間檢索的前提是實(shí)現(xiàn)數(shù)據(jù)在Redis數(shù)據(jù)庫(kù)中的存儲(chǔ)，并能夠?qū)ζ溥M(jìn)行高效地讀寫(xiě)，結(jié)合Key-Value型存儲(chǔ)結(jié)構(gòu)以及ZY1-02C空間分布矢量數(shù)據(jù)特點(diǎn)，設(shè)計(jì)了用于存儲(chǔ)矢量數(shù)據(jù)的3級(jí)結(jié)構(gòu)[6]，分別為圖層集(LayerSet)、圖層(Layer)及要素(Feature)。

1)圖層集(LayerSet)。一個(gè)數(shù)據(jù)庫(kù)中只有一個(gè)圖層集對(duì)應(yīng)的鍵-值對(duì)，鍵名即為“LayerSet”； 鍵值使用集合形式，存儲(chǔ)數(shù)據(jù)庫(kù)中所有圖層的圖層名。

2)圖層(Layer)。一個(gè)數(shù)據(jù)庫(kù)中可以有多個(gè)圖層，每個(gè)圖層的名稱不可重復(fù)，并在圖層集中登記； 每個(gè)圖層使用一個(gè)鍵-值對(duì)存儲(chǔ)其元數(shù)據(jù)信息，鍵名即為圖層名稱，其格式為“Layer: [Name]”，其中[Name]可使用字符或數(shù)字的組合來(lái)區(qū)別不同的圖層； 鍵值使用Hash格式，存儲(chǔ)圖層的圖層類型、圖層范圍、空間參考和空間索引名稱等信息； 圖層及其包含的要素通過(guò)鍵名進(jìn)行對(duì)應(yīng)。

3)要素(Feature)。一個(gè)圖層可包含多個(gè)要素，每個(gè)要素使用一個(gè)鍵-值對(duì)存儲(chǔ)其屬性及空間信息； 要素與其所在圖層之間通過(guò)鍵名進(jìn)行對(duì)應(yīng)，要素的鍵名格式為“Layer: [Name]: Fea: [Index] ”，其中前半部分即為所在圖層的鍵名，后半部分為要素編號(hào)，其中[Index]以數(shù)字區(qū)分不同要素，不可重復(fù)； 鍵值使用Hash格式，存儲(chǔ)要素的屬性及空間信息； 對(duì)于其中要素的屬性信息，在Hash值中，子鍵名(SubKey)為字段名，子鍵值(SubValue)為字段值； 對(duì)于其中要素的空間信息，在Hash值中，使用預(yù)定義的“Shape”作為子鍵名，將空間對(duì)象轉(zhuǎn)換為符合OGC標(biāo)準(zhǔn)的wkb格式，以二進(jìn)制的形式存儲(chǔ)于子鍵值中。

2.2 存儲(chǔ)結(jié)構(gòu)示例

2.1節(jié)中存儲(chǔ)結(jié)構(gòu)的示例如圖1所示。

圖1 存儲(chǔ)結(jié)構(gòu)示例Fig.1 Storage structure example

3 基于Key-Value型存儲(chǔ)結(jié)構(gòu)的空間索引

3.1 空間索引基本概念

實(shí)現(xiàn)矢量數(shù)據(jù)在Redis數(shù)據(jù)庫(kù)中的存儲(chǔ)管理是進(jìn)行空間檢索操作的基礎(chǔ)，為提高空間檢索的效率，還需要為數(shù)據(jù)庫(kù)中的矢量數(shù)據(jù)建立空間索引。

空間索引[7-8]是一種數(shù)據(jù)結(jié)構(gòu)，使用預(yù)定義的算法將數(shù)據(jù)庫(kù)中各要素的空間特征(外接矩形和中心點(diǎn)坐標(biāo)等)與其存儲(chǔ)地址之間的對(duì)應(yīng)關(guān)系組織并保存起來(lái)。通過(guò)空間索引，用戶在空間檢索時(shí)不需要對(duì)全庫(kù)進(jìn)行遍歷，即可快速定位到所需的要素，從而大大提高檢索效率。

傳統(tǒng)的空間索引大多基于文件或關(guān)系型數(shù)據(jù)庫(kù)，Key-Value型內(nèi)存數(shù)據(jù)庫(kù)由于其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的差異，無(wú)法直接使用傳統(tǒng)的空間索引存儲(chǔ)結(jié)構(gòu)，需要依據(jù)基礎(chǔ)索引算法，設(shè)計(jì)并實(shí)現(xiàn)有針對(duì)性的空間索引。

3.2 R樹(shù)空間索引基礎(chǔ)算法

常見(jiàn)的空間索引算法包括格網(wǎng)索引、空間哈希索引和R樹(shù)索引等，其中R樹(shù)索引[9-10]是目前空間索引領(lǐng)域應(yīng)用最廣泛的索引算法，其特點(diǎn)為查詢維護(hù)便捷，效率高。本研究選用R樹(shù)索引作為生成空間索引的基礎(chǔ)算法。

R樹(shù)索引是B樹(shù)索引向二維空間的擴(kuò)展，其基礎(chǔ)算法為： ①R樹(shù)中的所有數(shù)據(jù)都存儲(chǔ)于葉節(jié)點(diǎn)中，其他非葉節(jié)點(diǎn)以最小外包矩形(minimum bounding rectangle，MBR)的格式存儲(chǔ)輔助數(shù)據(jù)； ②每個(gè)非葉節(jié)點(diǎn)的MBR范圍為其所有子節(jié)點(diǎn)MBR范圍的MBR； ③R樹(shù)生成過(guò)程中，同一層的各節(jié)點(diǎn)之間，矩形相交部分應(yīng)盡量?。?位置上相近的結(jié)點(diǎn)盡量在樹(shù)中聚集為一個(gè)父節(jié)點(diǎn)。

3.3 R樹(shù)索引在Redis數(shù)據(jù)庫(kù)下的存儲(chǔ)結(jié)構(gòu)

基于R樹(shù)索引基礎(chǔ)算法，設(shè)計(jì)并實(shí)現(xiàn)了基于Key-Value型存儲(chǔ)結(jié)構(gòu)的R樹(shù)索引存儲(chǔ)結(jié)構(gòu)及檢索方案，其中存儲(chǔ)結(jié)構(gòu)詳情如下：

1)R樹(shù)索引在Redis數(shù)據(jù)庫(kù)中均采用集合格式存儲(chǔ)。

2)每個(gè)圖層對(duì)應(yīng)一組索引，該組索引由一個(gè)根節(jié)點(diǎn)、多個(gè)中間節(jié)點(diǎn)及葉節(jié)點(diǎn)構(gòu)成，圖層的元數(shù)據(jù)信息中記錄根節(jié)點(diǎn)的鍵名，以標(biāo)識(shí)圖層與索引之間的對(duì)應(yīng)關(guān)系。

3)一組索引由數(shù)據(jù)庫(kù)中的多個(gè)鍵-值對(duì)描述，每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)鍵-值對(duì)，其鍵名為當(dāng)前節(jié)點(diǎn)的信息，鍵值為集合格式，記錄其包含的所有下一級(jí)子節(jié)點(diǎn)或要素的鍵名。

4)各個(gè)節(jié)點(diǎn)主要信息均記錄在鍵名中，即

RTI: #: *: [WestBound]|[EastBound]|

[SouthBound]|[NorthBound] ，

(1)

其中： #為索引序列號(hào)，按索引編制順序順次編碼，對(duì)應(yīng)某一圖層的一組索引序列號(hào)相同； *為索引層號(hào)，根節(jié)點(diǎn)層號(hào)為1，其子節(jié)點(diǎn)層號(hào)為2，依此類推； [WestBound]，[EastBound]，[SouthBound]和[NorthBound]分別為該節(jié)點(diǎn)對(duì)應(yīng)MBR的西、東、南和北邊界。

該索引存儲(chǔ)結(jié)構(gòu)示例如圖2所示。

圖2 R樹(shù)存儲(chǔ)結(jié)構(gòu)示例Fig.2 Storage structure example of R-tree index in Redis

4 系統(tǒng)實(shí)現(xiàn)

4.1 系統(tǒng)基礎(chǔ)環(huán)境

系統(tǒng)實(shí)現(xiàn)過(guò)程中，選取的計(jì)算機(jī)軟硬件基礎(chǔ)環(huán)境如下： ①操作系統(tǒng)選用Windows Server 2008R2； ②內(nèi)存數(shù)據(jù)庫(kù)軟件選用Redis 2.8 On Windows； ③集成開(kāi)發(fā)環(huán)境選用Microsoft Visual Studio.net 2010； ④開(kāi)發(fā)語(yǔ)言選用C#； ⑤GIS組件選用開(kāi)源柵格空間數(shù)據(jù)轉(zhuǎn)換庫(kù)(geospatial data abstraction library,GDAL)/OGR庫(kù)。

4.2 矢量數(shù)據(jù)轉(zhuǎn)換入庫(kù)

該功能將Shapefile格式的矢量數(shù)據(jù)轉(zhuǎn)換為2.1節(jié)中的存儲(chǔ)結(jié)構(gòu)，并存入Redis數(shù)據(jù)庫(kù)，其實(shí)現(xiàn)流程如圖3所示。

圖3 矢量數(shù)據(jù)轉(zhuǎn)換入庫(kù)流程Fig.3 Data conversion flowchart of shapefile

圖3流程中，首先使用GDAL組件對(duì)圖層文件進(jìn)行解析，獲取圖層名及元數(shù)據(jù)信息，并將上述信息存入Redis數(shù)據(jù)庫(kù)中的“圖層集”以及“圖層”鍵-值對(duì)； 同時(shí)逐個(gè)讀取矢量要素，并使用GDAL組件將空間信息轉(zhuǎn)為wkb格式，與屬性信息一同存入Redis中的“要素”鍵-值對(duì)。

4.3 Key-Value型結(jié)構(gòu)下R樹(shù)索引空間檢索

該功能根據(jù)輸入的空間查詢條件(包含目標(biāo)圖層及查詢空間對(duì)象)，依據(jù)所構(gòu)建的R樹(shù)索引，查找并返回?cái)?shù)據(jù)庫(kù)中符合空間條件的矢量要素，其流程如圖4所示。

圖4 空間數(shù)據(jù)檢索流程Fig.4 Flowchart of spatial data query

4.4 空間檢索效率測(cè)試與對(duì)比

系統(tǒng)功能實(shí)現(xiàn)后，在相同軟硬件環(huán)境下，對(duì)比了基于Redis內(nèi)存數(shù)據(jù)庫(kù)的R樹(shù)索引以及傳統(tǒng)基于Oracle數(shù)據(jù)庫(kù)的格網(wǎng)索引2種空間檢索架構(gòu)的檢索效率。

測(cè)試軟硬件環(huán)境為： VMWare虛擬機(jī)，二路二核CPU，8 GB內(nèi)存，Redis2.8.19和Oracle11.1.0.6軟件。測(cè)試數(shù)據(jù)為： ZY1-02C原始影像空間分布圖層，共包含411 523個(gè)要素。矩形空間范圍要素檢索測(cè)試結(jié)果如圖5所示。

圖5 空間數(shù)據(jù)檢索效率測(cè)試Fig.5 Efficiency test of spatial query

從對(duì)比測(cè)試結(jié)果中可以看到，基于Key-Value型內(nèi)存數(shù)據(jù)庫(kù)Redis進(jìn)行空間檢索操作，能夠在海量數(shù)據(jù)條件下，有效提高空間檢索的效率。

5 結(jié)論

本文針對(duì)ZY1-02C海量空間數(shù)據(jù)檢索的應(yīng)用需求，以及傳統(tǒng)空間檢索架構(gòu)的限制，基于Key-Value型內(nèi)存數(shù)據(jù)庫(kù)技術(shù)，設(shè)計(jì)并實(shí)現(xiàn)了一種矢量空間數(shù)據(jù)的存儲(chǔ)架構(gòu)以及空間索引架構(gòu)，完成了相應(yīng)功能開(kāi)發(fā)，現(xiàn)已部署于ZY1-02C相關(guān)應(yīng)用系統(tǒng)中。經(jīng)對(duì)比測(cè)試及實(shí)際運(yùn)行檢驗(yàn)，該架構(gòu)與傳統(tǒng)基于磁盤(pán)的關(guān)系型數(shù)據(jù)庫(kù)架構(gòu)相比，能夠更好地適用于ZY1-02C海量空間數(shù)據(jù)檢索的應(yīng)用場(chǎng)景，并有效提升空間檢索操作的效率，取得了良好的應(yīng)用效果。

[1] 薛 濤,刁明光,李建存,等.資源環(huán)境遙感海量空間數(shù)據(jù)存儲(chǔ)、檢索和訪問(wèn)方法[J].國(guó)土資源遙感,2013,25(2):168-173.doi:10.6046/gtzyyg.2013.02.28.

Xue T,Diao M G,Li J C,et al.Approach to storing, retrieving and accessing mass spatial data in resources and environments remote sensing[J].Remote Sensing for Land and Resources,2013,25(2):168-173.doi:10.6046/gtzyyg.2013.02.28.

[2] 楊武軍,張繼榮,屈軍鎖.內(nèi)存數(shù)據(jù)庫(kù)技術(shù)綜述[J].西安郵電學(xué)院學(xué)報(bào),2005,10(3):95-99.

Yang W J,Zhang J R,Qu J S.An overview of main-memory database technologies[J].Journal of Xi’an University of Post and Telecommunications,2005,10(3):95-99.

[3] 王 珊,肖艷芹,劉大為,等.內(nèi)存數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)應(yīng)用,2007,27(10):2353-2357.

Wang S,Xiao Y Q,Liu D W,et al.Research of main memory database[J].Computer Applications,2007,27(10):2353-2357.

[4] Wikipedia.Key-value database[EB/OL].(2016-05-16)[2016-06-27].https://en.wikipedia.org/wiki/Key-value_database.

[5] Redislabs.Redis[EB/OL].(2016-06-17)[2016-06-27].http://redis.io.

[6] 朱 進(jìn),胡 斌,邵 華,等.基于內(nèi)存數(shù)據(jù)庫(kù)Redis的輕量級(jí)矢量地理數(shù)據(jù)組織[J].地理信息科學(xué),2014,16(2):165-172.

Zhu J,Hu B,Shao H,et al.Research of lightweight vector geographic data management based on main memory database Redis[J].Journal of Geo-information Science,2014,16(2):165-172.

[7] 閻超德,趙學(xué)勝.GIS空間索引方法述評(píng)[J].地理與地理信息科學(xué),2004,20(4):23-26,39.

Yan C D,Zhao X S.The review of spatial indexes in GIS[J].Geography and Geo-Information Science,2004,20(4):23-26,39.

[8] 史文中,郭 薇,彭奕彰.一種面向地理信息系統(tǒng)的空間索引方法[J].測(cè)繪學(xué)報(bào),2001,30(2):156-161.

Shi W Z,Guo W,Peng Y Z.A spatial indexing method for GIS[J].Acta Geodaetica et Cartographica Sinica,2001,30(2):156-161.

[9] 黃曉明,楊紅雨,閆 覓.基于R樹(shù)的空管GIS數(shù)據(jù)模型索引的設(shè)計(jì)[J].微計(jì)算機(jī)信息,2008,24(8-3):144-146.

Huang X M,Yang H Y,Yan M.The index design for ATC GIS data model based on R tree[J].Microcomputer Information,2008,24(8-3):144-146.

[10] 羅 琪,李 軍,陳 犖.基于GIS平臺(tái)的R樹(shù)索引模型研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué),2003,25(6):93-96.

Luo Q,Li J,Chen L.Research and implementation of a R-tree index model based on the GIS platform[J].Computer Engineering and Science,2003,25(6):93-96.