劉永山，龔 翔，孔德瀚，單磊敬

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北環(huán)境工程學(xué)院 信息工程系，河北 秦皇島 066102；3. 中國(guó)人民解放軍聯(lián)勤保障部隊(duì)北戴河康復(fù)療養(yǎng)中心，河北 秦皇島 066100)

0 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展，獲取到的空間數(shù)據(jù)量成倍翻升，有效地管理大規(guī)模的空間數(shù)據(jù)變得越來越困難[1-3]。面對(duì)海量的三維空間數(shù)據(jù)，如何建立高效的索引結(jié)構(gòu)來有效地提高大規(guī)模數(shù)據(jù)的檢索查詢效率[4-5]，成為了空間數(shù)據(jù)庫(kù)領(lǐng)域的研究熱點(diǎn)[6]。

在現(xiàn)實(shí)世界中，存在著這樣一種三維場(chǎng)景分布情況，在某些區(qū)域范圍內(nèi)對(duì)象可能是密集聚集分布的，而另外一些區(qū)域內(nèi)的對(duì)象則是以無規(guī)則的方式零星分布著。這類情況是常見的：比如三維城市模型，在城市的中心地帶，高樓林立并且建筑分布比較集中，而在遠(yuǎn)離城市中心的邊緣地帶，多以低層建筑居多。再比如地下商業(yè)圈，地下礦產(chǎn)資源分布，大氣污染物PM2.5的分布等等，這些三維數(shù)據(jù)對(duì)象都呈現(xiàn)著局部分布密度差異大，且分布較為不均勻的特點(diǎn)。如若采用單一的空間索引結(jié)構(gòu)來存儲(chǔ)管理這些數(shù)據(jù)，往往會(huì)帶來結(jié)構(gòu)占用巨大的存儲(chǔ)空間問題或是效率低下的檢索查詢問題。本文正是基于這樣一種考慮，提出并設(shè)計(jì)了三維網(wǎng)格-R樹混合空間索引，用空間分塊的思想來解決不同區(qū)域內(nèi)數(shù)據(jù)密度不一的問題，在一定程度上提高了數(shù)據(jù)檢索查詢效率。

文章的結(jié)構(gòu)安排如下：本文在第1部分對(duì)研究現(xiàn)狀進(jìn)行了介紹和分析。第2部分提出基于三維網(wǎng)格-R樹的混合索引結(jié)構(gòu)。第3部分給出混合索引結(jié)構(gòu)的維護(hù)操作。第4部分介紹基于三維網(wǎng)格-R樹的查詢算法，第5部分以實(shí)驗(yàn)仿真數(shù)據(jù)驗(yàn)證了混合索引的查詢效率。

1 研究現(xiàn)狀

當(dāng)前的三維空間索引技術(shù)研究主要集中在網(wǎng)格索引[7]、八叉樹[8]、三維R樹[9]以及一些簡(jiǎn)單的混合樹研究方面[10]。

網(wǎng)格其實(shí)是一種基于Hashing的索引方法，它通過橫豎線將數(shù)據(jù)空間劃分成若干網(wǎng)格塊，唯一標(biāo)識(shí)每個(gè)網(wǎng)格，記錄每個(gè)網(wǎng)格中所有的空間對(duì)象[11]。

八叉樹是四叉樹在三維空間上的擴(kuò)展[12]，常用于劃分三維空間，它的每個(gè)結(jié)點(diǎn)表示一個(gè)立方體，每個(gè)結(jié)點(diǎn)有8個(gè)子結(jié)點(diǎn)，這8個(gè)子結(jié)點(diǎn)所表示的體積元素加在一起就等于父結(jié)點(diǎn)的體積[13]。八叉樹的空間分割是依據(jù)三維空間實(shí)體分布的特點(diǎn),首先建立空間實(shí)體的最小外包立方體，然后對(duì)外包立方體按照8個(gè)象限進(jìn)行遞歸分割，逐步分解成一系列子空間立方體，如圖1所示，它具有快速劃分三維空間、按照記錄結(jié)點(diǎn)快速高效查詢的特點(diǎn)[14]。

圖1 八叉樹示意圖
Fig.1 The model of octree

R樹是由Guttman于1984年提出的[15]，三維R樹是R樹在三維空間的拓展，具有自動(dòng)平衡、適用于外存存儲(chǔ)、空間利用率高、查詢效率高等優(yōu)點(diǎn)。

如圖2是一棵三維R樹向二維空間水平面的投影示意圖，(a)中實(shí)線框(r1，r2，…，r8)表示空間目標(biāo)的最小包圍盒，p1，p2，…，p10表示空間數(shù)據(jù)點(diǎn)；實(shí)線框(R1，R2，…，R8)表示中間結(jié)點(diǎn)索引項(xiàng)對(duì)應(yīng)的索引空間，即目錄矩形[16]。從圖中可以看出，目錄矩形允許重疊。

另外，龔俊等人提出了一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法[17],較好地解決了大規(guī)模獲取到的激光點(diǎn)云數(shù)據(jù)管理問題。但應(yīng)用場(chǎng)景僅限于海量均勻分布的點(diǎn)云數(shù)據(jù)，由于八叉樹自身具有很大的局限性，當(dāng)想要索引某一區(qū)域內(nèi)密集的數(shù)據(jù)時(shí)，不得不對(duì)八叉樹的中間節(jié)點(diǎn)繼續(xù)向下做八叉樹劃分，造成極大的空間開銷，索引的效率也由于樹層次的增加受到了影響。鄭坤等人提出了三維GIS中LOD_OR樹空間索引結(jié)構(gòu)[18]，利用八叉樹索引將R樹表示的空間進(jìn)行了限制,減輕了R樹插入、刪除的開銷。同理，該方法最外層由于八叉樹劃分空間的限制，同樣做不到區(qū)域密集數(shù)據(jù)的良好索引。且隨著八叉樹索引層數(shù)的增加，局部插入、刪除的開銷并不樂觀。這些結(jié)構(gòu)改進(jìn)了使用單一索引結(jié)構(gòu)時(shí)的不足，在一定程度上提高了三維數(shù)據(jù)的管理查詢效率，但針對(duì)本文所提出的問題，這些結(jié)構(gòu)仍有較大的弊端，不能在實(shí)際意義上真正解決關(guān)注的問題。

圖2 三維R樹在二維空間平面投影結(jié)構(gòu)示意圖
Fig.2 Schematic diagram of three-dimensional R tree projection in two-dimensional space

2 三維網(wǎng)格-R樹混合索引結(jié)構(gòu)

為了構(gòu)建三維網(wǎng)格-R樹混合索引結(jié)構(gòu)，首先，需要根據(jù)整個(gè)空間的區(qū)域大小，選取合適的長(zhǎng)、寬、高劃分值將整個(gè)三維空間快速劃分好，整個(gè)空間區(qū)域即為三維網(wǎng)格-R樹的根結(jié)點(diǎn)。對(duì)于數(shù)據(jù)點(diǎn)密度不均勻，分布較為稀疏的區(qū)域，按照網(wǎng)格粗略劃分后，將三維點(diǎn)元數(shù)據(jù)添加至相對(duì)應(yīng)的子網(wǎng)格葉結(jié)點(diǎn)內(nèi)，而不再需要添加至龐大的R樹索引結(jié)構(gòu)中。對(duì)于數(shù)據(jù)點(diǎn)分布密集的區(qū)域，可能一次粗略的網(wǎng)格劃分并不夠。這時(shí)，需要將這些子網(wǎng)格內(nèi)的三維點(diǎn)元數(shù)據(jù)構(gòu)建R樹結(jié)構(gòu)?；旌纤饕Y(jié)構(gòu)構(gòu)建的基本流程圖如圖3所示。采用這樣的混合索引結(jié)構(gòu)，避免了單獨(dú)使用八叉樹、網(wǎng)格索引數(shù)據(jù)密度大或者索引結(jié)構(gòu)過于深的弊端。在減少了構(gòu)建R樹開銷的同時(shí)，更好地保證了數(shù)據(jù)的查詢效率。在傳統(tǒng)的R樹索引結(jié)構(gòu)內(nèi)搜索那些稀疏的區(qū)域，由于R樹中間結(jié)點(diǎn)過多，可能查詢會(huì)走過許多無用的結(jié)點(diǎn)，同時(shí)由于R樹的中間結(jié)點(diǎn)允許重疊，在訪問數(shù)據(jù)點(diǎn)密度不均勻區(qū)域時(shí)，會(huì)出現(xiàn)大量的重復(fù)查詢路徑。而在三維網(wǎng)格-R樹混合索引結(jié)構(gòu)內(nèi)查找數(shù)據(jù)密度較為稀疏的數(shù)據(jù)區(qū)域，并不需要從復(fù)雜的R樹結(jié)構(gòu)中去查詢，而是直接從外層的網(wǎng)格結(jié)構(gòu)中直接找到，節(jié)省了查詢時(shí)間，提高了效率。同樣的，對(duì)于密集的數(shù)據(jù)區(qū)域內(nèi)的查詢，也無需從原本復(fù)雜龐大的R樹結(jié)構(gòu)中去查找，而是從一個(gè)個(gè)“小”的獨(dú)立的網(wǎng)格子R樹中去查詢?；谌S網(wǎng)格-R樹混合索引的本質(zhì)其實(shí)就是將一棵大的復(fù)雜的三維R樹拆分成許多“小”的三維R樹，并且按照網(wǎng)格快速劃分空間的優(yōu)勢(shì)來統(tǒng)一管理。

圖3 構(gòu)建混合索引結(jié)構(gòu)基本流程圖
Fig.3 The flow chart for constructing a hybrid index structure

在外層網(wǎng)格結(jié)構(gòu)的劃分中，一般將三維空間劃分為M×N×K個(gè)均等的小網(wǎng)格，每個(gè)網(wǎng)格區(qū)域?yàn)橐粋€(gè)索引項(xiàng)，分配一個(gè)動(dòng)態(tài)存儲(chǔ)區(qū)，在索引項(xiàng)中記錄了所有落在該區(qū)域內(nèi)的三維數(shù)據(jù)點(diǎn)。如果M、N、K的值選取得過大，將會(huì)極大地增加存儲(chǔ)開銷，影響到系統(tǒng)的整體性能，因此只能根據(jù)實(shí)際情況即數(shù)據(jù)集的大小由用戶選擇適當(dāng)?shù)闹?。?dāng)數(shù)據(jù)集較小時(shí)，可以選擇較小的劃分方式，如圖4所示是一個(gè)2×2×2方式劃分的網(wǎng)格。而當(dāng)數(shù)據(jù)集比較大時(shí)，可以適當(dāng)?shù)母鶕?jù)空間位置信息增大網(wǎng)格的劃分方式。

圖4 網(wǎng)格劃分結(jié)構(gòu)圖
Fig.4 The structure diagram of grid division

在外層網(wǎng)格中，從世界域的原點(diǎn)出發(fā)按照z-y-x的編碼順序依次為每一個(gè)子網(wǎng)格循環(huán)遞增編碼，將其索引號(hào)記錄至各自網(wǎng)格結(jié)點(diǎn)的索引號(hào)IndexofGrid中去。假設(shè)整個(gè)三維空間網(wǎng)格的長(zhǎng)、寬、高劃分方式為a×b×c，那么一個(gè)子網(wǎng)格的長(zhǎng)la、寬lb、高lc計(jì)算公式分別為

(1)

(2)

(3)

式中，xmax，xmin，ymax，ymin，zmax，zmin分別表示在x軸，y軸和z軸數(shù)據(jù)對(duì)象的最大坐標(biāo)點(diǎn)和最小坐標(biāo)點(diǎn)。在這種初步劃分方式下，某些子網(wǎng)格內(nèi)的三維點(diǎn)元數(shù)量并未達(dá)到用戶事先規(guī)定的閾值，則滿足網(wǎng)格-R樹葉子結(jié)點(diǎn)要求，不再向下劃分；而如果子網(wǎng)格內(nèi)仍有大量的數(shù)據(jù)點(diǎn)，即超過了閾值的要求，則將此網(wǎng)格作為向下構(gòu)建網(wǎng)格子R樹的根結(jié)點(diǎn)，向下建立二級(jí)R樹結(jié)構(gòu)，使其在該子網(wǎng)格葉結(jié)點(diǎn)中的所有記錄統(tǒng)統(tǒng)存儲(chǔ)至該網(wǎng)格子R樹結(jié)構(gòu)中。此時(shí)，這棵網(wǎng)格子R樹結(jié)構(gòu)僅僅管理著該區(qū)域范圍內(nèi)的三維點(diǎn)元數(shù)據(jù)，屬于其它子網(wǎng)格中間結(jié)點(diǎn)中的三維點(diǎn)元數(shù)據(jù)并不在其管理的范圍內(nèi)。通過這樣的方式，降低了傳統(tǒng)R樹結(jié)構(gòu)的平均深度，不需要將所有的三維點(diǎn)元數(shù)據(jù)集放在一棵大的三維R樹中，在減少了I/O操作的同時(shí)提高了查詢的效率。某些數(shù)據(jù)集分布不均勻的情況下可以很大程度上減少空間的重疊，提高了整體的性能。

此混合索引的數(shù)據(jù)結(jié)構(gòu)包括一個(gè)外層網(wǎng)格結(jié)構(gòu)以及若干個(gè)網(wǎng)格子R樹結(jié)構(gòu)。其中網(wǎng)格結(jié)構(gòu)記錄著所有的子網(wǎng)格中間結(jié)點(diǎn)信息，在所有的網(wǎng)格-R樹中間結(jié)點(diǎn)中，記錄著指向數(shù)據(jù)項(xiàng)數(shù)組或是R樹根結(jié)點(diǎn)的指針。描述如圖5所示。

圖5 混合索引結(jié)構(gòu)示意圖
Fig.5 The diagram of hybrid index structure

其中網(wǎng)格中間結(jié)點(diǎn)記錄著索引號(hào)IndexofGrid，所有子網(wǎng)格葉子結(jié)點(diǎn)信息：包含著一個(gè)Flag標(biāo)識(shí)，以及指向數(shù)據(jù)項(xiàng)數(shù)組或是內(nèi)層R樹根結(jié)點(diǎn)的指針。在圖的最左側(cè)是記錄著所有子網(wǎng)格結(jié)構(gòu)信息的泛型List集合。其中包括：網(wǎng)格中間結(jié)點(diǎn)的索引號(hào)，該結(jié)點(diǎn)所代表的空間區(qū)域范圍，以及該結(jié)構(gòu)下是否有子R樹二級(jí)索引結(jié)構(gòu)的標(biāo)志。比如其中的第一條結(jié)構(gòu)代表著它是網(wǎng)格索引號(hào)為0的子網(wǎng)格，(0，0，0)，(50，50，50)分別代表著該網(wǎng)格中間結(jié)點(diǎn)的左下前坐標(biāo)以及右后上坐標(biāo)，即表示著0≤x<50，0≤y<50，0≤z<50這片空間區(qū)域范圍。它的Flag標(biāo)識(shí)為false，意味著在該中間結(jié)點(diǎn)下沒有二級(jí)R樹索引。相反，如果結(jié)構(gòu)中的Flag標(biāo)志為true，意味著該網(wǎng)格結(jié)點(diǎn)下還存在著二級(jí)R樹結(jié)構(gòu)。

3 混合索引結(jié)構(gòu)的維護(hù)

3.1 插入操作

三維網(wǎng)格-R樹混合索引結(jié)構(gòu)的插入操作算法偽代碼如下所示。

輸入：point q, root of Grid-R tree

輸出：none

BEGIN

1: Index←Calculate(q);

2: Root←Root of Grid-R tree;

3: If(Grid[Index].Flag is fasle) Then

4: Root[Index].LeafNode.Add(q);

5: Else

6: L←ChooseNode(Root[Index]);

7: If L is not overfill Then

8: LeafNode(L)←q;

9: Else

10: L,LL←SplitNode(L);

11: AdjustTree(L);

12: Grid-Rtree.Height++;

13: LeafNode(L)←q

ChooseNode(N)//選擇結(jié)點(diǎn)算法

Root←N;

If Root is LeafNode

Return N;

Else

For each node E in Root

Find the smallest E.I when insert q

If E.ChildNode is null

Return E;

Else

Root←E Then goto (2);

AdjustTree (N)//調(diào)整樹算法

P←Parent Node of N;

En←Pointer from P to N;

Adjust En.I to surround N;

If NN←N.Split//若結(jié)點(diǎn)分裂導(dǎo)致了向上傳遞

Pointer Enn←NN;

If P has enough space

Add Enn to P;

Else

P，PP←P.Split;

END

算法流程：

1) 計(jì)算得出新插入的三維點(diǎn)元對(duì)象所在的網(wǎng)格索引號(hào)index(第1行)。

2) 根據(jù)index可以定位到其所在的網(wǎng)格中間結(jié)點(diǎn)，接著判斷該子網(wǎng)格結(jié)點(diǎn)中的標(biāo)識(shí)flag是true還是 false，也就是在子網(wǎng)格內(nèi)原先是否有存在的R樹結(jié)構(gòu)。若為false，則將該條插入的點(diǎn)元對(duì)象直接插入該index對(duì)應(yīng)的網(wǎng)格-R樹葉結(jié)點(diǎn)中(第2～3行)。

這里考慮一種臨界情況：即插入該條三維點(diǎn)元數(shù)據(jù)對(duì)象后，正好達(dá)到了該子網(wǎng)格-R樹葉子結(jié)點(diǎn)設(shè)定的閾值要求。此時(shí)應(yīng)將原本在該子網(wǎng)格葉結(jié)點(diǎn)存儲(chǔ)著點(diǎn)元數(shù)據(jù)執(zhí)行出隊(duì)操作，并將出隊(duì)的三維點(diǎn)元數(shù)據(jù)對(duì)象逐一添加至內(nèi)層二級(jí)網(wǎng)格子R樹結(jié)構(gòu)中。此時(shí)網(wǎng)格-R樹內(nèi)的插入操作其實(shí)質(zhì)是在“小”的獨(dú)立且相互不重疊網(wǎng)格子R樹內(nèi)進(jìn)行插入操作。

3) 當(dāng)三維點(diǎn)元對(duì)象數(shù)據(jù)插入進(jìn)來時(shí)標(biāo)志flag已經(jīng)為true，說明網(wǎng)格-R樹中間結(jié)點(diǎn)下已經(jīng)有了子R樹結(jié)構(gòu)，則直接向該子網(wǎng)格R樹結(jié)構(gòu)中插入該條記錄，插入過程如上臨界情況所述。

該算法相比傳統(tǒng)的R樹插入算法，優(yōu)勢(shì)更為明顯。首先，外層網(wǎng)格提供了快速均勻劃分空間的特性。其次，設(shè)置閾值的操作又可以保證該索引結(jié)構(gòu)豐富的靈活性。對(duì)于稀疏空間區(qū)域的數(shù)據(jù)，可能僅僅需要一次操作就可以達(dá)到目的。同時(shí)，密集數(shù)據(jù)區(qū)域劃分子R樹的設(shè)計(jì)拆分了原先龐大無比的R樹，使得插入算法更便捷迅速。

圖6為一棵三維網(wǎng)格-R樹中間結(jié)點(diǎn)的插入過程。由上述介紹的網(wǎng)格-R樹插入算法可以知道，當(dāng)新來的三維點(diǎn)元數(shù)據(jù)對(duì)象P到來時(shí)，通過公式計(jì)算選擇將其插入到了網(wǎng)格-R樹結(jié)構(gòu)下的某一中間結(jié)點(diǎn)內(nèi)。此時(shí)，執(zhí)行ChooseNode方法選擇對(duì)象P應(yīng)該插入至當(dāng)前哪一個(gè)網(wǎng)格-R樹葉結(jié)點(diǎn)中。其中，Minimum Bounding Rectangle(MBR)為結(jié)點(diǎn)的最小邊界矩形。

圖6 三維網(wǎng)格-R樹插入操作示意圖
Fig.6 The diagram of insertion of 3D grid-R tree

由于插入數(shù)據(jù)對(duì)象P之后，葉結(jié)點(diǎn)A與葉結(jié)點(diǎn)B的最小外包圍矩形框MBRA與MBRB增長(zhǎng)如圖所示。顯然，MBRA擴(kuò)張的要比MBRB小，因此下一步選擇將P插入至葉子結(jié)點(diǎn)A當(dāng)中。但由于此時(shí)葉結(jié)點(diǎn)A中無額外空間來存儲(chǔ)P，因此將結(jié)點(diǎn)A分裂成如右圖所示的A與AA兩個(gè)結(jié)點(diǎn)。此時(shí)，原本在A結(jié)點(diǎn)中的數(shù)據(jù)對(duì)象1分至新結(jié)點(diǎn)A中；而數(shù)據(jù)對(duì)象2與新插入的數(shù)據(jù)對(duì)象P則存至新結(jié)點(diǎn)AA中。接下來，執(zhí)行AdjustTree操作。在葉結(jié)點(diǎn)A與AA的上一層找到其父結(jié)點(diǎn)，并將其指向該結(jié)點(diǎn)MBR的指針修改為此時(shí)恰好包圍葉結(jié)點(diǎn)A與AA的最小外包圍矩形框，插入操作結(jié)束。

3.2 刪除操作

三維網(wǎng)格-R樹混合索引結(jié)構(gòu)的刪除操作算法偽代碼描述如下所示。

輸入：point q, root of Grid-R tree

輸出：none

BEGIN

1: Index←Calculate(q);

2: Root←Root of Grid-R tree;

3: If(Root[index].Flag is fasle)

4: Delete(q) from Root[Index];

5: Else

6: For each node N in Root[Index] Do

7: If MBRn intersects with q Then

8: If N.Count≥m

9: Adjust I.MBR to enclose all child′s rectangles；

10: N.Count:=N.Count-1;

11: Else//結(jié)點(diǎn)下溢

12: CondenseTree(N);

CondenseTree(N)

Q←NewQueueList;/初始化鏈表Q

If N.Level = 0

Goto(9);

Else

P is parent of N; En←P point to N;

Delete En from P;

Q←N. rectangle;

Set N←P; goto(2);

Q←NewQueueList;

If N.Level = 0

Goto(9);

Else

P is parent of N; En←P point to N;

Delete En from P;

Q←N. rectangle;

Set N←P; goto(2);

ReInsert all remain entries of Q;

END

算法流程：

1) 計(jì)算出該刪除的三維點(diǎn)元對(duì)象所在的網(wǎng)格-R樹的中間結(jié)點(diǎn)索引號(hào)index(第1行)。

2) 判斷該網(wǎng)格-R樹中間結(jié)點(diǎn)中的標(biāo)識(shí)flag為true or false，也就是該條要?jiǎng)h除的點(diǎn)元數(shù)據(jù)記錄是否存在于網(wǎng)格子R樹索引中(第2～5行)。若為false，則在該index對(duì)應(yīng)的網(wǎng)格-R樹葉結(jié)點(diǎn)所存儲(chǔ)的動(dòng)態(tài)鏈表中找到該條三維點(diǎn)元數(shù)據(jù)對(duì)象直接刪除即可，并將該網(wǎng)格-R樹葉結(jié)點(diǎn)的Count值減1。

3) 若flag標(biāo)志為true，證明在該網(wǎng)格-R樹中間結(jié)點(diǎn)下已經(jīng)存在子R樹結(jié)構(gòu)。這時(shí)，執(zhí)行相應(yīng)的網(wǎng)格子R樹刪除對(duì)象操作(第6～10行)。將該網(wǎng)格-R樹中間結(jié)點(diǎn)作為三維網(wǎng)格子R樹根結(jié)點(diǎn)，自此開始，依次檢索該網(wǎng)格子R樹根結(jié)點(diǎn)下相對(duì)應(yīng)的子樹。直至查找到該條待刪除記錄所在的葉子結(jié)點(diǎn)后，刪除其對(duì)應(yīng)的結(jié)點(diǎn)記錄即可。如果刪除后該葉子結(jié)點(diǎn)內(nèi)單元數(shù)少于m，則需要進(jìn)行網(wǎng)格-子R樹的CondenseTree操作。

該算法同插入算法一樣，優(yōu)勢(shì)體現(xiàn)在由于外層嵌套了網(wǎng)格結(jié)構(gòu)，可以根據(jù)要?jiǎng)h除的數(shù)據(jù)信息快速地定位至一個(gè)小的區(qū)域空間。這正是利用了網(wǎng)格可以快速劃分?jǐn)?shù)據(jù)空間的特性。同時(shí)在密集數(shù)據(jù)區(qū)域內(nèi)的子R樹結(jié)構(gòu)中刪除，減少了原先從龐大唯一R樹結(jié)構(gòu)中刪除的繁瑣。既便于稀疏數(shù)據(jù)空間的刪除，又利于數(shù)據(jù)密集區(qū)域部分的刪除。使得原本復(fù)雜且耗時(shí)的操作變得有針對(duì)性，更高效。

這里仍然考慮一種網(wǎng)格-R樹刪除操作過程中的臨界情況：當(dāng)刪除一條記錄后，子網(wǎng)格-R樹葉子結(jié)點(diǎn)內(nèi)的點(diǎn)元數(shù)量小于設(shè)定的閾值要求，規(guī)定一個(gè)下限閾值。當(dāng)數(shù)量在下限閾值至閾值之間時(shí)不作任何處理，允許在這個(gè)范圍內(nèi)繼續(xù)刪除而不解散這棵子網(wǎng)格子R樹，因?yàn)楹罄m(xù)可能會(huì)繼續(xù)執(zhí)行插入操作而引起該網(wǎng)格子R樹的重構(gòu)，降低系統(tǒng)性能。而當(dāng)數(shù)量遠(yuǎn)遠(yuǎn)小于這個(gè)下限閾值時(shí)，此時(shí)開始解散當(dāng)前網(wǎng)格子R樹結(jié)構(gòu)，將所有空間對(duì)象記錄從該結(jié)構(gòu)中取出保存至網(wǎng)格-R樹葉結(jié)點(diǎn)所對(duì)應(yīng)的鏈表即可。

圖7是一棵三維網(wǎng)格-R樹中間結(jié)點(diǎn)的刪除操作示意圖。假如刪除r1，p1，p4，首先根據(jù)路徑：網(wǎng)格-R樹根結(jié)點(diǎn)→R1所指結(jié)點(diǎn)→R3所指結(jié)點(diǎn)，找到其所在葉子結(jié)點(diǎn)對(duì)于的數(shù)據(jù)項(xiàng)并分別刪除之。此時(shí)產(chǎn)生結(jié)點(diǎn)下溢，依據(jù)CondenseTree操作刪除結(jié)點(diǎn)R3，并調(diào)整R1所在目錄矩形使其完全包圍R4、R5。執(zhí)行刪除操作之后的三維網(wǎng)格-R樹中間結(jié)點(diǎn)的整體結(jié)構(gòu)如圖7所示。

4 基于三維網(wǎng)格-R樹的查詢算法

設(shè)計(jì)好三維網(wǎng)格-R樹混合索引結(jié)構(gòu)之后，針對(duì)其提出一種查詢算法。該算法的核心設(shè)計(jì)思想是通過簡(jiǎn)單的計(jì)算，利用外層網(wǎng)格空間和查詢目標(biāo)空間二者的重疊區(qū)域快速定位空間范圍。通過索引內(nèi)有無子R樹的標(biāo)志，靈活適應(yīng)查詢數(shù)據(jù)區(qū)密集與查詢數(shù)據(jù)區(qū)稀疏的不同應(yīng)用場(chǎng)景。相比傳統(tǒng)的R樹查詢算法，大大減少了與R樹中間節(jié)點(diǎn)的重疊檢測(cè)與計(jì)算，做到了不同應(yīng)用場(chǎng)景進(jìn)行查詢的普適性和快捷高效性。

圖7 三維網(wǎng)格-R樹刪除操作示意圖
Fig.7 The diagram of delete of 3D Grid-R tree

基于三維網(wǎng)格-R樹混合索引結(jié)構(gòu)的區(qū)域查詢算法偽代碼描述如下所示。

輸入：root node N, region query W

輸出：PointList

BEGIN

1: PointList←NewList; Queue←NewQueue;

Root←root of Grid-R tree

2: For each node N in Root Do

3: Queue←N intersect with W

4: If the Flag of N.Flag is false Then

5: Add all data that intersect with W to PointList;

6: Else

7: For each node I in N Do

8: If Level of I is 1 Then

9: Add all data that intersect with W to PointList;

10: Else

11: If I intersect with W Then

12: Goto (9);

13: Return PointList;

END

算法流程：

從三維網(wǎng)格-R樹根結(jié)點(diǎn)開始，依次循環(huán)所有的網(wǎng)格-R樹中間結(jié)點(diǎn)，將所有與區(qū)域查詢框所相交的外層網(wǎng)格結(jié)構(gòu)索引號(hào)返回并記錄下來添加至隊(duì)列中(第1～3行)。通過這一步驟，將與區(qū)域范圍不相交且無關(guān)的大量網(wǎng)格-R樹中間結(jié)點(diǎn)直接剪枝掉，其后各步驟均是在剪枝后的網(wǎng)格-R樹中間結(jié)點(diǎn)內(nèi)進(jìn)行查找。相比傳統(tǒng)R樹索引依次比較所有的中間結(jié)點(diǎn)的MBR信息，大大減少了無用結(jié)點(diǎn)的訪問率，并且在很大程度上減少了重疊空間的無用查找。在此基礎(chǔ)上，檢索出落在區(qū)域查詢范圍框內(nèi)的三維數(shù)據(jù)對(duì)象，并將其添加至結(jié)果集中(第7～13行)。

三維網(wǎng)格-R樹的優(yōu)點(diǎn)在于可以利用網(wǎng)格快速劃分空間區(qū)域的特點(diǎn)，將三維空間數(shù)據(jù)區(qū)域按照一定的規(guī)則高效劃分并組織起來，相比傳統(tǒng)單一的R樹索引，減少了大量不必要的中間結(jié)點(diǎn)的重疊。因此，基于三維網(wǎng)格-R樹的k近鄰查詢，可以充分利用三維網(wǎng)格-R樹的優(yōu)勢(shì)，結(jié)合空間分割的思想，以合理的方式對(duì)網(wǎng)格-R樹的中間結(jié)點(diǎn)進(jìn)行剪枝操作，有效提高了查詢的效率。

在索引的外層，網(wǎng)格中心結(jié)點(diǎn)代表了該網(wǎng)格中心點(diǎn)在空間區(qū)域內(nèi)的所在位置，也可以借助其完成快速的定位、判斷其離查詢點(diǎn)之間的距離。三維網(wǎng)格-R樹外層網(wǎng)格結(jié)構(gòu)每一中心結(jié)點(diǎn)的計(jì)算公式為

(4)

式中，pli代表了網(wǎng)格-R樹各個(gè)中間結(jié)點(diǎn)左前下邊界點(diǎn)的(x,y,z)值，pri則表示了右上后邊界點(diǎn)的(x，y，z)值。用d表示查詢點(diǎn)到網(wǎng)格-R樹外層結(jié)構(gòu)中心結(jié)點(diǎn)的距離，則它的計(jì)算公式為

(5)

通過上述距離計(jì)算，可以快速比較求得離查詢中心最近鄰的若干個(gè)網(wǎng)格子空間，將其依次添加至隊(duì)列中，并按照d值由小至大的順序?qū)㈥?duì)列排序。采用全局的思想，優(yōu)先選擇隊(duì)列中靠前的網(wǎng)格子空間。此時(shí)，那些距離查詢點(diǎn)較遠(yuǎn)的網(wǎng)格葉結(jié)點(diǎn)可以作為“無用結(jié)點(diǎn)”直接剔除掉。完成初步剪枝操作后，接下來，判斷在候選集的網(wǎng)格-R樹中間結(jié)點(diǎn)內(nèi)有無網(wǎng)格子R樹索引。若無，則直接按照候選集至查詢點(diǎn)的距離由小到大排序，直至選出k個(gè)候選項(xiàng)作為最終k近鄰查詢的結(jié)果；若有網(wǎng)格子R樹索引，則按照寬度優(yōu)先遍歷算法，從網(wǎng)格子R樹的根結(jié)點(diǎn)開始，依次以全局的思想選擇某一中間結(jié)點(diǎn)為候選項(xiàng)，遞歸的查詢每一中間結(jié)點(diǎn)的MBR，直至遍歷至R樹葉結(jié)點(diǎn)，最終得到k個(gè)最近鄰結(jié)果集。

利用上述算法思想，下面對(duì)基于網(wǎng)格-R樹的k近鄰查詢算法進(jìn)行了具體的描述，給出了算法執(zhí)行的步驟。

輸入：query center q, k, root of Grid-R tree

輸出：NearestList

BEGIN

1: queue←NewQueue();

2: NearestList←NewList(k);

3: Index←Search(q);

4: For each node N in Root do

5: Search the nearest N to Index;

6: Enqueue(queue，N);

7: Calculate each center point of N;

8: Prune queue with Distance;

9: Sort(queue);

10: For each node N in Node do

11: If(N is LeafNode) Then

12: Calculate each d(p,q) in N;

13: If ( d(p,q)

14: Insert(NearestList,p) ;

15: Update MINDIST(NearestList) with d(p,q) ;

16: Else

17: Goto (12);

18: Else

19: For each d(mbr,q) in N

20: If(d(mbr,q)

21: Resort each mbr of N;

22: For each node I of N

23: Goto (11);

24: Else

25: Goto (19);

26: Add nearest k to nearestList;

27: Return NearestList;

END

算法流程：

首先初始化一個(gè)優(yōu)先隊(duì)列用于存放當(dāng)前網(wǎng)格-R樹結(jié)點(diǎn)，并新建一個(gè)NearestList鏈表用于存放k個(gè)最近鄰候選集(第1～2行)。計(jì)算得到查詢點(diǎn)q所在的網(wǎng)格-R樹外層網(wǎng)格索引號(hào)(第3行)。將網(wǎng)格-R樹根結(jié)點(diǎn)中所有下一級(jí)中間結(jié)點(diǎn)取出，并將它們依次執(zhí)行入隊(duì)操作。接下來，利用式(4)計(jì)算其網(wǎng)格-R樹外層網(wǎng)格結(jié)構(gòu)的中心結(jié)點(diǎn)，并利用式(5)分別計(jì)算其網(wǎng)格-R樹結(jié)構(gòu)中心結(jié)點(diǎn)至查詢點(diǎn)之間的距離，并根據(jù)距離由近至遠(yuǎn)的順序?qū)﹃?duì)列進(jìn)行排序(第7～9行)。計(jì)算葉結(jié)點(diǎn)N下每一數(shù)據(jù)對(duì)象p至查詢點(diǎn)q的距離，并與當(dāng)前NearestList鏈表中的MINDIST值(初始為正無窮)作比較(第11～13行)。若小于這一距離值，則直接將該數(shù)據(jù)對(duì)象插入至候選集中，并用當(dāng)前的距離值來更新MINDIST值(第14～15行)。倘若N是網(wǎng)格-R樹的中間結(jié)點(diǎn)，而非葉子結(jié)點(diǎn)，則循環(huán)遍歷其子樹的每一MBR(第19～20行)，優(yōu)先選擇其子樹MBR至查詢點(diǎn)最近的中間結(jié)點(diǎn)開始遍歷(第21～23行)。同時(shí)計(jì)算q到其子樹MBR的距離，若大于此時(shí)的MINDIST值，則將當(dāng)前結(jié)點(diǎn)直接舍棄掉，轉(zhuǎn)而去遍歷查詢下一子樹的MBR。通過這一剪枝規(guī)則，大大減少了中間結(jié)點(diǎn)的迭代與距離計(jì)算工作量。最后，直至遍歷至所有網(wǎng)格-R樹葉子結(jié)點(diǎn)，選中k近鄰個(gè)候選項(xiàng)，并返回最后的結(jié)果集。

算法分析：

基于網(wǎng)格-R樹k近鄰查詢算法最大的優(yōu)勢(shì)在于利用網(wǎng)格將空間劃分后快速的定位查找。通過簡(jiǎn)單的計(jì)算可以將查詢中心定位至某一網(wǎng)格葉子結(jié)點(diǎn)內(nèi)，此時(shí)，要查詢的k近鄰對(duì)象一定位于該網(wǎng)格葉節(jié)點(diǎn)內(nèi)，或者是在位置上鄰近于該網(wǎng)格。快速定位到查詢點(diǎn)所在的網(wǎng)格索引號(hào)。假設(shè)在相同條件下的R樹索引結(jié)構(gòu)，要想確認(rèn)查詢點(diǎn)在結(jié)構(gòu)中的位置，可能需要查詢大量的重疊空間方可找到。在定位到的網(wǎng)格葉子結(jié)點(diǎn)內(nèi)，計(jì)算其所在網(wǎng)格與鄰近網(wǎng)格結(jié)點(diǎn)的中心結(jié)點(diǎn)，通過距離剪枝規(guī)則將剪枝后的結(jié)點(diǎn)按照距離查詢點(diǎn)的遠(yuǎn)近由近至遠(yuǎn)依次入隊(duì)排序，依次將查詢到的最近鄰更新至NearestList隊(duì)列。在減少了比較R樹大量中間重疊結(jié)點(diǎn)的同時(shí)，也減少了網(wǎng)格葉結(jié)點(diǎn)的重復(fù)比較，通過剪枝操作，達(dá)到了快速的檢索要求，同時(shí)保證了檢索的精度和準(zhǔn)確性。

索引本身就是利用空間換取時(shí)間效率，下面將介紹混合索引的時(shí)間復(fù)雜度分析。從整體上來看，利用R樹索引結(jié)構(gòu)查詢的時(shí)間復(fù)雜度為O(log2n)，而基于網(wǎng)格-R樹的索引結(jié)構(gòu)時(shí)間復(fù)雜度為1/2O(log2n)。網(wǎng)格索引在數(shù)據(jù)檢索上效率很高，只需要通過簡(jiǎn)單的地址運(yùn)算，就可以快速定位至三維數(shù)據(jù)對(duì)象所在的空間區(qū)域。但其內(nèi)部缺少高效的檢索機(jī)制，這在很大程度上限制了其索引性能?；谌S網(wǎng)格-R樹的混合索引對(duì)外層網(wǎng)格結(jié)點(diǎn)有選擇性的建立網(wǎng)格子空間R樹索引，大大提高了網(wǎng)格內(nèi)部檢索效率。經(jīng)過網(wǎng)格-R樹結(jié)構(gòu)的區(qū)域分塊劃分，相比傳統(tǒng)R樹，在某些層次上降低了樹的深度，無論在區(qū)域查詢還是k近鄰查詢中表現(xiàn)出的性能均得到了提升，并且將重構(gòu)的代價(jià)變小。傳統(tǒng)的R樹結(jié)構(gòu)在數(shù)據(jù)對(duì)象密度較大的區(qū)域，其MBR會(huì)出現(xiàn)大面積的重疊，導(dǎo)致查詢時(shí)相鄰的兄弟結(jié)點(diǎn)大量反復(fù)無用查找，冗余度較大，影響查詢效率。而經(jīng)過外層的網(wǎng)格-R樹空間劃分，密度較大的幾個(gè)空間區(qū)域得以分離，不再需要將所有的三維點(diǎn)元數(shù)據(jù)對(duì)象添加至一棵龐大的R樹結(jié)構(gòu)中，有效改善了結(jié)點(diǎn)冗余度，提高了索引效率，并且得到了實(shí)驗(yàn)驗(yàn)證。基于三維網(wǎng)格-R樹的混合索引結(jié)構(gòu)將一棵棵小而獨(dú)立分散的R樹以外層三維網(wǎng)格形式組織起來，以犧牲少量存儲(chǔ)空間為代價(jià)換取了更為高效的查詢效率。

5 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)環(huán)境為 Windows 7，64位操作系統(tǒng)，Intel Core i5-4590 CPU@3.30GHz，4 G內(nèi)存。使用 Visual Studio 2010開發(fā)平臺(tái)建立了三維網(wǎng)格-R樹混合索引結(jié)構(gòu)模型。

本文通過使用SpatialDataGenerator軟件來生成隨機(jī)的空間三維對(duì)象。分別采用5萬(wàn)數(shù)據(jù)集、20萬(wàn)數(shù)據(jù)集以及100萬(wàn)數(shù)據(jù)集進(jìn)行試驗(yàn)論證，并針對(duì)不同場(chǎng)景分布下的數(shù)據(jù)集進(jìn)行了測(cè)試，分別對(duì)各自進(jìn)行范圍查詢、k近鄰查詢的時(shí)間進(jìn)行了比較。實(shí)驗(yàn)中用到的參數(shù)范圍和默認(rèn)值如表1所示。

表1 空間索引查詢實(shí)驗(yàn)數(shù)據(jù)參數(shù)
Tab.1 Experimental parameters of spatial index query

數(shù)據(jù)參數(shù)范圍默認(rèn)值索引結(jié)構(gòu)R-tree,3D Grid-R tree3D Grid-R tree數(shù)據(jù)大小50 000,200 000,1 000 00050 000查詢半徑100,110,120,130100k值大小100,200,300,400100

在構(gòu)建好索引的基礎(chǔ)上，比較各個(gè)索引結(jié)構(gòu)的查詢性能。首先，在5萬(wàn)隨機(jī)均勻分布的數(shù)據(jù)集大小下，規(guī)定查詢半徑依次為100、110、120、130。為了排除實(shí)驗(yàn)當(dāng)中的偶然性，在世界域即0≤x<400，0≤y<400，0≤z<400內(nèi)隨機(jī)生成100組三維測(cè)試點(diǎn)，將生成的這100個(gè)參考點(diǎn)分別當(dāng)作范圍查詢的中心，并以此為循環(huán)依次進(jìn)行范圍查詢。如表2所示，分別表示了在兩種索引結(jié)構(gòu)下進(jìn)行100次范圍查詢的平均檢索時(shí)間。圖8給出在5萬(wàn)均勻分布數(shù)據(jù)集下R樹索引結(jié)構(gòu)和網(wǎng)格-R樹索引結(jié)構(gòu)在查詢半徑分別為100至130下的查詢時(shí)間。從圖8可以看出，網(wǎng)格-R樹的查詢時(shí)間明顯優(yōu)于傳統(tǒng)R樹。

表2 5萬(wàn)數(shù)據(jù)集大小下平均查詢時(shí)間(均勻分布)
Tab.2 Average query time under 50 000 dataset size (evenly distributed)

查詢半徑/mR樹查詢時(shí)間/s網(wǎng)格-R樹查詢時(shí)間/s1002.72.181103.092.191203.742.811304.213.62

圖8 范圍查詢時(shí)間對(duì)比圖(均勻分布)
Fig.8 Time comparison of range query (evenly distributed)

接下來觀察在5萬(wàn)服從高斯分布數(shù)據(jù)集下的實(shí)驗(yàn)，如表3和圖9所示。

表3 5萬(wàn)數(shù)據(jù)集大小下平均查詢時(shí)間(高斯分布)
Tab.3 Average query time under 50,000 dataset size (Gaussian distributed)

查詢半徑/mR樹查詢時(shí)間/s網(wǎng)格-R樹查詢時(shí)間/s1003.341.721103.912.491204.523.121305.333.77

圖9 范圍查詢時(shí)間對(duì)比圖(高斯分布)
Fig.9 Time comparison of range query (Gaussian distribution)

對(duì)比分析圖8和圖9，隨著范圍查詢搜索半徑逐漸的增大，落在查詢區(qū)域內(nèi)的三維點(diǎn)元對(duì)象的數(shù)量勢(shì)必增加，查詢的時(shí)間也相應(yīng)的各自增大。結(jié)合構(gòu)建索引性能綜合考慮，隨著查詢半徑的增大，三維網(wǎng)格-R樹查詢所需要的時(shí)間增長(zhǎng)勢(shì)頭要比R樹索引較慢，很好地詮釋了三維網(wǎng)格-R樹混合索引結(jié)構(gòu)在查詢方面的優(yōu)勢(shì)。適當(dāng)?shù)卦龃髷?shù)據(jù)集大小，選取20萬(wàn)隨機(jī)均勻分布與高斯分布的數(shù)據(jù)集，同樣選取查詢半徑分別為100至130，類似地選擇100個(gè)點(diǎn)當(dāng)作是范圍查詢的中心點(diǎn)，分別進(jìn)行范圍查詢。圖10給出在20萬(wàn)均勻分布數(shù)據(jù)集下R樹索引結(jié)構(gòu)和網(wǎng)格-R樹索引結(jié)構(gòu)在查詢半徑分別為100至130下的查詢時(shí)間。圖11給出在20萬(wàn)高斯分布數(shù)據(jù)集下R樹索引結(jié)構(gòu)和網(wǎng)格-R樹索引結(jié)構(gòu)在查詢半徑分別為100至130下的查詢時(shí)間。

從圖10、圖11中可以看出，與5萬(wàn)數(shù)據(jù)集大小下的實(shí)驗(yàn)結(jié)果一致，三維網(wǎng)格-R樹的查詢時(shí)間要小于傳統(tǒng)R樹，同時(shí)增長(zhǎng)的速度并不是很大。實(shí)驗(yàn)中20萬(wàn)服從高斯分布的數(shù)據(jù)集，即模擬了三維現(xiàn)實(shí)中那些分布不均勻，部分空間數(shù)據(jù)特別密集的情景，圖11顯示了在這種數(shù)據(jù)集極端分布不均勻情況下三維網(wǎng)格-R樹相比傳統(tǒng)R樹的查詢更為快速的優(yōu)勢(shì)。同時(shí)可以看出，在模擬數(shù)據(jù)分布不均勻的高斯分布下，三維網(wǎng)格-R樹比傳統(tǒng)R樹節(jié)省的時(shí)間要優(yōu)于數(shù)據(jù)在隨機(jī)均勻下分布下的時(shí)間，同時(shí)大大優(yōu)于5萬(wàn)數(shù)據(jù)集下的時(shí)間?？梢?，在數(shù)據(jù)量增大的情景下，三維網(wǎng)格-R樹對(duì)于查詢效率的優(yōu)化要更為出色。

圖10 范圍查詢時(shí)間對(duì)比圖(均勻分布)
Fig.10 Time comparison of range query (evenly distributed)

圖11 范圍查詢時(shí)間對(duì)比圖(高斯分布)
Fig.11 Time comparison of range query (Gaussian distribution)

基于上述的分析，為了證明在數(shù)據(jù)量更為巨大的情況下三維網(wǎng)格-R樹良好的查詢性能，接下來繼續(xù)增大數(shù)據(jù)集。圖12，圖13給出數(shù)據(jù)集大小增大至100萬(wàn)時(shí)，在隨機(jī)均勻分布和在高斯分布下100次范圍查詢操作的平均查詢時(shí)間。從圖中不難看出，三維網(wǎng)格-R樹相比傳統(tǒng)R-樹繼續(xù)保持著更好的查詢性能，并且隨著數(shù)據(jù)量以及查詢范圍的增大，網(wǎng)格-R樹的優(yōu)勢(shì)顯得更為突出，滿足預(yù)期的假設(shè)。

圖12 范圍查詢時(shí)間對(duì)比圖(均勻分布)
Fig.12 Time comparison of range query (evenly distributed)

圖13 范圍查詢時(shí)間對(duì)比圖(高斯分布)
Fig.13 Time comparison of range query (Gaussian distribution)

在對(duì)不同索引結(jié)構(gòu)下的區(qū)域范圍查詢做了對(duì)比實(shí)驗(yàn)的基礎(chǔ)上，接下來選取不同的參數(shù)變量，來對(duì)實(shí)驗(yàn)測(cè)試數(shù)據(jù)集下不同索引結(jié)構(gòu)的k近鄰查詢進(jìn)行對(duì)比分析。

表4為默認(rèn)參數(shù)為5萬(wàn)高斯均勻分布數(shù)據(jù)集下的不同索引結(jié)構(gòu)k近鄰查詢時(shí)間。其中分別設(shè)定k近鄰查詢中的k值范圍為100～400。

表4 不同k值大小下k近鄰查詢時(shí)間
Tab.4k-nearest neighbor query time with differentk-values

k值R樹查詢時(shí)間/s網(wǎng)格-R樹查詢時(shí)間/s10052.1146.0220078.4871.53300102.68100.03400124.1121.3

隨著k值不斷的增大，不同索引結(jié)構(gòu)下k近鄰查詢的時(shí)間均有所上升,如圖14所示。這是因?yàn)殡S著查找對(duì)象個(gè)數(shù)的上升，需要比對(duì)與距離的計(jì)算增加，故時(shí)間有所增長(zhǎng)。但無論在哪一種k值要求下，本文提出的三維網(wǎng)格-R樹索引總比傳統(tǒng)R樹索引的查詢時(shí)間要短，可見其性能優(yōu)勢(shì)。

圖14k近鄰查詢對(duì)比圖
Fig.14 Time comparison ofknearest neighbor query

接下來將k值固定不變，設(shè)定其為100。比較在不同數(shù)據(jù)集大小下分別進(jìn)行k近鄰查詢不同索引結(jié)構(gòu)的性能優(yōu)勢(shì),如表5所示。為了更好地驗(yàn)證之前的假設(shè)，所選數(shù)據(jù)集均滿足三維場(chǎng)景下的高斯分布。

在不同測(cè)試數(shù)據(jù)集大小下，三維網(wǎng)格-R樹索引在k近鄰查詢中的效率都要優(yōu)于傳統(tǒng)R樹索引。且隨著數(shù)據(jù)集數(shù)量的增大，三維網(wǎng)格-R樹所凸顯出的查詢性能更為出色，相比傳統(tǒng)的R樹索引，在k近鄰查詢中可以提高約1/3的索引性能。

表5 不同數(shù)據(jù)集大小下k近鄰查詢時(shí)間(k=100)
Tab.5k-nearest neighbor query time for different dataset sizes(k=100)

數(shù)據(jù)集大小R樹查詢時(shí)間/s網(wǎng)格-R樹查詢時(shí)間/s50 00052.1146.02200 000107.34100.621 000 000999.62679.5

6 結(jié)論

本文針對(duì)三維空間數(shù)據(jù)具有數(shù)據(jù)量大、對(duì)象之間關(guān)系復(fù)雜，同時(shí)某些特定場(chǎng)景下，對(duì)象分布呈現(xiàn)區(qū)域密集集中的問題，提出的三維網(wǎng)格-R樹混合索引結(jié)構(gòu)，在快速管理大規(guī)模數(shù)據(jù)的同時(shí)可以達(dá)到較高的查詢效率。

在相同數(shù)據(jù)集大小下，本文提出的三維網(wǎng)格-R樹索引結(jié)構(gòu)查詢的效率要高于傳統(tǒng)R樹，同時(shí)在數(shù)據(jù)集大小極具增長(zhǎng)的情況下，查詢的性能也要優(yōu)于傳統(tǒng)R樹索引結(jié)構(gòu)。在不同范圍內(nèi)的區(qū)域查詢、不同k值下的k近鄰查詢，利用本文提出的索引結(jié)構(gòu)均可達(dá)到良好的性能且優(yōu)于傳統(tǒng)R樹。由于三維網(wǎng)格-R樹索引結(jié)構(gòu)具備較好的靈活性，使其可以使用于不同數(shù)據(jù)集分布的場(chǎng)景問題研究中，無論是服從正態(tài)分布還是均勻分布的實(shí)際問題，均有著良好的應(yīng)用價(jià)值。

本文所提出的方法還有諸多局限性。為此，今后可以考慮系統(tǒng)自動(dòng)根據(jù)空間內(nèi)三維對(duì)象數(shù)據(jù)集大小及其分布情況選擇最佳的網(wǎng)格-R樹閾值劃分大小。此外，可以考慮將R*樹索引結(jié)構(gòu)的核心思想引入進(jìn)來，形成更為高效的空間索引結(jié)構(gòu)。