基于分區(qū)技術(shù)的靜態(tài) R 樹索引并行計(jì)算技術(shù)

R 樹索引性能優(yōu)良，被廣泛用于原型研究和商用空間數(shù)據(jù)庫系統(tǒng)，它是目前最流行、最成功的多維索引結(jié)構(gòu)之一[1]。但在海量空間數(shù)據(jù)的管理過程中，存在 R 樹構(gòu)建時耗過大、數(shù)據(jù)更新效率低、全局索引維護(hù)困難等問題。因此，本文針對靜態(tài) R 樹加載過程良好的可并行性，采用并行計(jì)算技術(shù)并行化 R 樹的構(gòu)建過程，以提高索引構(gòu)建效率。利用大型商用數(shù)據(jù)庫分區(qū)技術(shù)管理海量空間數(shù)據(jù)，在邏輯上保證數(shù)據(jù)的無縫存儲，確保查詢效率并從物理層次上提高海量空間數(shù)據(jù)及其索引的可管理性、可用性和性能。

1 分區(qū)技術(shù)在空間數(shù)據(jù)庫引擎中的應(yīng)用

1.1 分區(qū)技術(shù)

數(shù)據(jù)庫提供的分區(qū)功能可以提高許多應(yīng)用程序的可管理性、性能和可用性。在 GIS 領(lǐng)域，將商用關(guān)系數(shù)據(jù)庫作為空間數(shù)據(jù)的容器，采用分區(qū)技術(shù)提高空間數(shù)據(jù)訪問的性能需要合理確定分區(qū)字段。在分區(qū)的基礎(chǔ)上建立高效、易于管理維護(hù)的空間索引是成功應(yīng)用分區(qū)技術(shù)的關(guān)鍵。

1.2 海量空間數(shù)據(jù)的高效存儲

1.2.1 分區(qū)方案選擇

常見的分區(qū)方法包括范圍分區(qū)、Hash 分區(qū)、列表分區(qū)和組合分區(qū)。空間數(shù)據(jù)的特殊性在于其空間特性，根據(jù) GIS 應(yīng)用的特點(diǎn)，范圍分區(qū)和列表分區(qū)較適合海量空間數(shù)據(jù)的大表分區(qū)存儲。本文采用范圍分區(qū)方法，通過預(yù)先設(shè)定圖幅范圍避免范圍分區(qū)帶來的各分區(qū)數(shù)據(jù)不均勻問題。

1.2.2 數(shù)據(jù)裝載

為保證分區(qū)內(nèi)空間對象地理范圍的連續(xù)性，先根據(jù)數(shù)據(jù)的空間分布特征劃分圖幅范圍，各圖幅應(yīng)該是整個數(shù)據(jù)范圍的一個劃分。如圖 1 所示，根據(jù)數(shù)據(jù)的空間分布情況，將數(shù)據(jù)分為 4 個區(qū)，盡量保證各區(qū)數(shù)據(jù)量均衡。存儲在數(shù)據(jù)庫中4 個不同的表空間內(nèi)，跨圖幅的數(shù)據(jù)單獨(dú)存放在分區(qū) 4 中。

1.2.3 數(shù)據(jù)維護(hù)

基于分區(qū)技術(shù)的空間數(shù)據(jù)存儲使空間數(shù)據(jù)能以分區(qū)為單位被維護(hù)并管理，如數(shù)據(jù)更新、索引維護(hù)等工作可以在單個分區(qū)內(nèi)進(jìn)行，而不影響其他分區(qū)中的數(shù)據(jù)，提高了海量數(shù)據(jù)的可管理性和可維護(hù)性。

2 靜態(tài) R 樹的并行構(gòu)建

2.1 存在的問題

空間數(shù)據(jù)的 R 樹構(gòu)建[2]是 CPU 密集型計(jì)算，且涉及大量I/O 操作，其時耗很大。已有很多方法可以加速 R 樹的構(gòu)建，如 Packed R 樹、Hilbert Packed R 樹、Bercken’s Buffer R 樹、 Arge’s Buffered R 樹等靜態(tài) R 樹，但針對海量數(shù)據(jù)的 R 樹構(gòu)建時間仍然不能滿足實(shí)際應(yīng)用的要求。且全局空間索引維護(hù)困難，海量空間數(shù)據(jù)的 R 樹索引會導(dǎo)致樹深度增加，查詢效率下降。存在小部分?jǐn)?shù)據(jù)“臟區(qū)”時，必須對全局?jǐn)?shù)據(jù)重建空間索引。

針對以上問題，在空間數(shù)據(jù)分區(qū)存儲的基礎(chǔ)上對分區(qū)數(shù)據(jù)并行計(jì)算空間索引，減少索引創(chuàng)建時間。在保證查詢效率的同時，提高全局索引的可維護(hù)性。

2.2 基于 TGS 算法的 R 樹并行構(gòu)建

2.2.1 TGS 算法

Garcia 等人于 1998 提出自上而下的貪婪分裂(Top-down Greedy-Split, TGS)算法，其特點(diǎn)是自上而下地遞歸構(gòu)建 R 樹。

在 R 樹的遞歸分裂過程中，通常采用掃描線分割空間中N 個對象的 MBR 面積作為 TGS 的自定義代價函數(shù)選擇掃描線，即

f(r1, r2)=SArea(r1)+SArea(r2)

其中，SArea(ri)為被掃描線分割的第 i 個部分的面積。

每次遞歸過程中選擇分割當(dāng)前子集中 N 個對象的 MBR面積最小的掃描線，即

S=min(fi(r1, r2))

其中，i=1,2,…,n，n 為掃描線總數(shù);S 為選取的掃描線;fi(r1, r2)表示第 i 條掃描線。

2.2.2 R 樹的并行構(gòu)建

如圖 2 所示，并行計(jì)算 R 樹索引的基本思想如下：采用并行 GIS 處理常用的典型策略[3]，即 DCSO(Decomposition, Conquer, Stitch, Output)策略，本文數(shù)據(jù)分區(qū)存儲實(shí)現(xiàn)了數(shù)據(jù)的自然分解，即問題分解;指定處理節(jié)點(diǎn)分別處理各分區(qū)數(shù)據(jù)，生成 R 樹的子樹;將各子樹作為根節(jié)點(diǎn)的分支節(jié)點(diǎn)插入，完成整體索引創(chuàng)建，得到最終結(jié)果。

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