一種改進(jìn)的R-樹(shù)節(jié)點(diǎn)分裂優(yōu)化算法

摘? 要：對(duì)R-樹(shù)空間索引查詢效率低下的問(wèn)題，提出一種改進(jìn)的PSR-樹(shù)索引方法。PSR-樹(shù)使用貪心算法找到要分裂的節(jié)點(diǎn)中對(duì)應(yīng)的MBR的最小邊界值，在最小邊界值和非最小邊界值中分別隨機(jī)選擇一個(gè)邊界對(duì)象，用選擇得到的這兩個(gè)對(duì)象為分裂后兩個(gè)新增節(jié)點(diǎn)首選空間數(shù)據(jù)對(duì)象進(jìn)行分裂操作，建立好PSR-樹(shù)后并寫(xiě)入節(jié)點(diǎn)。實(shí)驗(yàn)表明，PSR-樹(shù)可以有效地減少節(jié)點(diǎn)中最小外接矩形的重疊面積，時(shí)間響應(yīng)上比已有的R-樹(shù)索引快，PSR-樹(shù)從上述兩個(gè)方面提高了查詢效率。

關(guān)鍵詞：R-樹(shù);最小外接矩形;節(jié)點(diǎn)分裂;最小邊界值

中圖分類號(hào)：TP391;TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）22-0086-06

An Improved R-tree Node Splitting Optimization Algorithm

HE Jianying

（School of Intelligent Manufacturing，Sichuan University of Arts and Science，Dazhou? 635000，China）

Abstract：To solve the problem of low efficiency of R-tree space index query，an improved PSR-tree index method is proposed. The PSR-tree uses a greedy algorithm to find the minimum boundary value of the corresponding MBR in the node to be split. A boundary object is randomly selected from the minimum boundary value and the non-minimum boundary value，use the selected two objects to perform the split operation for the two newly-added node preferred spatial data objects after splitting，and then write the node after the PSR-tree is established. The experiment shows that PSR-tree can effectively reduce the overlap area of the MBR in the node，and the time response is faster than the existing R-tree index，PSR-tree improves the query efficiency from these two aspects.

Keywords：R-tree;MBR;node splitting;minimum boundary value

0? 引? 言

在大數(shù)據(jù)、云計(jì)算等相關(guān)技術(shù)的推動(dòng)下，空間數(shù)據(jù)、多維數(shù)據(jù)等詞相繼出現(xiàn)在人們的視野中，它們主要用來(lái)描述與位置有關(guān)的地理信息。但隨著技術(shù)的不斷進(jìn)步，對(duì)非位置點(diǎn)數(shù)據(jù)也可以使用空間數(shù)據(jù)和多維數(shù)據(jù)等來(lái)描述。如對(duì)于學(xué)生基本信息表，其存儲(chǔ)信息字段包括姓名、性別、年齡、出生日期、家庭住址、身份證號(hào)。這里可將該表視為6維空間中的點(diǎn)，每一維度分別對(duì)應(yīng)某一屬性。盡管各維的類型不盡相同，如姓名、家庭住址和身份證號(hào)是字符串類型，性別為比特型，年齡是數(shù)字類型，出生年月是日期型。其實(shí)對(duì)于家庭住址可以按定位的經(jīng)緯度坐標(biāo)，理解為空間位置?？臻g數(shù)據(jù)的存在則需建立與之對(duì)應(yīng)的索引結(jié)構(gòu)來(lái)方便空間數(shù)據(jù)的訪問(wèn)。

空間索引是提高空間數(shù)據(jù)訪問(wèn)性能的關(guān)鍵技術(shù)。目前的空間索引技術(shù)主要有基于二叉樹(shù)、B-樹(shù)、哈希以及空間填充曲線的索引等[1]。R-樹(shù)就是B-樹(shù)的一種擴(kuò)展，在當(dāng)前的空間數(shù)據(jù)索引領(lǐng)域中已得到了廣泛的應(yīng)用。R-樹(shù)及其變體均是允許節(jié)點(diǎn)相互重疊的平衡樹(shù)。R-樹(shù)構(gòu)建的好壞決定了訪問(wèn)R-樹(shù)時(shí)效率的高低，而構(gòu)建R-樹(shù)的關(guān)鍵在于節(jié)點(diǎn)的插入與分裂。已有的研究表明R-樹(shù)的構(gòu)建實(shí)際上可以看成是一個(gè)聚類問(wèn)題，可通過(guò)聚類算法及相應(yīng)的分裂算法有效地降低R-樹(shù)節(jié)點(diǎn)的重疊[2-4]。且在插入節(jié)點(diǎn)時(shí)，對(duì)子樹(shù)的選擇和節(jié)點(diǎn)的分裂等過(guò)程中，均是基于“使節(jié)點(diǎn)的最小外接矩形（Minimum Bounding Rectangle，MBR）的增量最小，則MBR的重疊區(qū)域最少”這一基本原則進(jìn)行探討研究的。

本文是在項(xiàng)目“大數(shù)據(jù)下R-樹(shù)在高維數(shù)據(jù)去重中的應(yīng)用研究”的研究成果之一，作者在文獻(xiàn)[5]研究的“SR-樹(shù)節(jié)點(diǎn)分裂優(yōu)化算法”的基礎(chǔ)上對(duì)R-樹(shù)的搜索算法進(jìn)行改進(jìn)，提出一種改進(jìn)的PSR-樹(shù)空間索引方法，該方法的節(jié)點(diǎn)分裂優(yōu)化算法是基于使R-樹(shù)的MBR體積最小的原則，采用最小邊界算法，找到MBR中的任意兩個(gè)邊界對(duì)象，以它們?yōu)榉至押蟮膬蓚€(gè)新節(jié)點(diǎn)的首選空間對(duì)象進(jìn)行分裂節(jié)點(diǎn)的操作，最后把構(gòu)建好的R-樹(shù)存儲(chǔ)在存儲(chǔ)設(shè)備上。這樣既增加了葉子節(jié)點(diǎn)的聚類性，又減少了葉節(jié)點(diǎn)的最小MBR的面積之和，從而提高了查詢的性能。

1? 相關(guān)工作

節(jié)點(diǎn)分裂是在構(gòu)建R-樹(shù)過(guò)程中，當(dāng)插入數(shù)據(jù)對(duì)象的某一目標(biāo)節(jié)點(diǎn)P已滿，插入后節(jié)點(diǎn)數(shù)變M+1（M為節(jié)點(diǎn)所能容納的最大節(jié)點(diǎn)數(shù)），此時(shí)數(shù)據(jù)集合將產(chǎn)生益出（overflow），那么需要對(duì)該節(jié)點(diǎn)P進(jìn)行一分為二的操作，盡可能平均地把M+1個(gè)關(guān)鍵碼分到兩個(gè)子集中，并將某一中值關(guān)鍵碼middleVlaue轉(zhuǎn)交到父節(jié)點(diǎn)的pre_p中，對(duì)父節(jié)點(diǎn)pre_p使用同樣的方法遞歸處理，直到?jīng)]有節(jié)點(diǎn)需要分裂為止。若達(dá)到根節(jié)點(diǎn)也需要進(jìn)行分裂操作，那么將增加一個(gè)根節(jié)點(diǎn)，樹(shù)的高度增加一層。

R-樹(shù)插入節(jié)點(diǎn)的過(guò)程大致為：查找到包含所需插入空間范圍的MBR，找到將要插入數(shù)據(jù)對(duì)象所對(duì)應(yīng)的節(jié)點(diǎn)，查看該節(jié)點(diǎn)是否已經(jīng)包含了M個(gè)節(jié)點(diǎn)，如果是，則需要進(jìn)行分裂操作。分裂后，兩個(gè)MBR的面積之和要比原來(lái)的MBR的面積小。如果要插入節(jié)點(diǎn)的MBR有多個(gè)，則選擇MBR最小的那個(gè)插入，如果沒(méi)有最小的，那么遍歷選擇加入所需插入節(jié)點(diǎn)后MBR面積變化最小的那個(gè)MBR插入。

前人已經(jīng)研究了針對(duì)R-樹(shù)節(jié)點(diǎn)分裂的平方代價(jià)算法（Quadratic-Cost Algorithm）、窮舉算法（Exhaustive Al-gorithm）、線性代價(jià)算法（Linear-Cost Algorithm）等[6]。Guttman平方代價(jià)算法在時(shí)間上從窮舉法的O（2M）降低到了O（M2），時(shí)間復(fù)雜度有了較大的改進(jìn)，但當(dāng)數(shù)據(jù)對(duì)象較多時(shí)，平方代價(jià)算法執(zhí)行分裂操作仍需要較長(zhǎng)的時(shí)間，且不能保證分裂后的MBR的面積之和是最小的。而線性代價(jià)算法比較粗糙，雖然耗時(shí)少，但查詢效率仍很低下。文獻(xiàn)[5]在Guttman平方代價(jià)算法的啟發(fā)下提出了SR-樹(shù)節(jié)點(diǎn)分裂優(yōu)化算法。其具體執(zhí)行過(guò)程為：

（1）對(duì)需要分裂的節(jié)點(diǎn)隨機(jī)選擇兩個(gè)種子R1和R2，保證R1，R2的MBR的空白面積都比其余的Ri大，分別以R1和R2作為新節(jié)點(diǎn)創(chuàng)建新的MBR。

（2）計(jì)算每次有Ri加入到兩個(gè)新節(jié)點(diǎn)時(shí)，增加面積最小的那個(gè)節(jié)點(diǎn)，將Ri添加到該節(jié)點(diǎn)中，對(duì)每個(gè)Ri均遞歸調(diào)用此方法，直至把每個(gè)記錄都添加到相應(yīng)的節(jié)點(diǎn)集合中。

該算法在構(gòu)建好R-樹(shù)后，對(duì)其進(jìn)行遍歷查詢時(shí)，減少了多路查詢問(wèn)題，同時(shí)在減少葉子節(jié)點(diǎn)的最小外接矩形的面積方面也取得了一定的成效。

2? 空間數(shù)據(jù)索引設(shè)計(jì)

2.1? 相關(guān)概念及定義

本節(jié)中直接給出R-樹(shù)、空間數(shù)據(jù)距離函數(shù)、空間數(shù)據(jù)節(jié)點(diǎn)收益及最小邊界等的相關(guān)概念。[7-10]

定義1：R-樹(shù)是B-樹(shù)的擴(kuò)展，其包含兩類節(jié)點(diǎn)：葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)。設(shè)一棵度為m的R-樹(shù)，其必定滿足以下幾點(diǎn)：

（1）除非葉節(jié)點(diǎn)是根結(jié)點(diǎn)，否則葉子結(jié)點(diǎn)中所包含的數(shù)據(jù)記錄數(shù)在[m，2m];

（2）所有葉節(jié)點(diǎn)均處在同一層，是一棵結(jié)構(gòu)平衡的樹(shù);

（3）根節(jié)點(diǎn)除外，其余的子節(jié)點(diǎn)包含[m，2m]個(gè)子節(jié)點(diǎn);

定義2：設(shè)S類中的數(shù)據(jù){s1，s2，…，sn}包含n個(gè)數(shù)據(jù)，則該類的第t個(gè)屬性的均值點(diǎn)ct用屬性的k個(gè)相關(guān)值描述可表示為：

定義3：設(shè){s1，s2，…，sn}是n個(gè)d維上的空間數(shù)據(jù)集

合，設(shè)cj含有m個(gè)空間數(shù)據(jù)對(duì)象，則si與cj的距離函數(shù)為：

其中，i∈[1，n]，j∈[1，m]。

定義4：設(shè){s1，s2，…，sm}是包含m個(gè)空間數(shù)據(jù)的集合，則該類的均值點(diǎn)c為：

其中，，d∈[1，m]，t∈[1，d]。

定義5：給定MBR矩形的長(zhǎng)寬分別為w和h，設(shè)矩形的質(zhì)量定義為Q（mr），s1節(jié)點(diǎn)所構(gòu)成的最小外接矩形MBR的面積為mr1，刪除某一數(shù)據(jù)后，矩形面積值為mr2，則該節(jié)點(diǎn)的收益為G（mr1，mr2），則Q（mr）和G（mr1，mr2）分別為：

定義6：設(shè){s1，s2，…，sn}是空間數(shù)據(jù)集合，P是任意一數(shù)字，集合的P-邊界值是空間數(shù)據(jù)集合的子集。即P? {s1，s2，…，sn}。

定義7：設(shè){s1，s2，…，sn}是空間數(shù)據(jù)集合、任意一數(shù)字P及常量γ，設(shè)數(shù)據(jù)集合M的P-最小邊界是由最小數(shù)量的對(duì)象組成的子集N。即滿足：G（M，M-N）≥γ·G（M，M-P），其中γ∈[0，1]。

定義8：設(shè){s1，s2，…，sn}數(shù)據(jù)集合的MBR邊界MB，在空間數(shù)據(jù)集合中，層表示距離邊界MB相等的數(shù)據(jù)對(duì)象的集合。

2.2? 改進(jìn)的R-樹(shù)節(jié)點(diǎn)分裂優(yōu)化PSR算法

根據(jù)第1節(jié)中描述節(jié)點(diǎn)分裂的原因和已有的分裂算法，結(jié)合MBR邊界的思想。本文提出一種基于最小邊界的節(jié)點(diǎn)分裂算法（P-border split R-tree，PSR）。其具體過(guò)程為：

算法1? PSR（leafnode， obj） /*PSR節(jié)點(diǎn)分裂算法*/

輸入：等待插入的數(shù)據(jù)項(xiàng)obj，要插入的葉子節(jié)點(diǎn)leafnode;

輸出：分裂后的葉節(jié)點(diǎn);

（1）? if（leafnode.length

（2）? ? leafnode.add（obj）;

（3）? ? return leafnode;

（4）? else p←p_border（s，p，m）;? /*此時(shí)對(duì)節(jié)點(diǎn)進(jìn)行分裂操作，調(diào)用p_border（s，p，m）邊界算法取出數(shù)據(jù)集合的最小邊界值*/

（5）? ? p1_value=p.random（）;? ?/*從最小邊界中隨機(jī)取一個(gè)值*/

（6）? ? p2_value=p.random（s-p）; /*從非最小邊界中隨機(jī)取一個(gè)值存入p2_value*/

（7）? ? c1←?;

（8）? ? c2←?;

（9）? ?while pi_value ci? do {? /*i=1，2*/

（10）? ? ? ? ? ? /*求數(shù)據(jù)集合si中，與pj_value距離最小的數(shù)據(jù)項(xiàng)si，其中i∈[1，n]，j∈[1，M]*/

（11）? ? if d（si，pj_value）=min{d（sk，pj_value）}{ /*k∈[1，M]*/

（12）? ? ? leafnodei.add（si）;

（13）? ? ? wi←leafnode-leafnodei;

（14）? ? ? pi_value←ci;

（15）? ? ? pi_value←? ?/*重新計(jì)算質(zhì)心并賦值給pi_value， i∈[1，2]*/

（16）? ? }end if

（17）? ?}

（18）? ?return leafnodei;

（19） }end if

在算法1中，首先判斷葉節(jié)點(diǎn)所包含數(shù)據(jù)項(xiàng)的個(gè)數(shù)leafnode.length，如果leafnode.length小于節(jié)點(diǎn)能夠容納的最大數(shù)據(jù)項(xiàng)的個(gè)數(shù)，則直接把該數(shù)據(jù)項(xiàng)插入到該葉節(jié)點(diǎn)中。否則，leafnode.length大于等于葉節(jié)點(diǎn)能容納的最大個(gè)數(shù)，則需要進(jìn)行分裂操作，把一個(gè)葉節(jié)點(diǎn)分裂成兩個(gè)葉節(jié)點(diǎn)返回，見(jiàn)行4到行16。分裂過(guò)程中，首先使用最小邊界算法p_border（s，p），找到該葉節(jié)點(diǎn)的所有數(shù)據(jù)集合s中的P-邊界最小值的集合，然后再隨機(jī)找出兩個(gè)不同的邊界值分別存放在p1_value和p2_value中作為參照對(duì)象。再對(duì)剩下的數(shù)據(jù)項(xiàng)求使得d（si，pj_value）最小的數(shù)據(jù)項(xiàng)si，并將si劃分到以pi_value為質(zhì)心的集合中去，并重新計(jì)算新集合的質(zhì)心，若兩次的質(zhì)心值相同，則認(rèn)為已經(jīng)使得集合最優(yōu)，不需要進(jìn)行集合的劃分，此時(shí)循環(huán)結(jié)束。18行將返回分裂后的兩個(gè)節(jié)點(diǎn)。兩個(gè)節(jié)點(diǎn)劃分的有優(yōu)劣取決于最小邊界值得選擇，故在算法2中，使用貪心算法實(shí)現(xiàn)了P-最小邊界值算法，其具體過(guò)程算法過(guò)程為：

算法2? p_border（D，p，m） /*P_最小邊界值算法*/

輸入：空間數(shù)據(jù)對(duì)象集合D，p及m的值;

輸出：P-邊界的值（集合）;

（1）? ?recive_D_struct（D）;? /*獲得D的結(jié)構(gòu)*/

（2）? ?M←recive_ D _mbr（D） /*取D的MBR存入M*/

（3）? ?P←?;? ? ?/*初始化存放邊界值得集合*/

（4）? ?flag=true;

（5）? while? （flag）? do{

（6）? ? gmax=0;? ? ? ? /*設(shè)收益的最大初值為0*/

（7）? ? MBmax=LEFT;? /*設(shè)置邊界值的初始值*/

（8）? ? Layermax=0;

（9）? ? MB←receive_border（M）;? ? /*取得M中的每個(gè)邊界值存放在集合MB中*/

（10）? ? while （MB） do{? ? ? ? ? ?/*遍歷M中的每個(gè)邊界值*/

（11）? ? ? for（i=1;i m;i++）{? ? ? /*遍歷MB中邊界對(duì)象的每一層*/

（12）? ? ?if（MB[j]）.layer[i]==0 && MB[j]）.layer[i].

size+|P|>p）? ?/*邊界中包含i層上的數(shù)據(jù)對(duì)象，且i層上包含的對(duì)象與最小邊界的和不大于輸入的參數(shù)p時(shí)*/

（13）? ? border_split（MB[j].layer[i]）;? /*從邊界中分裂第i層*/

（14）? ? ? ? ? ? /*d為i層上的對(duì)象數(shù)，每移除第i層上的數(shù)據(jù)對(duì)象時(shí)的平均收益*/

（15）? ? ? ? ? if? （g>gmax）? then{

（16）? ? ? ? ? ? gmax=g;

（17）? ? ? ? ? ? MBmax=MB[i];

（18）? ? ? ? ? ? Layermax=i;

（19）? ? ? ? ? }end if

（20）? ? ? ?}end for

（21）? ? ?}end while

（6）? ? if? （gmax==0） then{

（22）? ? ? flag=false;

（23）? ?}end if

（24）? ?p←border_split（MBmax，Layermax）;? /*從邊界中分裂指定層的對(duì)象，把分裂后的集合存入p*/

（25）? ?MB←MB-p;? ?/*把分裂后的對(duì)象移除后，形成新的MBR矩形*/

（26）? }end while

（27） return P;

（28） }

在算法2中，對(duì)空間數(shù)據(jù)對(duì)象集合D及任意的p及m的值，使用貪心算法輸出P-邊界的值。行1到行4是初始化操作，行5到行26是對(duì)空間數(shù)據(jù)對(duì)象集合D組成的MBR矩形找到最小的邊界值并放到集合P中。27行是返回P的集合作為P-最小邊界值。

2.3? 存儲(chǔ)設(shè)計(jì)

通常建立的PSR-樹(shù)會(huì)存于內(nèi)存中，但隨著大數(shù)據(jù)時(shí)代的到來(lái)，空間數(shù)據(jù)量也變得十分巨大，一旦存放于內(nèi)存中的PSR-樹(shù)消失，重新建立PSR-樹(shù)要花費(fèi)較長(zhǎng)的時(shí)間。因此一般都會(huì)把建好的空間索引結(jié)構(gòu)寫(xiě)入磁盤(pán)文件中進(jìn)行存儲(chǔ)。本文根據(jù)文件存儲(chǔ)的相關(guān)特性，使用字節(jié)數(shù)組的方式對(duì)空間數(shù)據(jù)索引結(jié)構(gòu)進(jìn)行存儲(chǔ)[6]。在PSR-樹(shù)的文件存儲(chǔ)中主要包含兩類信息：樹(shù)的信息和節(jié)點(diǎn)信息;葉節(jié)點(diǎn)中具體存放的是空間數(shù)據(jù)對(duì)象。可通過(guò)存儲(chǔ)空間數(shù)據(jù)對(duì)象對(duì)于的ID標(biāo)識(shí)。具體的存儲(chǔ)過(guò)程為：

算法3? PSR_to_Storage_by_Byte（）

輸入：樹(shù)信息treeMess，樹(shù)的根節(jié)點(diǎn)node;

輸出：構(gòu)建好的整棵PSR-樹(shù)信息的字節(jié)數(shù)組;

（1）? B←new Byte（）;/*構(gòu)建存放樹(shù)信息的字節(jié)數(shù)組*/

（2）? size←write_Tree_Message_to_File（B， treeMess）; /*把樹(shù)信息寫(xiě)入文件中，并返回樹(shù)信息所占的字節(jié)數(shù)長(zhǎng)度*/

（3）? BB←node_storage_to_Byte（node，size）{

（4）? ? ? tmepB←new Byte（）;? ?/*構(gòu)建存放節(jié)點(diǎn)信息的字節(jié)數(shù)組*/

（5）? ? ?if node.level==0 then{? /*是葉節(jié)點(diǎn)*/

（6）? ? ? ?tempB.append（1）;

（7）? ? ?else? tempB.append（0）;

（8）? ? ?}end if

（9）? ? ?tempB.append（node.layer）;? ? /*添加節(jié)點(diǎn)的層次*/

（10）? ? ?tempB.append（node.targer.length）;? ? /*添加節(jié)點(diǎn)中所含實(shí)例項(xiàng)個(gè)數(shù)*/

（11）? ? ?data_list←recive_node_obj（node）;? ? /*獲得node節(jié)點(diǎn)的索引項(xiàng)數(shù)據(jù)*/

（12）? ? ?foreach data_list do{? ? ? ? ? ?/*對(duì)node節(jié)點(diǎn)的索引項(xiàng)數(shù)據(jù)進(jìn)行遍歷*/

（13）? ? ? if（datalist[i].pointer==true） then {? ? /*該數(shù)據(jù)項(xiàng)有指向的子節(jié)點(diǎn)*/

（14）? ? ?otherB←node_storage_to_Byte（datalist[i]，size）;/*遞歸添加節(jié)點(diǎn)信息*/

（15）? ? ? ? tempB.append（size，otherB）;

（16）? ? ? ? size=size+otherB.length（）;

（17）? ? ? }else tempB.append（0）;{

（18）? ? ? ? ? tempB.append（node.ID）;

（19）? ? ? }end if

（20）? ?}end for

（21）? }

（22）? return B+BB

（23） }

該方法首先在內(nèi)存中建立好索引樹(shù)，然后在字節(jié)數(shù)組中先存入樹(shù)的信息，包括樹(shù)的高度、大小、空間數(shù)據(jù)維數(shù)、樹(shù)節(jié)點(diǎn)能容納的最大子節(jié)點(diǎn)數(shù)、最小子節(jié)點(diǎn)數(shù)、樹(shù)信息存儲(chǔ)后的節(jié)點(diǎn)偏移量等。然后把樹(shù)的根節(jié)點(diǎn)作為第一個(gè)存入的節(jié)點(diǎn)，通過(guò)遞歸的方式把根節(jié)點(diǎn)下面的子節(jié)點(diǎn)依次存入字節(jié)數(shù)組中，直至葉子節(jié)點(diǎn)。

讀取和訪問(wèn)樹(shù)索引的過(guò)程較為簡(jiǎn)單，從文件頭開(kāi)始訪問(wèn)，根據(jù)根節(jié)點(diǎn)的偏移量找到根節(jié)點(diǎn)的位置，然后逐層訪問(wèn)。本過(guò)程采用字節(jié)數(shù)組的方式存儲(chǔ)整個(gè)PSR-樹(shù)，但對(duì)整個(gè)字節(jié)數(shù)組進(jìn)行整體讀寫(xiě)時(shí)，所花費(fèi)發(fā)時(shí)間較長(zhǎng)，且一次性地把整個(gè)字節(jié)數(shù)組讀入內(nèi)存，對(duì)內(nèi)存的占有也較大。而對(duì)于一個(gè)高度為m的PSR-樹(shù)，每次最多訪問(wèn)的節(jié)點(diǎn)個(gè)數(shù)為m，而不需要對(duì)整個(gè)樹(shù)的節(jié)點(diǎn)一一進(jìn)行訪問(wèn)。根據(jù)文獻(xiàn)[6]可知，把每個(gè)節(jié)點(diǎn)的大小設(shè)置為一個(gè)磁盤(pán)存儲(chǔ)頁(yè)的大小，這樣對(duì)節(jié)點(diǎn)的訪問(wèn)只需要一次讀寫(xiě)操作就可以完成，有效提高了索引的效率。

3? 實(shí)驗(yàn)及結(jié)果分析

索引算法的好壞，主要是看所構(gòu)建的空間索引樹(shù)中葉子節(jié)點(diǎn)的最小外接矩形的重疊面積的大小及查詢時(shí)間消耗的多少來(lái)做判斷：最小外接矩形的重疊面積越小，算法越優(yōu);查詢所耗費(fèi)的時(shí)間越短，算法越優(yōu)。本文設(shè)計(jì)的實(shí)驗(yàn)有兩個(gè)：一是比較不同的構(gòu)建樹(shù)的算法中最小外接矩形的重疊面積大小的比較;二是在不同算法中訪問(wèn)索引的時(shí)間消耗的對(duì)比。

本文所涉及的實(shí)驗(yàn)相關(guān)代碼均使用Java語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)中所采用的數(shù)據(jù)集選取了文獻(xiàn)[11]中所使用的Febrl數(shù)據(jù)集的數(shù)據(jù)生成器，人工生成了實(shí)驗(yàn)中所使用的實(shí)驗(yàn)數(shù)據(jù)。數(shù)據(jù)集中的信息包括姓名、性別、年齡、出生年月、家庭住址、身份證號(hào)、國(guó)籍等15項(xiàng)數(shù)據(jù)信息。在實(shí)驗(yàn)中，選取4維（4D）、8維（8D）、10維（10D）、12維（12D）4個(gè)不

同維度的各50萬(wàn)條數(shù)據(jù)，分別使用R-樹(shù)、SR-樹(shù)及PSR-樹(shù)的算法建立空間結(jié)構(gòu)索引樹(shù)。在數(shù)據(jù)量從10到50萬(wàn)條，以10萬(wàn)條的數(shù)據(jù)遞增時(shí)，數(shù)據(jù)所覆蓋的區(qū)域面積也在增加，因數(shù)據(jù)集中的數(shù)據(jù)來(lái)源是隨機(jī)的，故區(qū)域面積的增加不一定與數(shù)據(jù)量的增加成正比，其結(jié)果如圖1到圖4所示。

從圖1到圖4可以看出，當(dāng)數(shù)據(jù)量成倍增長(zhǎng)的情況下，MBR重疊面積區(qū)域并沒(méi)有成倍的增長(zhǎng)。在4維數(shù)據(jù)中，設(shè)置R-樹(shù)算法下構(gòu)建樹(shù)產(chǎn)生的MBR重疊面積的參照值為1，SR-樹(shù)所得到的MBR重疊面積是R-樹(shù)MBR重疊面積的76%左右，而PSR-樹(shù)的MBR重疊面積是SR-樹(shù)重疊面積的87.6%，重疊面積小了近12.4%。隨著維數(shù)和數(shù)據(jù)量的遞增，MBR重疊面積增長(zhǎng)的情況如圖5所示。

從圖5中可以看出，同等的數(shù)據(jù)增長(zhǎng)量情況下，在4D到10D時(shí)，隨著維度的提升，不同方法構(gòu)建樹(shù)的MBR重疊區(qū)域面積均明顯下降，但當(dāng)維數(shù)達(dá)到12D時(shí)，MBR重疊區(qū)域面積的變化不太明顯，這是高維數(shù)據(jù)的稀疏性的原因，在建立MBR時(shí)已越來(lái)越緊湊。

對(duì)3種算法在不同查詢區(qū)域中，對(duì)不同算法的響應(yīng)時(shí)間進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖6所示。

從圖6可以看出，PSR-樹(shù)的時(shí)間響應(yīng)在R-樹(shù)和SR-樹(shù)之間。這是因?yàn)殡m然PSR-樹(shù)的葉節(jié)點(diǎn)的聚集性強(qiáng)，減少了MBR重疊的面積，從而減少搜索的時(shí)間。但因在分裂過(guò)程中使用了貪心算法求最小邊界值，此時(shí)其時(shí)間上有大量的消耗。故PSR-樹(shù)的時(shí)間響應(yīng)慢于SR-樹(shù)，但仍然快于R-樹(shù)的時(shí)間響應(yīng)。

4? 結(jié)? 論

本文從R-樹(shù)空間索引的構(gòu)建到分析其查詢效率低下的原因。在此基礎(chǔ)上提出一種改進(jìn)的R-樹(shù)節(jié)點(diǎn)分裂優(yōu)化算法：PSR-樹(shù)索引。該算法在節(jié)點(diǎn)分裂過(guò)程中，通過(guò)使用貪心算法找到節(jié)點(diǎn)要分裂時(shí)其對(duì)應(yīng)的最小外接矩形MBR的最小邊界值，并在最小邊界值中任意找到兩個(gè)邊界對(duì)象。以這兩個(gè)對(duì)象為分裂后的兩個(gè)新增節(jié)點(diǎn)的首選數(shù)據(jù)對(duì)象進(jìn)行分裂操作。這樣有效地增加了葉子節(jié)點(diǎn)內(nèi)部空間數(shù)據(jù)的聚集性，從來(lái)減少了葉子節(jié)點(diǎn)最小外接矩形的面積。若將每次構(gòu)建好的PSR-樹(shù)存放在內(nèi)存中，下次訪問(wèn)時(shí)需要耗費(fèi)大量的時(shí)間進(jìn)行PSR-樹(shù)的重構(gòu)，因此本文把構(gòu)建好的PSR-樹(shù)存到文件中，并使用遞歸的方式寫(xiě)入節(jié)點(diǎn)信息。實(shí)驗(yàn)結(jié)果表明，PSR-樹(shù)比已有的SR-樹(shù)和R-樹(shù)在最小外接矩形的重疊面積上有明顯的減少，而PSR-樹(shù)中使用了貪心算法計(jì)算節(jié)點(diǎn)的最小邊界值，故在時(shí)間的耗費(fèi)上比SR-樹(shù)要高，而比R-樹(shù)的時(shí)間響應(yīng)上仍有所提高。

參考文獻(xiàn)：

[1] 陳菲，秦小麟.空間索引的研究 [J].計(jì)算機(jī)科學(xué)，2001，28（12）：59-62.

[2] 張明波，陸鋒，申排偉，等.R樹(shù)家族的演變和發(fā)展 [J].計(jì)算機(jī)學(xué)報(bào)，2005，28（3）：289-300.

[3] BRAKASTSOULAS S，PFOSER D，TTHEODORIDIS Y. Revisiting R-tree construction principles [C]//Proceedings of the 6th East European Conference on Advances in Databases and Information Systems.Springer-Verlag，2002：149-162.

[4] 孫殿柱，李心成，田中朝，等.基于動(dòng)態(tài)空間索引結(jié)構(gòu)的三角網(wǎng)格模型布爾運(yùn)算 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21（9）：1232-1237.

[5] 徐明.基于節(jié)點(diǎn)分裂優(yōu)化的R-樹(shù)索引結(jié)構(gòu) [J].計(jì)算機(jī)應(yīng)用研究，2016，33（12）：3530-3534.

[6] GUTTMAN A. R-Trees：A Dynamic Index Structure for Spatial Searching [J].Acm Sigmod Record，1984，14（2）：47-57.

[7] DU Q，GUNZBURGER M，JU L L，et al. Centroidal Voronoi Tessellation Algorithms for Image Compression，Segmentation，and Multichannel Restoration [J].Journal of Mathematical Imaging and Vision，2006，9（10）：177-194.

[8] PROIETTI G，F(xiàn)ALOUTSOS C. Analysis of range queries and self-spatial join queries on real region datasets stored using an R-tree [J].IEEE Transactions on Knowledge and Data Engineering，2000，12（5）：751-762.

[9] 胡昱璞.動(dòng)態(tài)k值聚類的R-樹(shù)空間索引構(gòu)建 [D].太原：太原理工大學(xué)，2016.

[10] 陳敏，王晶海.R*-樹(shù)空間索引的優(yōu)化研究 [J].計(jì)算機(jī)應(yīng)用，2007（10）：2581-2583.

[11] DRAISBACH U，NAUMANN F，SZOTT S，et al. Adaptive windows for duplicate detection [C]//Proceedings of the 2012 IEEE 28th International Conference on Data Engineering.IEEE，2012：1073-1083.

作者簡(jiǎn)介：賀建英（1979—），女，漢族，四川金堂人，教師，副教授，碩士，主要研究方向：軟件工程、機(jī)器學(xué)習(xí)。