基于Hadoop的分布式SQL數據庫索引設計與實踐?

陳 紅

（昌吉職業技術學院 昌吉 831100）

1 引言

隨著數據規模的增長，傳統的SQL數據庫管理模式已經無法有效地管理海量的數據庫數據［1］。隨著云計算等技術在信息系統等技術領域的應用，分布式系統為處理海量數據提供了一個全新的方案［2］，如何將分布式系統應用到數據管理當中已經成為了一個研究的熱點。SQL數據庫索引是海量數據管理與檢索的關鍵問題。樹形索引［3］是當前流行的SQL數據庫索引結構，其中以R樹家族［4］最為突出。隨著分布式系統研究的深入，分布式索引逐漸成為SQL數據庫索引的研究熱點［5］，文獻［6～7］研究了MR-tree、R樹和多級R-tree的并行化實現，文獻［8］對四叉樹進行面向列式存儲擴展改進，文獻［9］將VoR-Tree、雙層倒排網格索引、SQL數據庫的k近鄰查詢與MapReduce編程模型相結合進行分布式改造。

針對海量數據的索引需求，本文將SQL數據庫索引與云計算技術相結合，提出了基于Hadoop平臺的分布式SQL數據庫索引，并從架構設計、數據劃分和局部索引和全局索引構建等方面出發，在Hadoop下設計并實現了分布式SQL數據庫索引。同時。最后本文搭建了Hadoop環境并進行實驗證明了改進后的算法可以有效減少數據檢索時間，提高整體性能，高并發、低成本、高可靠的完成數據檢索任務。

2 索引結構設計

本文設計的基于HDFS的分布式SQL數據庫索引采用分層的分布式索引結構，分層式分布式索引結構首先將數據庫數據按照SQL數據庫分布進行劃分，將SQL數據庫上臨近的數據劃分到一個分區當中，再對每一個分區當中的數據構建一個局部索引，并將局部索引以及該分區數據存儲到數據節點當中。當所有數據劃分完畢并且所有局部索引構建完成以后，在主節點中依據各個局部索引的根節點構建一個全局索引，存在主節點當中。由于主節點中的全局索引只保存了局部索引的根節點的信息，全局索引的大小得到了限制，減輕了主節點存儲與計算的負擔［10］，同時，由于全局索引的大小較小，在程序運行時可以將全局索引一次性加載到內存中，對全局索引進行檢索時避免了磁盤的IO，提升了數據檢索效率［11］。分層式SQL數據庫索引結構如圖1所示。

圖1 分層式分布式索引

本文索引由全局索引、局部索引、數據分片三層構成，索引構建主要分為如下三個步驟：

全局索引：全局索引是指針對整個數據集建立一個統一的索引，每一個索引指向一個節點或一個數據塊，實現算法相對比較簡單。全局索引可以看做是局部索引的緩存，基于全局索引的查詢操作，只需要訪問相關的節點或數據塊即可，能夠減少數據讀取時間，提高檢索效率。

局部索引：局部索引是指針對每一個數據分區所建立的獨立索引，數據塊之間的檢索也相互獨立，具有良好的容錯能力；同時也有利于數據塊的局部更新和索引重建。

數據分片：文件上傳到HDFS上會被分成若干文件塊并存儲到Datanode上。每個文件塊的大小應小于HDFS文件塊的大小，如果文件塊的大小大于HDFS文件塊大小，那么單個數據分片就可能會被存到多個不同的Datanode當中，這樣導致在進行檢索時需要通過網絡從不同的Datanode上獲取數據，這樣會降低數據檢索的效率。因此，應控制數據分片與其對應的索引大小和小于HDFS的文件塊大小。

數據集劃分成若干個數據分片：

局部索引構建：根據每一個數據分片的數據，構建局部索引，并將構建的索引存儲到對應的Datanode中。

全局索引構建：根據數據劃分以及局部索引構建的結果，在Namenode上構建一個全局索引。

3 SQL數據庫劃分

其中，S為待劃分數據庫數據大小，一般是128M，α表示膨脹系數，膨脹系數主要的考慮因素為數據庫數據與其局部索引的大小差距，一般采用0.2～

本文基于海量SQL數據庫數量，直接建立索引將會使索引太龐大，嚴重影響數據檢索效率［12］，需要將整個數據庫數據按照一定規則進行劃分后建立局部索引，這樣可以避免上述狀況，選取一個合適的SQL數據庫劃分方案十分重要。

3.1 SQL數據庫劃分規則

SQL數據庫劃分是構造分布式索引的關鍵環節，劃分規則的好壞直接決定了索引的檢索效率，在進行數據劃分時，應盡量遵循如下兩個原則：

1）生成若干個大小基本相等的分區，且分區大小不超過HDFS數據塊大小。如果劃分分區超過HDFS數據塊大小可能導致該分區數據存儲到不同的HDFS上，影響查詢效率。如果分區大小差距過大，部分分區數據量太少，會導致索引節點數增加，索引層數高度增加，同時會導致熱區問題，影響查詢效率。

2）生成的數據分區要保證SQL數據庫局部性。在進行范圍查詢時，應當盡量減少IO操作，減少讀寫磁盤的次數。如當e1和e2SQL數據庫上距離較近，則e1和e2應當分配到同一個分區當中。劃分結果以及其局部索引需要存儲到同一個HDFS塊中，所以劃分的數據分區以及該分區的局部索引大小之和應小于HDFS塊大小。確定劃分區域數量為0.3即可［13］。

本文采用STR樹葉節點生成算法［14］對數據進行劃分，圖2為STR樹葉節點劃分方式，假設有N個數據，首先將數據按照x坐標值的大小進行排序，平均生成[n]個分組，其中n為分區數量，這樣生成的分組中每個分組至少包含[N/n]個數據。然后在得到的分組結果中以y的坐標值大小進行排序，每[N/n]個數據被劃為一組，生成n個分組。如果數據結構為多邊形，則按照其最小外包矩形中心點進行排序。根據以上算法可以得知，如果數據均勻分布在SQL數據庫區域上，那么這種劃分方式與網格分割［15］效果類似，但是如果數據分布極不均勻，那么這種劃分方式能夠更好地對數據進行劃分。

圖2 STR葉子節點分割示意圖

STR葉節點劃分方式依據數據的SQL數據庫臨近，對數據進行了聚類處理［16］，能夠有效地應對數據分布不均勻的情況，但是在劃分過程中，需要進行多次排序操作，處理海量數據的效率不高，因此，考慮首先對數據進行采樣處理，然后采用Ma?pReduce進行并行劃分，具體實現過程將在下一節詳細描述。

3.2 并行數據劃分

本文首先對SQL數據庫中的數據進行充足隨機采樣，因為足夠的采樣數據可以代表整體數據的分布趨勢及分布規律，通過MapReduce對任意采樣的數據塊實施數據排序，采樣的數據塊進行X排序后，將X分組中x坐標的最大值與下個相鄰分組的X最小值的平均值作為兩個分組直接的界線值，全部分組中的第一個分組與最后一個分組的界線值分別選擇起始X值與結束X值；同理可得到y坐標的界線值。最終得到一個劃分函數func確定一個分區

4 基于改進R樹的分布式索引構建及存儲

通過數據劃分得到了劃分后的數據分區，將根據每一個數據分片的結果單獨構建R樹索引，保證所有的數據都在索引范圍內，采用一種改進的R樹生成方式構建局部索引，提升在分區中查詢數據的效率。

4.1 局部索引構建與存儲

假設經過數據劃分的數據塊中有k個數據，相應則在數據劃分過程中建立了k個MBR，在本節使用一種改進的R樹生成算法Reduce過程中構建數據的局部R樹索引。在map的階段已經獲取了數據分片中所有數據的MBR，采用動態插入MBR的方式構建R樹。在插入數據過程中，如果向一個飽和節點中插入數據，首先檢查溢出節點表中是否包含此節點，如果已經包含且該節點的溢出節點沒有飽和則直接插入數據即可，如果溢出節點表中尚未包含該節點，則在溢出節點表中為該節點創建一個溢出節點，并向溢出節點中插入數據。若一個節點的溢出節點也飽和，則對該節點及其溢出節點進行歸并分裂操作，寫回到R樹種。當所有對象都訪問完，如果溢出節點表中還有數據，則進行一次強制寫回操作，最后將生成的R樹索引及分區數據序列化到HDFS上。

圖3 局部索引存儲格式

在進行數據劃分時，已經在每個數據分區中為局部索引預留了SQL數據庫，所以可以直接將局部索引和數據存儲在同一個HDFS塊中。數據及其局部索引的存儲格式如圖3所示，分為索引元數據部分、局部索引部分和數據部分。其中，第一部分為樹結構區存儲R樹的結構信息，包括索引的大小即樹結點數據區域的大小、樹的高度、樹中每個結點的容量以及SQL數據庫對象的個數。根據樹的高度以及結點容量可以計算出結點對象的個數。中間區域為樹結點數據區域，該區域存放的是樹結點信息，每個結點對象存放其子節點的信息（子節點的位置指針及子節點的MBR），最后一個區域為數據區域記錄每一個屬于該區域的數據。在信息查詢時一般不會加載數據，而是只把R樹的結構信息加載到內存中，當只需要進一步查詢時才加載具體的數據。

4.2 全局索引構建與存儲

本文的設計思想是用戶在每一次對數據的操作都會先經過全局索引的檢索，然后根據全局索引的檢索情況在對局部索引進行檢索。本節將介紹全局索引的構建和存儲。由于全局索引使用的頻率高且數據量很小，因此，全局索引構建完成后可以將其常駐于Namenode節點的內存中。

全局索引的存儲結構與局部索引類似，具有樹結構信息以及樹結點信息兩個部分組成，不同之處為在全局索引的樹葉子結點數據中存放的不是具體的數據的指針與外包矩形，而是存放的相應的HDFS文件路徑以及局部索引根結點的MBR信息。從而實現全局索引與局部索引的關聯。全局索引的構建在所有局部索引構建完成之后進行。由于分區數量不會過多。因此全局索引的大小不會過大，不需要分布式執行。全局索引采用常規的R樹生成方式即可。

5 實驗分析

5.1 實驗環境

本實驗借助虛擬機搭建了具有6個節點的Ha?doop集群，每個節點分配4G內存和一定SQL數據庫的硬盤，節點上運行Ununtu14.0操作系統以及Hadoop2.6.4，并支持Linux下Java8的操作環境Ha?doop集群中包括1個Master和5個Slave，Master主要負責數據的整體調度，Slave作為具體的執行者負責存儲數據和處理數據。

5.2 區域查詢實驗

由于本文索引采用多級分布式索引結構，因此在進行區域查詢時與普通單機SQL數據庫索引查詢操作不同。在區域查詢操作中首先通過全局索引將SQL數據庫查詢操作劃分到不同的數據節點中進行查詢，最終將數據節點中查詢到的數據聚合為最終的數據。

實驗使用谷歌地圖數據集［17］，大小約為9.3G，查詢范圍由0.0001%～1%變化，分別選取工作節點數目為2、4、6和單機狀態，測試節點個數的變化對查詢時間的影響。實驗數據如圖4所示。

圖4 區域查詢實驗結果

由圖4可得出，當查詢區域特別小時，單機狀態下查詢所需時間并沒有明顯劣勢，但是隨著查詢區域的擴大，查詢操作耗時呈指數型增長，這是因為單臺計算機本身性能有限。通過對比2、4、6個工作節點的查詢耗時，可看出相同數據量、相同查詢區域的情況下，數據查詢時間隨著工作節點的增多而減少，這是因為具體的查詢操作被分配到了數據節點中執行，提高了檢索性能。由此得出，本文設計的分布式SQL數據庫索引提高了檢索性能，適用于處理海量數據。

5.3 k近鄰查詢實驗

k近鄰查詢的基本思想是，給定一個參考點的坐標，查詢離該點最近的k個數據。基于本文索引的k臨近查詢操作共分為3個步驟分別為全局knn操作，局部knn操作，局部knn結果檢查合并。其中全局knn操作由于計算量較小在Master節點執行即可。局部knn操作和檢查在Map階執行。結果合并階段在Reduce中執行。

實驗同樣使用谷歌地圖數據集，大小約為9.3G，n的范圍從1～10000變化，實驗隨機選取若干點進行多次實驗，取最終的平均值，實驗分別選取工作節點數目為2、4、6和單機狀態，測試節點個數的變化對查詢時間的影響。實驗數據如圖5所示。

如圖5所示在k近鄰查詢實驗中隨著k值的增加，查詢耗時也在增加。這是因為k值越大，需要檢索的范圍越大，查詢操作耗費的時間也就越多，并且耗時增幅越明顯。這是由于在k值比較小時，集群并未發揮全部性能。因此小幅度增大k值，查詢所需時間增長幅度較小。然而當k值增大到一定程度，集群已經發揮全部性能，此時繼續增長k值，查詢操作耗時就會出現線性增長的狀況。當k值較大時k近鄰查詢所需時間隨著工作節點數量的增加而減小，而當k值較小時，查詢操作的耗時幾乎不受節點數量的影響。這證實了n值較小時，k近鄰查詢只在比較少的節點中進行。而當k值較大時，k近鄰查詢將在集群所有節點中并行執行。

圖5 k近鄰查詢實驗結果

6 結語

由于傳統的單機SQL數據庫索引技術面對大規模數據時計算能力不足，索引效率低，因此本文還將SQL數據庫索引技術與云計算技術相結合，提出了基于Hadoop平臺的分布式SQL數據庫索引。本文從索引結構設計、數據劃分、局部和全局索引構建和存儲等方面，詳細闡述了分布式SQL數據庫索引的實現，最后搭建Hadoop平臺進行了測試。在今后的研究工作中，重點會放在對R樹算法更好的優化過程中。同時，本文主要是針對二維數據上的研究，日后的研究將不僅僅局限在二維數據上，將研究的目光擴展到更高維上。

［1］賀瑤，王文慶，薛飛.基于云計算的海量數據挖掘研究［J］. 計算機技術與發展，2013，23（02）：69-72.

［2］曲家朋，廖海.海量文件存儲技術研究［J］.機電工程技術，2016（08）：359-362.

［3］史曉楠，徐瀾，徐丹丹，等.一種改進的基于Hash算法及概率的k-mer索引方法［J］.通信電源技術，2017，34（03）：70-72，74.

［4］邵華，江南，胡斌，等.利用GPU的R樹細粒度并行STR方法批量構建［J］.武漢大學學報（信息科學版），2014，39（09）：1068-1073.

［5］翁海星，宮學慶，朱燕超，等.集群環境下分布式索引的實現［J］. 計算機應用，2016，36（01）：1-7+12.

［6］劉義，景寧，陳犖，等.MapReduce框架下基于R-樹的k-近鄰連接算 法［J］. 軟 件學報，2013，24（08）：1836-1851.

［7］劉義，陳犖，景寧，等.基于R-樹索引的Map-Reduce空間連接聚集操作［J］.國防科技大學學報，2013，35（01）：136-141.

［8］楊建思.一種四叉樹與KD樹結合的海量機載LiDAR數據組織管理方法［J］.武漢大學學報（信息科學版），2014，39（08）：918-922.

［9］楊文奇，劉杰，陳飛輪.基于MapReduce的并行VoR-Tree索引［J］. 地理空間信息，2013，11（06）：109-111.

［10］陳潤健，王金鳳.并行計算和稀疏存儲在模糊積分上的應用［J］. 計算機應用研究，2017（01）：1-9.

［11］趙輝，楊樹強，陳志坤，等.基于MapReduce模型的范圍查詢分析優化技術研究［J］.計算機研究與發展，2014，51（03）：606-617.

［12］杜朝暉，朱文耀.云存儲中利用屬性基加密技術的安全數據檢索方案［J］.計算機應用研究，2016，33（03）：860-865.

［13］王蛟龍，周潔，高慧，等.基于局部環境形狀特征識別的移動機器人避障方法［J］.信息與控制，2015，44（01）：91-98.

［14］昌春艷，王沁，田錕，等.優化STR模型的實證研究［J］.武漢理工大學學報（信息與管理工程版），2013，35（04）：565-569.

［15］施逸飛，熊岳山，謝智歌，等.基于多核學習的快速網格分割算法［J］.計算機輔助設計與圖形學學報，2015，27（11）：2031-2038.

［16］黃良韜，趙志誠，趙亞群.基于隨機森林的密碼體制分層識別方案［J］. 計算機學報，2017（07）：1-19.

［17］李艷霞，劉學，黨壽江，等.網管系統中基于谷歌地圖的拓撲可視化實現［J］.計算機工程與設計，2013，34（02）：681-685.