內存數據庫在ZY1-02C海量數據空間檢索中的應用

王彥佐， 周 偉， 馮 磊

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

0 引言

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

1 Key-Value型內存數據庫Redis

1.1 Key-Value型存儲結構

Key-Value型存儲結構[4]是一種存儲管理數據的范式，與之相對的是關系型存儲結構，它們之間有非常大的區別。

關系型存儲結構中，數據以“記錄-字段”的形式存儲于預定義好的二維數據結構中，記錄中每個字段的類型都必須符合預定義的要求，且無法更改。

Key-Value型存儲結構則通過鍵-值對的形式存儲數據，每一個唯一的鍵名(Key)對應一個唯一的值(Value)，存取時通過鍵名來查找對應的值，值的類型和格式可任意定義，擁有較大的靈活性。同時，由于其靈活性較強，該結構占用的內存遠小于關系型數據結構，因此內存數據庫大多采用Key-Value型存儲結構。

1.2 Redis內存數據庫

Redis[5]是一款開源的Key-Value型內存數據庫，自發布以來已被Twitter及新浪微博等多家知名互聯網公司使用，功能強大，運行穩定，本研究采用該數據庫作為海量數據檢索的基礎平臺。由于存儲方式的巨大差異，傳統關系型存儲結構中的矢量數據存儲方法及索引算法均無法應用于Key-Value型存儲結構中，需要根據Key-Value型存儲結構的組織形式進行重新設計及實現。

2 矢量數據在Redis中的存儲結構

2.1 基于Key-Value型存儲結構的矢量數據存儲結構設計

對海量數據進行空間檢索的前提是實現數據在Redis數據庫中的存儲，并能夠對其進行高效地讀寫，結合Key-Value型存儲結構以及ZY1-02C空間分布矢量數據特點，設計了用于存儲矢量數據的3級結構[6]，分別為圖層集(LayerSet)、圖層(Layer)及要素(Feature)。

1)圖層集(LayerSet)。一個數據庫中只有一個圖層集對應的鍵-值對，鍵名即為“LayerSet”； 鍵值使用集合形式，存儲數據庫中所有圖層的圖層名。

2)圖層(Layer)。一個數據庫中可以有多個圖層，每個圖層的名稱不可重復，并在圖層集中登記； 每個圖層使用一個鍵-值對存儲其元數據信息，鍵名即為圖層名稱，其格式為“Layer: [Name]”，其中[Name]可使用字符或數字的組合來區別不同的圖層； 鍵值使用Hash格式，存儲圖層的圖層類型、圖層范圍、空間參考和空間索引名稱等信息； 圖層及其包含的要素通過鍵名進行對應。

3)要素(Feature)。一個圖層可包含多個要素，每個要素使用一個鍵-值對存儲其屬性及空間信息； 要素與其所在圖層之間通過鍵名進行對應，要素的鍵名格式為“Layer: [Name]: Fea: [Index] ”，其中前半部分即為所在圖層的鍵名，后半部分為要素編號，其中[Index]以數字區分不同要素，不可重復； 鍵值使用Hash格式，存儲要素的屬性及空間信息； 對于其中要素的屬性信息，在Hash值中，子鍵名(SubKey)為字段名，子鍵值(SubValue)為字段值； 對于其中要素的空間信息，在Hash值中，使用預定義的“Shape”作為子鍵名，將空間對象轉換為符合OGC標準的wkb格式，以二進制的形式存儲于子鍵值中。

2.2 存儲結構示例

2.1節中存儲結構的示例如圖1所示。

圖1 存儲結構示例Fig.1 Storage structure example

3 基于Key-Value型存儲結構的空間索引

3.1 空間索引基本概念

實現矢量數據在Redis數據庫中的存儲管理是進行空間檢索操作的基礎，為提高空間檢索的效率，還需要為數據庫中的矢量數據建立空間索引。

空間索引[7-8]是一種數據結構，使用預定義的算法將數據庫中各要素的空間特征(外接矩形和中心點坐標等)與其存儲地址之間的對應關系組織并保存起來。通過空間索引，用戶在空間檢索時不需要對全庫進行遍歷，即可快速定位到所需的要素，從而大大提高檢索效率。

傳統的空間索引大多基于文件或關系型數據庫，Key-Value型內存數據庫由于其數據存儲結構的差異，無法直接使用傳統的空間索引存儲結構，需要依據基礎索引算法，設計并實現有針對性的空間索引。

3.2 R樹空間索引基礎算法

常見的空間索引算法包括格網索引、空間哈希索引和R樹索引等，其中R樹索引[9-10]是目前空間索引領域應用最廣泛的索引算法，其特點為查詢維護便捷，效率高。本研究選用R樹索引作為生成空間索引的基礎算法。

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

3.3 R樹索引在Redis數據庫下的存儲結構

基于R樹索引基礎算法，設計并實現了基于Key-Value型存儲結構的R樹索引存儲結構及檢索方案，其中存儲結構詳情如下：

1)R樹索引在Redis數據庫中均采用集合格式存儲。

2)每個圖層對應一組索引，該組索引由一個根節點、多個中間節點及葉節點構成，圖層的元數據信息中記錄根節點的鍵名，以標識圖層與索引之間的對應關系。

3)一組索引由數據庫中的多個鍵-值對描述，每一個節點對應一個鍵-值對，其鍵名為當前節點的信息，鍵值為集合格式，記錄其包含的所有下一級子節點或要素的鍵名。

4)各個節點主要信息均記錄在鍵名中，即

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

[SouthBound]|[NorthBound] ，

(1)

其中： #為索引序列號，按索引編制順序順次編碼，對應某一圖層的一組索引序列號相同； *為索引層號，根節點層號為1，其子節點層號為2，依此類推； [WestBound]，[EastBound]，[SouthBound]和[NorthBound]分別為該節點對應MBR的西、東、南和北邊界。

該索引存儲結構示例如圖2所示。

圖2 R樹存儲結構示例Fig.2 Storage structure example of R-tree index in Redis

4 系統實現

4.1 系統基礎環境

系統實現過程中，選取的計算機軟硬件基礎環境如下： ①操作系統選用Windows Server 2008R2； ②內存數據庫軟件選用Redis 2.8 On Windows； ③集成開發環境選用Microsoft Visual Studio.net 2010； ④開發語言選用C#； ⑤GIS組件選用開源柵格空間數據轉換庫(geospatial data abstraction library,GDAL)/OGR庫。

4.2 矢量數據轉換入庫

該功能將Shapefile格式的矢量數據轉換為2.1節中的存儲結構，并存入Redis數據庫，其實現流程如圖3所示。

圖3 矢量數據轉換入庫流程Fig.3 Data conversion flowchart of shapefile

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

4.3 Key-Value型結構下R樹索引空間檢索

該功能根據輸入的空間查詢條件(包含目標圖層及查詢空間對象)，依據所構建的R樹索引，查找并返回數據庫中符合空間條件的矢量要素，其流程如圖4所示。

圖4 空間數據檢索流程Fig.4 Flowchart of spatial data query

4.4 空間檢索效率測試與對比

系統功能實現后，在相同軟硬件環境下，對比了基于Redis內存數據庫的R樹索引以及傳統基于Oracle數據庫的格網索引2種空間檢索架構的檢索效率。

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

圖5 空間數據檢索效率測試Fig.5 Efficiency test of spatial query

從對比測試結果中可以看到，基于Key-Value型內存數據庫Redis進行空間檢索操作，能夠在海量數據條件下，有效提高空間檢索的效率。

5 結論

本文針對ZY1-02C海量空間數據檢索的應用需求，以及傳統空間檢索架構的限制，基于Key-Value型內存數據庫技術，設計并實現了一種矢量空間數據的存儲架構以及空間索引架構，完成了相應功能開發，現已部署于ZY1-02C相關應用系統中。經對比測試及實際運行檢驗，該架構與傳統基于磁盤的關系型數據庫架構相比，能夠更好地適用于ZY1-02C海量空間數據檢索的應用場景，并有效提升空間檢索操作的效率，取得了良好的應用效果。

[1] 薛 濤,刁明光,李建存,等.資源環境遙感海量空間數據存儲、檢索和訪問方法[J].國土資源遙感,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] 楊武軍,張繼榮,屈軍鎖.內存數據庫技術綜述[J].西安郵電學院學報,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] 王 珊,肖艷芹,劉大為,等.內存數據庫關鍵技術研究[J].計算機應用,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] 朱 進,胡 斌,邵 華,等.基于內存數據庫Redis的輕量級矢量地理數據組織[J].地理信息科學,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] 閻超德,趙學勝.GIS空間索引方法述評[J].地理與地理信息科學,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] 史文中,郭 薇,彭奕彰.一種面向地理信息系統的空間索引方法[J].測繪學報,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樹的空管GIS數據模型索引的設計[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平臺的R樹索引模型研究與實現[J].計算機工程與科學,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.