白 凱，李 敏，王華兵 (長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州 434023)

基于嵌入式數(shù)據(jù)庫的移動(dòng)GIS系統(tǒng)設(shè)計(jì)研究

白 凱，李 敏，王華兵 (長江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州 434023)

針對移動(dòng) GIS 平臺的特點(diǎn)，設(shè)計(jì)并構(gòu)建了一種基于嵌入式數(shù)據(jù)庫的移動(dòng)GIS系統(tǒng)。該系統(tǒng)的核心框架采用訪問者設(shè)計(jì)模式設(shè)計(jì)空間索引接口，基于Packed R-tree 的數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)空間索引，基于適配器設(shè)計(jì)模式實(shí)現(xiàn)對空間數(shù)據(jù)的一體化存儲。實(shí)際應(yīng)用表明，該系統(tǒng)可提高移動(dòng) GIS 的空間查詢效率與存儲能力，且具有較好的可擴(kuò)展性和靈活性。

移動(dòng)GIS；嵌入式數(shù)據(jù)庫； 空間索引策略； Packed R-tree

隨著嵌入式技術(shù)和GIS技術(shù)的成熟和發(fā)展，兩者相結(jié)合的產(chǎn)物——移動(dòng)GIS(也稱嵌入式GIS)的應(yīng)用也逐步擴(kuò)大并迅猛發(fā)展。移動(dòng)GIS就是在嵌入式系統(tǒng)中實(shí)現(xiàn)的地理信息系統(tǒng)。與桌面計(jì)算機(jī)平臺的GIS相比，移動(dòng) GIS具有體積小、功能簡單、數(shù)據(jù)量不大、攜帶方便等特點(diǎn)。針對移動(dòng)GIS的特點(diǎn)和嵌入式系統(tǒng)不足(如CPU運(yùn)算速度慢、存儲空間小等)，筆者設(shè)計(jì)并構(gòu)建了一種基于嵌入式數(shù)據(jù)庫的移動(dòng)GIS系統(tǒng)。

1 移動(dòng)GIS的特點(diǎn)

圖1是一種典型移動(dòng)GIS的主要組成結(jié)構(gòu)圖。

圖1 移動(dòng)GIS的典型組成結(jié)構(gòu)圖

移動(dòng)GIS的數(shù)據(jù)除了具有GIS數(shù)據(jù)的數(shù)據(jù)量大和復(fù)雜的特點(diǎn)外，還必須符合嵌入式系統(tǒng)存儲空間小和計(jì)算檢索簡單快捷的特點(diǎn)。這就產(chǎn)生了移動(dòng)GIS數(shù)據(jù)處理中必須要解決的2大矛盾：①大數(shù)據(jù)量與小存儲空間的矛盾。復(fù)雜的空間數(shù)據(jù)相對于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫的數(shù)據(jù)來說數(shù)據(jù)量大，而且數(shù)據(jù)分布很不均勻。但是在嵌入式系統(tǒng)上，存儲空間非常寶貴，這就要求用更有效的結(jié)構(gòu)和方式使得GIS數(shù)據(jù)的存儲空間更小，使用時(shí)所占內(nèi)存更小。②復(fù)雜的空間檢索需求與嵌入式系統(tǒng)的計(jì)算速度的矛盾。對于移動(dòng)GIS數(shù)據(jù)庫來說，其查詢條件與空間位置相關(guān)而不是屬性數(shù)據(jù)，因此必須采用比桌面操作系統(tǒng)更為靈活的機(jī)制來滿足嵌入式系統(tǒng)的要求[1]。

2 移動(dòng)GIS數(shù)據(jù)庫的空間索引策略

解決上述2大矛盾，可以從2個(gè)方面來考慮：①采用合適的數(shù)據(jù)壓縮技術(shù)；②定制合適的數(shù)據(jù)索引機(jī)制。由于嵌入式系統(tǒng)本身存儲和速度的特點(diǎn)使得索引機(jī)制不能像在桌面操作系統(tǒng)上一樣大而全，對于數(shù)據(jù)的管理和需求也不像桌面操作系統(tǒng)一樣全面，通常它只是運(yùn)用桌面GIS數(shù)據(jù)庫的一部分功能。因此針對該數(shù)據(jù)特點(diǎn)需要定制特定的數(shù)據(jù)索引機(jī)制[2]。

常用的索引策略有：①基于B樹的索引技術(shù)。其范例有R樹及其改進(jìn)，如Packed R樹，R*樹， R+樹，Hilbert R樹等；②基于Hashing的網(wǎng)格文件索引技術(shù)；③基于二叉樹的索引技術(shù)，如KD樹，KDB樹，SKD樹等；④空間填充曲線及四叉樹類。

如果R樹、四叉樹、Buddy樹作為只描述線型數(shù)據(jù)的主存索引，則四叉樹空間占用量最小，Buddy樹空間占用量最大。對于點(diǎn)查詢，Buddy樹速度最快，電量消耗最少，R樹與四叉樹在速度與耗電量上都差不多。對于范圍查詢，Buddy樹與R樹性能比較接近，速度差不多，耗電量也差不多，四叉樹的速度慢，耗電量也大。對于最鄰近查詢，R樹索引速度最快，耗電量最大，四叉樹的速度一般，耗電量最小?？梢?，沒有哪種索引結(jié)構(gòu)有絕優(yōu)勢，應(yīng)根據(jù)具體的系統(tǒng)實(shí)際應(yīng)用來確定相應(yīng)索引策略。

影響檢索速度的一個(gè)重要因素就是檢索樹的深度。采用靜態(tài)批量建樹，這時(shí)R樹的存儲利用率最大，幾乎達(dá)到100%，索引所占的空間最小，深度也最小。Packed R樹的一個(gè)最大的缺點(diǎn)就是在插入方面存在缺陷。當(dāng)需要插入一個(gè)數(shù)據(jù)的時(shí)候，基本上是對每一層的結(jié)點(diǎn)都需要進(jìn)行分裂。由于在電子地圖中不存在結(jié)點(diǎn)的插入操作，因此地圖數(shù)據(jù)庫對于用戶來說是只讀的、靜態(tài)的。所以筆者在建樹時(shí)采用Packed R樹。

3 系統(tǒng)總體設(shè)計(jì)方案

圖2是系統(tǒng)總體設(shè)計(jì)方案。在核心框架中采用一個(gè)抽象幾何體類，該類與其他幾何對象的基本拓?fù)潢P(guān)系進(jìn)行比較，這樣上層移動(dòng) GIS 空間對象的所有復(fù)雜形狀可以通過統(tǒng)一封裝成抽象幾何體類的形式，實(shí)現(xiàn)對具體形狀的解釋，并以統(tǒng)一方式傳遞給索引框架進(jìn)行空間查詢、存儲；索引結(jié)構(gòu)的搜索、查詢結(jié)果也封裝成抽象幾何體類返回給上層移動(dòng)GIS。

圖2 系統(tǒng)總體設(shè)計(jì)方案圖

3.1空間索引框架

移動(dòng)GIS對于空間索引框架的操作主要包括以下2種：①索引建立和修改，記錄插入和刪除；②空間查詢，主要包括范圍查詢和點(diǎn)查詢等。在公共抽象接口中定義了這些通用操作，而在索引結(jié)構(gòu)類(Packed R-tree)中具體實(shí)現(xiàn)這些操作。通用存儲接口對索引結(jié)構(gòu)、空間數(shù)據(jù)的存儲管理操作抽象定義，采用基于LRU 算法(Least Recently Used)的緩沖管理器實(shí)現(xiàn)對索引結(jié)構(gòu)、空間數(shù)據(jù)的緩存，并在存儲管理器中嵌入適配器接口實(shí)現(xiàn)索引結(jié)構(gòu)和空間數(shù)據(jù)在移動(dòng) GIS 關(guān)系數(shù)據(jù)庫的持久化。LRU算法的基本內(nèi)容是：當(dāng)內(nèi)存的剩余的可用空間不夠時(shí)，緩沖區(qū)盡可能先保留使用者最常使用的數(shù)據(jù)，即優(yōu)先清除“較不常使用的數(shù)據(jù)”，并釋放其空間?！拜^不常使用的數(shù)據(jù)”判斷的標(biāo)準(zhǔn)是人為的、不嚴(yán)格的。

索引結(jié)構(gòu)存儲在關(guān)系數(shù)據(jù)庫中，在內(nèi)存中定義一個(gè)緩沖管理器，負(fù)責(zé)管理上層應(yīng)用與底層關(guān)系數(shù)據(jù)庫的數(shù)據(jù)傳輸。對于上層用戶來說，這一處理是透明的。LRU算法實(shí)現(xiàn)的Packed R樹索引結(jié)構(gòu)的緩沖管理器，提高了索引結(jié)構(gòu)的查詢效率。

3.2緩沖管理器實(shí)現(xiàn)方法

緩沖管理器主要實(shí)現(xiàn)索引結(jié)構(gòu)的存取操作，還要實(shí)現(xiàn)2個(gè)重要的緩沖操作：增加入口和減少入口。實(shí)現(xiàn)方法是：每個(gè)入口存儲索引結(jié)構(gòu)近期使用的一個(gè)節(jié)點(diǎn)信息，當(dāng)索引結(jié)構(gòu)載入或存儲數(shù)據(jù)時(shí)，在緩沖區(qū)增加入口；刪除數(shù)據(jù)時(shí)，在緩沖區(qū)減少入口。當(dāng)緩沖區(qū)容量已滿，而需要增加入口時(shí)，則采用 LRU 策略從緩沖區(qū)已有的入口中刪去一個(gè)，加入新的入口。保證緩沖區(qū)的最后一項(xiàng)總是“較不常使用的數(shù)據(jù)即最近一段時(shí)間內(nèi)最長時(shí)間沒有被訪問過的入口”，如果在操作過程中緩沖區(qū)溢出，則直接移走最后一項(xiàng)沒有使用的數(shù)據(jù)塊[3]。

3.3基于適配器的存儲管理器的設(shè)計(jì)方法

在存儲管理器中嵌入一個(gè)關(guān)系數(shù)據(jù)庫的讀寫適配器接口，完成關(guān)系數(shù)據(jù)庫中索引結(jié)構(gòu)、空間數(shù)據(jù)信息和核心框架之間的讀寫邏輯及相互間數(shù)據(jù)傳送。圖2展示了存儲管理器與嵌入式數(shù)據(jù)庫之間的關(guān)系。該適配器接口分別繼承存儲管理器類和 GIS 地理要素類，完成以下適配功能：將字節(jié)組形式數(shù)據(jù)按Packed R 樹節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)解譯成索引結(jié)構(gòu)數(shù)據(jù)和空間數(shù)據(jù)2部分(對非葉結(jié)點(diǎn)，空間數(shù)據(jù)為空)，分別轉(zhuǎn)換成索引表的數(shù)據(jù)和地理要素表的數(shù)據(jù)；將索引表的數(shù)據(jù)和地理要素表的數(shù)據(jù)封裝成字節(jié)組數(shù)據(jù)。在進(jìn)行具體的存取操作時(shí)，存儲管理器通過使用適配器接口轉(zhuǎn)換數(shù)據(jù)，用戶可方便地利用 SQL 訪問接口讀寫底層的移動(dòng) GIS 關(guān)系數(shù)據(jù)庫。

4 結(jié) 語

筆者從嵌入式設(shè)備，嵌入式數(shù)據(jù)庫和移動(dòng)GIS三者的特點(diǎn)出發(fā)，本著充分利用嵌入式設(shè)備資源的設(shè)計(jì)思想，設(shè)計(jì)出一個(gè)完整的、高效的基于嵌入式數(shù)據(jù)庫的移動(dòng)GIS系統(tǒng)構(gòu)架。該系統(tǒng)有一套相應(yīng)的索引策略，能夠高效低耗的管理數(shù)據(jù)，同時(shí)各個(gè)子模塊之間實(shí)現(xiàn)了高內(nèi)聚低耦合的特征，使系統(tǒng)有相當(dāng)高的延展性。在移動(dòng)GIS和嵌入式數(shù)據(jù)庫之間設(shè)計(jì)一個(gè)核心框架，框架采用高效的索引策略，具有很強(qiáng)的針對性，其中基于適配器的設(shè)計(jì)模式實(shí)現(xiàn)了對空間數(shù)據(jù)的一體化存儲。

[1]謝忠,鳳鳴,馬常杰.嵌入式空間索引策略[J].地球科學(xué)——中國地質(zhì)大學(xué)學(xué)報(bào),2006,31(5):653～658.

[2]裴凌,王慶,王慧青.嵌入式GIS的數(shù)據(jù)模型構(gòu)造方法[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,35(3):480～483.

[3]蔡苗紅,王慶.移動(dòng)GIS的嵌入式空間索引框架的構(gòu)建[J].計(jì)算機(jī)工程，2006，32(23)：91～93.

[編輯] 李啟棟

TP393

A

1673-1409(2009)01-N082-03

2008-12-18

湖北省教育廳基金資助項(xiàng)目(B200612012)。

白凱(1980-)，男，2002年大學(xué)畢業(yè)，講師，碩士生，現(xiàn)主要從事嵌入式系統(tǒng)方面的教學(xué)與研究工作。