Skiptree：面向多維數(shù)據(jù)的可擴(kuò)性范圍查詢的數(shù)據(jù)結(jié)構(gòu)

葉培順，史旭寧

(1.榆林學(xué)院 信息工程學(xué)院，陜西 榆林719000；2.銅川職業(yè)技術(shù)學(xué)院 繼續(xù)教育學(xué)院，陜西 銅川 727031)

近幾年來，基于集中式服務(wù)的網(wǎng)絡(luò)結(jié)構(gòu)逐漸向分布式結(jié)構(gòu)和對等網(wǎng)絡(luò)結(jié)構(gòu)發(fā)展，這種結(jié)構(gòu)就是可擴(kuò)展的分布式數(shù)據(jù)結(jié)構(gòu)(SDDS)，它首先是在LH*中提出的。建立在散列法或關(guān)鍵值匹配的基礎(chǔ)上的新的分布式數(shù)據(jù)結(jié)構(gòu)如Chord[1]，Viceroy[2]，Koorde[3]，Pastry[4]以及P-Grid[5]已經(jīng)被提出，現(xiàn)在多數(shù)對等覆蓋網(wǎng)為了達(dá)到路由O(logn)跳數(shù)，要求有O(logn)個(gè)鏈接每個(gè)節(jié)點(diǎn)，以DHTs為基礎(chǔ)的Viceroy 和Koorde是很值得討論的，因?yàn)閮H有O(1)個(gè)鏈接的每個(gè)節(jié)點(diǎn)只能有O(n)跳數(shù)，如果要達(dá)到O(logn)跳數(shù)是以受約束或無負(fù)載平衡為代價(jià)的。

以DHTs和散列法為基礎(chǔ)的系統(tǒng)無法進(jìn)行范圍查詢，相反，那些基于關(guān)鍵值匹配的系統(tǒng)，盡管要求更復(fù)雜的負(fù)載平衡技術(shù)，卻能支持范圍查詢。像P-Grid、 R-Tree和SkipNet[6]系統(tǒng)可以在單維空間中進(jìn)行范圍查詢。為了在多維空間儲(chǔ)存關(guān)鍵值，本文提出了一種新的可擴(kuò)展的分布式數(shù)據(jù)結(jié)構(gòu)叫Skiptree，該系統(tǒng)用一種分布式分割樹把空間分成許多較小的區(qū)域，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)是這棵數(shù)的葉子節(jié)點(diǎn)，并且負(fù)責(zé)一個(gè)區(qū)域。為了便于與同樣基于樹的解決方法做比較，在這里分割樹僅用來說明區(qū)域間的一種排序。路由機(jī)制和鏈接維護(hù)類似于SkipNet系統(tǒng)，并不依賴分割樹的形狀，所以通常情況下該系統(tǒng)不需要平衡這棵分割樹。SkipNet系統(tǒng)是依靠葉子節(jié)點(diǎn)來維護(hù)，在這棵樹里節(jié)點(diǎn)在跳躍中的順序是與分割樹的葉子從左到右定義的順序相同。處理一個(gè)單個(gè)關(guān)鍵值查詢與普通的SkipNet查詢方法類似，而范圍查詢的不同主要?dú)w因于Skiptree本身的多維性時(shí)，從另一個(gè)角度來說，Skiptree可以看作是對SkipNet在多維空間的一種延伸。

1 Skiptree的基本結(jié)構(gòu)

Skiptree由分割樹組成，所有分割樹的葉子形成了一個(gè)SkipNet系統(tǒng)。

假定每個(gè)數(shù)據(jù)單元有一個(gè)關(guān)鍵值，這個(gè)值是K維搜索空間中的一個(gè)點(diǎn)，當(dāng)這個(gè)網(wǎng)絡(luò)有N個(gè)葉子節(jié)點(diǎn)時(shí)，這個(gè)空間將被分成N個(gè)區(qū)域，也就是說每個(gè)葉子節(jié)點(diǎn)負(fù)責(zé)一個(gè)區(qū)域。圖1就是一個(gè)描述兩維空間的分割樹的例子，分割樹上的內(nèi)部節(jié)點(diǎn)用數(shù)字表示，葉子節(jié)點(diǎn)用字母表示，每個(gè)葉子就代表一個(gè)區(qū)域。假設(shè)S(v)表示指向節(jié)點(diǎn)v的區(qū)域，其中v是對每個(gè)數(shù)據(jù)單元負(fù)責(zé)的節(jié)點(diǎn)，它的關(guān)鍵值在S(v)中。

圖1 一棵兩維樹和它相應(yīng)的空間分割

對于網(wǎng)絡(luò)節(jié)點(diǎn)u，也就是分割樹上葉子節(jié)點(diǎn)，我們把樹的根部到節(jié)點(diǎn)u的路徑叫做節(jié)點(diǎn)u的主要路徑。這個(gè)路徑上節(jié)點(diǎn)的超平面等式，我們把它認(rèn)為是節(jié)點(diǎn)u特有的平面等式(Characteristic Plane Equations)，簡稱為u的CPE。在Skiptree中每個(gè)葉子節(jié)點(diǎn)儲(chǔ)存它自己的CPE也儲(chǔ)存它的那些鏈接的CPE。利用這些CPE的信息，在一個(gè)分割樹上節(jié)點(diǎn)u左右兩邊或者是它的其它鏈接點(diǎn)的左右兩邊的點(diǎn)，每個(gè)節(jié)點(diǎn)跟u一樣都能夠在本地被識(shí)別。此后，我們提到一個(gè)平面，實(shí)質(zhì)上就是指一個(gè)k維空間中k-1維的一個(gè)超級(jí)平面。

我們把在Skiptree中的網(wǎng)絡(luò)節(jié)點(diǎn)如圖2所示連在一起，按照前面所描述的，分割樹中的葉子組成一個(gè)SkipNet。

圖2 分割樹中的葉子組成的SkipNet

2 查詢處理

2.1單點(diǎn)查詢

單點(diǎn)查詢就是單個(gè)關(guān)鍵值查詢，它的路由算法在本質(zhì)上和SkipNet中的查詢算法是相同的,就是每個(gè)節(jié)點(diǎn)沿著路徑來接受查詢,發(fā)送查詢是通過最遠(yuǎn)的鏈接,如圖3所示, 到達(dá)目標(biāo)節(jié)點(diǎn)之間的長度是在每一個(gè)躍點(diǎn)都會(huì)被等分成2個(gè)節(jié)點(diǎn),這就說明查詢最多經(jīng)過log2n跳后到達(dá)目標(biāo).然而，由于在網(wǎng)絡(luò)中SkipNet是利用一種概率方法來選擇和維護(hù)鏈接,所以它能保證路由在O(logn)跳數(shù)內(nèi)。在文獻(xiàn)[3]中給出了形式證明。

圖3 單點(diǎn)查詢

為確保節(jié)點(diǎn)上不同位置的點(diǎn)能順序地在落在另一個(gè)節(jié)點(diǎn)包含的范圍內(nèi)，一個(gè)節(jié)點(diǎn)相對于CPE平面中不同位置的點(diǎn)就要能夠顯示從起始位置到根目錄的主路徑,直到它查詢當(dāng)前點(diǎn)落在第一個(gè)平面不同的位置的節(jié)點(diǎn)上,這個(gè)點(diǎn)包含在屬于一個(gè)兄弟子樹的一個(gè)區(qū)域中,如果子樹是一個(gè)左(右)子樹, 所有包含這個(gè)點(diǎn)的節(jié)點(diǎn)必須也是當(dāng)前節(jié)點(diǎn)的左(右)節(jié)點(diǎn)。

2.2范圍查詢

Skiptree中范圍查詢是一個(gè)3元組即(R,fs,ls),其中R是多維空間的查詢緯度, [fs,ls]是指所查詢的區(qū)間，也就是說它查詢這個(gè)序號(hào)僅僅是在[fs,ls]區(qū)間上的網(wǎng)絡(luò)節(jié)點(diǎn)，一個(gè)正常的范圍查詢?nèi)≈涤?R，-∞，+∞)，因此所有的節(jié)點(diǎn)在忽略它們的序號(hào)的情況下，都會(huì)被查詢到，注意R定義的區(qū)域可以是任意形狀樹，不管R與給定的超立方體是否相交,只要每個(gè)節(jié)點(diǎn)在本地能被識(shí)別。

當(dāng)一個(gè)節(jié)點(diǎn)S接到一個(gè)范圍查詢(R,fs,ls)，只要那兒的節(jié)點(diǎn)在此鏈接和下個(gè)鏈接之間都與R區(qū)域相交，它就發(fā)送這個(gè)請求到它的每個(gè)鏈接，例如在圖4中，假定A和B是S維護(hù)的兩個(gè)連續(xù)鏈接相對應(yīng)的兩個(gè)節(jié)點(diǎn)，如果在與R相交的A和B之間有節(jié)點(diǎn)，那S向A發(fā)送一份搜索請求副本，每個(gè)這樣的節(jié)點(diǎn)一定在圖4中畫陰影的子樹中之一上。

事實(shí)上，這樣的節(jié)點(diǎn)一定是標(biāo)有“+”的右邊節(jié)點(diǎn)和標(biāo)有“-”的左邊節(jié)點(diǎn)，因?yàn)镾有與它鏈接相對應(yīng)的所有的CPE，它也有權(quán)使用與標(biāo)有“+”或“-”的內(nèi)部節(jié)點(diǎn)相對應(yīng)的平面等式。因此,它能容易地從介于A和B之間每一個(gè)子樹相關(guān)聯(lián)的多維空間領(lǐng)域內(nèi)的等式內(nèi)被識(shí)別, 并且從此它可以確定是否有一些介于A和B之間的子樹的區(qū)域與R相交,以及是否有這樣一個(gè)子樹,它必須也包含一個(gè)區(qū)域與R相交的節(jié)點(diǎn)，注意一個(gè)查詢的副本通過一個(gè)鏈接被發(fā)送出去之前要適當(dāng)修正fs和ls 的查詢區(qū)間，原因就是要約束被查詢節(jié)點(diǎn)的順序防止重復(fù)查詢，例如在圖4中，假如復(fù)制的三元組(R,fs,ls)從S發(fā)送到A，也可以假定A.seq 和 B.seq分別是A和B的序號(hào)，然后S計(jì)算這個(gè)區(qū)間[fs/, ls/]作為[fs,ls]和[A.seq, B.seq]的交集,向A發(fā)送(R,fs/,ls/)查詢,這就確保了在這個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)只接受一次查詢。

圖4 一個(gè)范圍請求是通過S維護(hù)的各個(gè)鏈接來傳播

3節(jié)點(diǎn)的加入和離開

3.1節(jié)點(diǎn)的加入

為了加入到Skiptree中，一個(gè)新的節(jié)點(diǎn)v必須能夠聯(lián)系到現(xiàn)有的節(jié)點(diǎn)u。節(jié)點(diǎn)v首先插入到一個(gè)分割樹中，這個(gè)分割樹是用一個(gè)新的平面P把S(u)分成兩個(gè)區(qū)域，一個(gè)區(qū)域分給v，而u保持支配其他區(qū)域,同樣，v復(fù)制它的CPE從u和附加的平面P到雙方的CPE。我們可以任意選擇平面P，因?yàn)樨?fù)載平衡協(xié)議將不斷改變分割樹來得到一個(gè)更平衡的結(jié)構(gòu)。

分割樹更新之后，v通過連接SkipNet建立了它自身的網(wǎng)絡(luò)鏈接，這里節(jié)點(diǎn)序號(hào)是定義在這些節(jié)點(diǎn)中的一個(gè)全序號(hào)，僅僅只有O(logn)步。加入SkipNet的算法在文獻(xiàn)[3]中被描述。

3.2節(jié)點(diǎn)的離開

和節(jié)點(diǎn)的加入類似，當(dāng)節(jié)點(diǎn)v離開Skiptree時(shí)，它必須要經(jīng)過以下三步。

第一步是更新這個(gè)分割樹，假如在CPEv(節(jié)點(diǎn)v的CPE)中末尾的平面，我們把這個(gè)平面叫P，平面P 把它父親區(qū)域分成S(v)和R兩個(gè)區(qū)域，為了更新這個(gè)分割樹，節(jié)點(diǎn)v對R中的節(jié)點(diǎn)發(fā)送一個(gè)專門的范圍請求，通知它們把平面P從他們的CPE中移開，這樣v從分割樹中有效地移開。

第二步就是傳送數(shù)據(jù)，對每個(gè)用單點(diǎn)請求的數(shù)據(jù)v能簡單地發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)并能正確地傳送這個(gè)數(shù)據(jù)，然而，一個(gè)更有效的方法就是收集所有的可能的目標(biāo)區(qū)域并在本地對這個(gè)請求進(jìn)行評估。

最后一步，v必須從SkipNet中移開，在文獻(xiàn)[3]中指出，這能被減少到使用類似于Chord和 Pastry的后臺(tái)修正除去 O(1) 鏈接處理。

4總結(jié)

本文主要研究和論述了Skiptree這種數(shù)據(jù)結(jié)構(gòu)在分布式環(huán)境下處理多維空間的單點(diǎn)查詢和范圍查詢方法，詳細(xì)論證了這種數(shù)據(jù)結(jié)構(gòu)在每個(gè)節(jié)點(diǎn)上維護(hù)O(logn)個(gè)鏈接，并對單點(diǎn)查詢保證一個(gè)最大值為O(logn)個(gè)信息，同時(shí)也保證深度為O(logn)的范圍查詢，研究具有一定的學(xué)術(shù)價(jià)值和意義。對于節(jié)點(diǎn)失敗時(shí)的容錯(cuò)性和負(fù)載平衡以及存儲(chǔ)最優(yōu)化等問題還需進(jìn)一步研究和討論。