大型空間數(shù)據(jù)庫的并發(fā)索引策略 CQR樹

R 樹是目前最流行的動(dòng)態(tài)空間索引結(jié)構(gòu)之一。多用戶并發(fā)環(huán)境下 ,現(xiàn)有的 R 樹并發(fā)控制算法 ,如 R2link 樹[1 ] 及其改進(jìn)算法[2 ] ,改變了 R 樹存儲(chǔ)結(jié)構(gòu) ,在原始 R 樹的基礎(chǔ)上添加控制信息 ,不易與現(xiàn)有系統(tǒng)的 R 樹結(jié)合 ;純粹基于加鎖的控制算法[3 ] ,使得并發(fā)處理更為復(fù)雜 , 而且容易出現(xiàn)死鎖。這些算法都不適合海量空間數(shù)據(jù)的并發(fā)操作。本文提出了適用于客戶端方式空間數(shù)據(jù)庫引擎并發(fā)控制的空間索引結(jié)構(gòu) ———CQR 樹。將靜態(tài) R 樹與四叉樹相結(jié)合 ,四叉樹編碼與空間對(duì)象綁定管理被編輯過的對(duì)象 ,僅在刪除葉子結(jié)點(diǎn)包中的對(duì)象時(shí)對(duì)索引包加鎖 ,縮短系統(tǒng)響應(yīng)時(shí)間。

1 　空間數(shù)據(jù)引擎與空間索引

目前的空間數(shù)據(jù)庫擴(kuò)展大多采用 R 樹及其變種建立數(shù)據(jù)集的空間索引。從提供方來看 ,可以把空間數(shù)據(jù)引擎或空間擴(kuò)展分為數(shù)據(jù)庫平臺(tái)和GIS 平臺(tái)兩類?；蛘卟痪窒抻?GIS 平臺(tái) ,分為數(shù)據(jù)庫方和非數(shù)據(jù)庫方?？臻g索引與空間數(shù)據(jù)引擎或空間擴(kuò)展的結(jié)合也可以據(jù)此分為內(nèi)嵌式和外掛式兩類[4 ] 。

內(nèi)嵌式空間索引內(nèi)置于數(shù)據(jù)庫內(nèi)核 ,直接操

縱空間數(shù)據(jù)類型。由數(shù)據(jù)庫方提供的空間擴(kuò)展多提供內(nèi)嵌式空間索引 ,如 Oracle Spatial 的 R 樹 , IBM DB2 和 Informix 的網(wǎng)格索引和 R 樹 , Po st2 GIS 的 GIST R 樹等。外掛式空間索引的創(chuàng)建和維護(hù)都獨(dú)立于數(shù)據(jù)庫管理系統(tǒng)而自行管理。由GIS 平臺(tái)提供的空間數(shù)據(jù)引擎多提供外掛式空間索引 ,如 ESRI ArcSDE 的三級(jí)格網(wǎng)索引 , Super2 Map SDX + 提供的混合索引等 , GRASS 平臺(tái)提供的是外掛文件式的 R 樹索引。外掛式索引靈活可控 ,能夠選擇各種類型的空間索引加以實(shí)現(xiàn) ,但卻無法借助數(shù)據(jù)庫的先進(jìn)功能 ,對(duì)于數(shù)據(jù)的頻繁更新和并發(fā)操作均有不利影響。

1. 1 　空間數(shù)據(jù)引擎的外掛 R 樹索引

在 RDBMS 中對(duì)空間數(shù)據(jù)的訪問主要有 3 種方式 :服務(wù)器方式、客戶端方式和混合方式[ 5 ] 。本文主要針對(duì)客戶端方式 ,空間數(shù)據(jù)引擎作為客戶端接口 ,直接把空間請(qǐng)求轉(zhuǎn)換成標(biāo)準(zhǔn) SQL 命令發(fā)送到 RDBMS 上 ,并解釋所返回的數(shù)據(jù) ,見圖 1。

在客戶端對(duì)數(shù)據(jù)進(jìn)行編輯更新的同時(shí) ,空間數(shù)據(jù)引擎需要對(duì)空間索引進(jìn)行維護(hù)。對(duì) R 樹索引而言 ,R 樹的葉子節(jié)點(diǎn)即索引包通常以二進(jìn)制方式存儲(chǔ)在數(shù)據(jù)庫中 ,更新時(shí) ,首先確定需要更新的索引包 ,然后將索引包取到客戶端內(nèi)存 ,在內(nèi)存中更新后 ,由空間數(shù)據(jù)引擎提交到數(shù)據(jù)庫服務(wù)器端。如圖 2 所示。

1. 2 　R 樹存在的問題

由于多用戶并發(fā)編輯同一索引包里的對(duì)象時(shí) ,都是在客戶端內(nèi)存操作然后提交到數(shù)據(jù)庫服務(wù)器 ,因此 ,多客戶端對(duì)索引包的修改會(huì)被最后一個(gè)提交的結(jié)果覆蓋 ,從而導(dǎo)致并發(fā)編輯對(duì)象“丟失”(實(shí)際上數(shù)據(jù)已經(jīng)被更新 ,但由于在索引包中丟失信息導(dǎo)致索引不到該對(duì)象) 或結(jié)果不正確。例如 ,客戶端 A 和客戶端 B 同時(shí)向索引包 R i 中添加對(duì)象 A k 、B k , 后更新的 B k 將覆蓋先更新的A k 在索引包中的數(shù)據(jù) ,導(dǎo)致 A k“丟失”。

這種情況雖然可以通過對(duì)索引表 (見圖 2) 加行級(jí)鎖來解決 ,但在 R 樹中 ,由于關(guān)鍵字是非排序的甚至可能是相互重疊的 ,而且每個(gè)更新操作還需要頻繁地進(jìn)行數(shù)據(jù)的向上回溯 ,因此僅僅采用加鎖機(jī)制將使得并發(fā)處理更為復(fù)雜而且容易出現(xiàn)死鎖。R2link 樹是為解決 R 樹的并發(fā)控制問題而提出的 ,它在 R 樹的基礎(chǔ)上增加相關(guān)控制輔助信息 ,從而允許各種操作并發(fā)執(zhí)行而不會(huì)出現(xiàn)死鎖 ,但它的數(shù)據(jù)結(jié)構(gòu)復(fù)雜 ,且仍然存在海量數(shù)據(jù)R 樹維護(hù)困難的問題。

外掛模式下海量數(shù)據(jù)的 R 樹更新操作還存在操作費(fèi)時(shí)及索引邊界外對(duì)象難以維護(hù)的問題。對(duì)海量空間數(shù)據(jù)而言 ,其他參數(shù)一定的條件下 ,R樹的深度劇增 ,確定需要更新的葉子節(jié)點(diǎn)以及節(jié)點(diǎn)分裂等操作都比較復(fù)雜費(fèi)時(shí) ,盡管可以通過增加 R 樹葉子節(jié)點(diǎn)的容量來降低 R 樹的高度 ,但是 ,葉子節(jié)點(diǎn)容量的增加會(huì)導(dǎo)致索引包增大 ,加大了客戶端訪問數(shù)據(jù)時(shí)的通信量。R 樹索引根結(jié)點(diǎn)的范圍一定 ,當(dāng)編輯的對(duì)象在此范圍之外時(shí) ,涉及R 樹的一系列復(fù)雜操作 ,尤其當(dāng) R 樹深度較深時(shí) ,這種操作更加難以維護(hù)。因此 ,單純的 R 樹索引并不能滿足海量數(shù)據(jù)并發(fā)編輯的要求。

更多內(nèi)容請(qǐng)查看pdf