Skiptree：面向多維數據的可擴性范圍查詢的數據結構

葉培順，史旭寧

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

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

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

1 Skiptree的基本結構

Skiptree由分割樹組成，所有分割樹的葉子形成了一個SkipNet系統。

假定每個數據單元有一個關鍵值，這個值是K維搜索空間中的一個點，當這個網絡有N個葉子節點時，這個空間將被分成N個區域，也就是說每個葉子節點負責一個區域。圖1就是一個描述兩維空間的分割樹的例子，分割樹上的內部節點用數字表示，葉子節點用字母表示，每個葉子就代表一個區域。假設S(v)表示指向節點v的區域，其中v是對每個數據單元負責的節點，它的關鍵值在S(v)中。

圖1 一棵兩維樹和它相應的空間分割

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

我們把在Skiptree中的網絡節點如圖2所示連在一起，按照前面所描述的，分割樹中的葉子組成一個SkipNet。

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

2 查詢處理

2.1單點查詢

單點查詢就是單個關鍵值查詢，它的路由算法在本質上和SkipNet中的查詢算法是相同的,就是每個節點沿著路徑來接受查詢,發送查詢是通過最遠的鏈接,如圖3所示, 到達目標節點之間的長度是在每一個躍點都會被等分成2個節點,這就說明查詢最多經過log2n跳后到達目標.然而，由于在網絡中SkipNet是利用一種概率方法來選擇和維護鏈接,所以它能保證路由在O(logn)跳數內。在文獻[3]中給出了形式證明。

圖3 單點查詢

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

2.2范圍查詢

Skiptree中范圍查詢是一個3元組即(R,fs,ls),其中R是多維空間的查詢緯度, [fs,ls]是指所查詢的區間，也就是說它查詢這個序號僅僅是在[fs,ls]區間上的網絡節點，一個正常的范圍查詢取值于(R，-∞，+∞)，因此所有的節點在忽略它們的序號的情況下，都會被查詢到，注意R定義的區域可以是任意形狀樹，不管R與給定的超立方體是否相交,只要每個節點在本地能被識別。

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

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

圖4 一個范圍請求是通過S維護的各個鏈接來傳播

3節點的加入和離開

3.1節點的加入

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

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

3.2節點的離開

和節點的加入類似，當節點v離開Skiptree時，它必須要經過以下三步。

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

第二步就是傳送數據，對每個用單點請求的數據v能簡單地發現這個節點并能正確地傳送這個數據，然而，一個更有效的方法就是收集所有的可能的目標區域并在本地對這個請求進行評估。

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

4總結

本文主要研究和論述了Skiptree這種數據結構在分布式環境下處理多維空間的單點查詢和范圍查詢方法，詳細論證了這種數據結構在每個節點上維護O(logn)個鏈接，并對單點查詢保證一個最大值為O(logn)個信息，同時也保證深度為O(logn)的范圍查詢，研究具有一定的學術價值和意義。對于節點失敗時的容錯性和負載平衡以及存儲最優化等問題還需進一步研究和討論。