結構化數據存儲結構的索引方法研究仿真

張天一，張杰松

(1. 清華大學微電子與納電子學系，北京 100084；2. 大連理工大學電子信息與電氣工程學部，遼寧 大連 116024)

1 引言

目前數據的存儲工作是通過半結構化路由完成的，同時存儲對象為文件，采用文件名或者文件ID進行標識，同時構建對應的邏輯拓撲結構，并且借助DHT對關鍵字進行索引[1，2]，利用隨機哈希函數將結構化數據映射到Overlay Network相同的ID空間中?，F階段，在DHT上進行關鍵字索引的技術還需要進一步完善，尤其是無序數據的索引更是重中之重。

國內外相關專家針對結構化數據存儲索引方面的內容進行了大量的研究，例如劉良桂等人[3]根據類屬性提取關鍵字，構建分組索引，通過分組加密的形式降低索引和查詢請求的加密時間，獲取各個組分量的類別信息，更好實現分組索引。朱慶等人[4]將多模態場景數據抽象為圖的節點和邊，將稀疏矩陣采用時空索引的方式進行存儲和描述，最終結合多維樹實現索引。由于上述兩種方法未能采用模糊聚類算法對數據進行分割處理，導致查詢時間、索引構建時間以及通信開銷上升，查詢準確率下降等。為了有效解決上述問題，提出一種基于查詢采樣的結構化數據存儲索引方法，經實驗測試證明，所提方法能夠有效提升查詢正確率，同時還能夠降低查詢時間、索引構建時間以及通信開銷，以更快的速度完成查詢采樣。

2 結構化數據存儲索引方法

2.1 結構化數據劃分和樹狀索引結構的建立

采用模糊聚類算法對全部數據進行預處理[5，6]，同時確保每一個需要分割的數據是通過網格進行連通的。其中，算法的詳細操作步驟如下所示：

1)對網格模型優先進行預處理；

2)計算網格每對面片的最短距離權值Dist(facei，facej)；

3)為不同的面片分配對應的分割片，同時得到對應的可能性值；

4)計算模糊分解，同時將其劃分為三個部分；

5)在模糊分解中獲取準確的分界線，將網格劃分為精確的兩部分。

計算網絡S中兩個鄰近面片facei和facej之間的加權距離Weight(facei，facej)，以此為基礎計算測地線距離和夾角距離，最終得到兩個面片之間的最短距離。

計算相鄰面片facei和facej之間的夾角距離Ang-Dist(αij)，如式(1)所示

Ang-Dist(αij)=η(1-cosαij)

(1)

式中，η代表凹凸面角的取值；αij代表法向量夾角。

接下來計算相鄰兩個面片facei和facej之間的測地線距離Geod(facei，facej)

Geod(facei，facej)=dis(centeri，v)+dis(centerj，v)

(2)

式中，v代表公共頂點；centeri和centerj代表面片的中心點。

通過式(1)和式(2)求解出的夾角距離和測地線距離，并計算對應的加權處理后距離Weight(facei，facej)，對應的計算公式為

(3)

式中，avg(Geod)代表全部相鄰面片中全部測地線距離平均值；avg(Ang-Dist)代表全部相鄰平面夾角距離平均值；δ代表夾角距離和測試線距離經過加權后的比重值。

當結構化數據完成預處理后，無法直接通過原始模型進行連通，首先需要對原始模型進行簡化處理，即網格模型預處理，詳細的操作流程如下所示：

1)計算任意兩個面片之間的最短路徑Dist(facei，facej)；

2)假設Dist(facei，facej)的取值存在∞，則說明網格不連通，跳轉至步驟3)；假設不存在∞，則說明網格連通，則繼續進行分割即可；

3)如果網格模型中隨機兩個面片是連通的，則說明兩者不在同一網格內。

在模糊聚類算法計算的過程中，選取面片之間距離值Dist(facei，facej)最大的面片，同時選取一對代表點采用REPA和REPB表示。通過式(4)和式(5)計算分割面片SA和SB的可能性值PA(facei)和PB(facei)：

(4)

(5)

通過模糊聚類算法獲取模糊分割結果[7，8]，進而獲取分解模型需要分解的兩個部分，其中兩部分的邊界都是模糊邊界，將模糊邊界設定為模糊部分。

設定p代表分割片patch的面片，進行聚類的主要目的就是將面片聚類劃分為兩個部分，通過式(6)對其進行最小化處理

(6)

式中，pA和pB代表不同的分割片面片。

獲取分解結果需要優先在模糊部分SC區域構建一個邊界，當邊界確定后，則SC中的面片就能夠分配到對應的分割片中。

通過上述分析，主要使用模糊聚類算法對數據進行分割[9，10]，并且深入分析全部數據的組成結構，得到結構化數據的詳細分布信息。當數據完成分割處理后，需要借助B+樹構建樹狀索引。由于單位為距離，需要對各個類別的聚類環進行編號和排序操作，然后將其放置到B+樹中，以獲取最優參考點。

2.2 基于查詢采樣的結構化數據分布情況估計

當結構化數據被訪問時，將平均訪問概率設定為數據存儲的重要依據，然后通過最小聚類環判定數據是否為邊緣數據。

為了全面掌握結構化數據分布情況和策略索引之間的關聯性，采用查詢采樣方法進行分析和研究。設定聚類環為單位，得到結構化數據的平均訪問概率。在此基礎上，進一步分析數據分布情況對索引概率的影響，簡化數據存儲和掃描流程。

聚類環可索引能力ICi的計算公式為

(7)

式中，ci代表第i個聚類環，P(ci)代表聚類環i被訪問的平均概率；Nci代表聚類環i中全部數據的總數；b代表節點的數據容納量；u代表樹中的節點總數；H代表樹中間節點的高度。

當ICi的取值小于或者等于0，則說明聚類環為邊緣聚類環，對應的數據則為邊緣數據。

當完成結構化數據的分割后建立樹狀索引，以此為依據構建查詢集合Q，利用Q在B+樹中對結構化數據進行存儲索引，同時計算數據的平均訪問概率P。其中，聚類環內的數據過濾能力和P值存在密切關聯，P值越大，則過濾能力越差。另外，聚類環的可索引能力是通過查詢概率和索引計算式得到的。最終，還需要通過中心權限定理以及設定的置信度控制采樣次數，確保算法能夠以最快的速度和最少的次數完成采樣。

各個聚類環被訪問的期望主要將聚類環是否為邊緣環作為邊緣環的判定依據，同時也能夠完成采樣目標的查詢。對于被訪問概率為p的聚類環而言，設定各個聚類環中的變量是隨機且獨立分布的，在n次采樣過程中，聚類環被訪問的頻率ηn需要滿足n和p的二次分布條件。結合中心極限定理，能夠獲取參數的標準正態分布。

根據置信度的查詢采樣控制，需要借助置信度的調節實現采樣頻率和精度兩者的均衡。進行查詢采樣的主要目的就是估算不同聚類環的可索引能力，為了確保估算結果的準確性，在計算時需要及時對樹狀索引結構進行修正，確保ICi不會發生任何變化，同時還能夠提前終止采樣，降低采樣數量。

2.3 結構化數據存儲索引

為了有效提升高維數據庫的查詢效率，需要通過數據的分布情況來選擇合適的索引策略。其中，結構化數據存儲索引的組成結構如圖1所示。

圖1 結構化數據存儲索引結構圖

為了加快結構化數據存儲速度和索引效率，需要設定一個專門的緩存系統，系統中主要包含一個用戶跟蹤的緩存幀描述器。同時，在以塊為單位的存儲系統中，加入B+樹索引，以全面提升檢索效率。

在采用B+樹實現索引的過程中，需要在原始結構的基礎上增加一些全新的頁結構。其中，新增頁結構也能夠劃分為多個頁節點。詳細的操作過程如下所示：

1)對各個分支頁進行初始化處理；

2)假設層數為1，跳轉至步驟3)；

3)假設當前頁有可用空間，則直接插入當前頁，同時輸出分支頁記錄；

4)假設當前頁沒有可用空間，分裂當前頁，假設當前頁為根節點，則樹長高一層，分配一個全新的根節點；反之，則跳轉至步驟3)；

5)假設層數不為1，則跳轉至步驟7)；

6)通過當前頁和鍵值Key獲取當前頁節點對應子樹的頁號，利用子樹的頁號在緩存區中讀取對應的子節點；

7)將當前層數減1設定為全新的輸入值，通過遞歸調用算法進行調節，輸出結果賦值；

8)如果當前頁未滿，則直接跳轉至步驟2)；

9)假設當前頁已滿，則對當前頁進行分裂處理；反之，則跳轉至步驟2)。

由于樹型索引具有較強的過濾性能，所以優先通過順序掃描方法對結構化數據進行稀疏處理；然后將全部結構化數據自動存儲到樹型索引中繼續進行關鍵字查詢，為后續的研究奠定一定的理論依據，同時也確保查詢結果的準確性。

采用最優KNN查詢策略對結構化數據進行檢索時[11，12]，按照順序對文件中的全部數據進行掃描，確保聚類環內的全部查詢半徑和查詢結果會實時更新。針對B+樹索引而言，全部的聚類環主要通過數據距離查詢點的距離長短進行排序，并且放置到對應的序列中。同時還需要進一步判定聚類環區域和查詢區域是否相交，假設兩者是相交關系，則對聚類環內的數據進行搜索，并且在樹狀索引中裁剪出稀疏數據，根據順序搜索策略達到結構化數據存儲索引的目的。

3 仿真研究

為了驗證所提基于查詢采樣的結構化數據存儲索引方法的有效性，需要進行仿真測試。

1)結構化數據存儲索引構建效率測試

在相同的數據集中，實驗重點分析采用模糊聚類分解前后的結構化數據存儲索引構建效率變化情況，將索引構建時間設定為測試指標，分析采用傳統聚類算法和模糊聚類算法后的索引構建時間變化情況，如圖2所示。

圖2 傳統聚類和模糊聚類算法的索引構建時間對比結果

分析圖2中的實驗數據可知，當通過傳統聚類算法和模糊聚類算法分別進行結構化數據分割處理后，其中采用模糊聚類算法后的索引構建時間明顯低于傳統聚類方法，同時也能夠在查詢過程中有效避免整體聚類搜索，進而使所提方法的索引構建時間得到明顯降低，索引構建效率大幅度提升。

選取文獻[3]方法和文獻[4]方法作為測試對象，分析各個方法的索引構建時間變化情況，詳細的實驗結果如圖3所示。

圖3 不同方法的索引構建時間測試結果

由圖3中的實驗數據可知，當數據規模開始持續增加，各個方法對應的索引構建時間也開始飛速增加。但是相比另外兩種方法，所提方法的索引構建時間明顯更低一些，充分證明在所提方法中加入模糊聚類算法的可行性和正確性。

2)通信開銷和查詢時間測試分析

實驗分別模擬三種不同方法在復雜查詢條件下的通信開銷和查詢時間變化情況，具體實驗結果如圖4和圖5所示。

圖4 不同方法的通信開銷測試結果

圖5 不同方法的查詢時間測試結果

分析圖4和圖5中的實驗數據可知，當數據集的大小開始增加，三種方法的通信開銷和查詢時間也開始呈直線上升趨勢。相比另外兩種方法，所提方法的通信開銷和查詢時間明顯更低一些，充分證明了所提方法的優越性。

3)查詢正確率測試分析

為了測試不同方法的可用性，實驗將查詢正確率設定為測試指標，詳細的實驗結果如表1所示。

表1 不同方法的查詢正確率測試結果

分析表1中的實驗數據可知，查詢正確率會隨著失效節點的增加而降低，而且各個方法的下降幅度十分明顯。但是相比另外兩種方法，所提方法的查詢正確率還是更高一些。

4 結束語

為了更好實現結構化數據存儲索引，結合查詢采樣算法提出一種基于查詢采樣的結構化數據存儲索引方法。經實驗測試證明，所提方法能夠有效降低查詢時間、索引構建時間以及通信開銷，提升查詢準確率，具有較強的可用性。