基于Hadoop的分布式SQL數(shù)據(jù)庫索引設(shè)計(jì)與實(shí)踐?

陳 紅

（昌吉職業(yè)技術(shù)學(xué)院 昌吉 831100）

1 引言

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

針對(duì)海量數(shù)據(jù)的索引需求，本文將SQL數(shù)據(jù)庫索引與云計(jì)算技術(shù)相結(jié)合，提出了基于Hadoop平臺(tái)的分布式SQL數(shù)據(jù)庫索引，并從架構(gòu)設(shè)計(jì)、數(shù)據(jù)劃分和局部索引和全局索引構(gòu)建等方面出發(fā)，在Hadoop下設(shè)計(jì)并實(shí)現(xiàn)了分布式SQL數(shù)據(jù)庫索引。同時(shí)。最后本文搭建了Hadoop環(huán)境并進(jìn)行實(shí)驗(yàn)證明了改進(jìn)后的算法可以有效減少數(shù)據(jù)檢索時(shí)間，提高整體性能，高并發(fā)、低成本、高可靠的完成數(shù)據(jù)檢索任務(wù)。

2 索引結(jié)構(gòu)設(shè)計(jì)

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

圖1 分層式分布式索引

本文索引由全局索引、局部索引、數(shù)據(jù)分片三層構(gòu)成，索引構(gòu)建主要分為如下三個(gè)步驟：

全局索引：全局索引是指針對(duì)整個(gè)數(shù)據(jù)集建立一個(gè)統(tǒng)一的索引，每一個(gè)索引指向一個(gè)節(jié)點(diǎn)或一個(gè)數(shù)據(jù)塊，實(shí)現(xiàn)算法相對(duì)比較簡單。全局索引可以看做是局部索引的緩存，基于全局索引的查詢操作，只需要訪問相關(guān)的節(jié)點(diǎn)或數(shù)據(jù)塊即可，能夠減少數(shù)據(jù)讀取時(shí)間，提高檢索效率。

局部索引：局部索引是指針對(duì)每一個(gè)數(shù)據(jù)分區(qū)所建立的獨(dú)立索引，數(shù)據(jù)塊之間的檢索也相互獨(dú)立，具有良好的容錯(cuò)能力；同時(shí)也有利于數(shù)據(jù)塊的局部更新和索引重建。

數(shù)據(jù)分片：文件上傳到HDFS上會(huì)被分成若干文件塊并存儲(chǔ)到Datanode上。每個(gè)文件塊的大小應(yīng)小于HDFS文件塊的大小，如果文件塊的大小大于HDFS文件塊大小，那么單個(gè)數(shù)據(jù)分片就可能會(huì)被存到多個(gè)不同的Datanode當(dāng)中，這樣導(dǎo)致在進(jìn)行檢索時(shí)需要通過網(wǎng)絡(luò)從不同的Datanode上獲取數(shù)據(jù)，這樣會(huì)降低數(shù)據(jù)檢索的效率。因此，應(yīng)控制數(shù)據(jù)分片與其對(duì)應(yīng)的索引大小和小于HDFS的文件塊大小。

數(shù)據(jù)集劃分成若干個(gè)數(shù)據(jù)分片：

局部索引構(gòu)建：根據(jù)每一個(gè)數(shù)據(jù)分片的數(shù)據(jù)，構(gòu)建局部索引，并將構(gòu)建的索引存儲(chǔ)到對(duì)應(yīng)的Datanode中。

全局索引構(gòu)建：根據(jù)數(shù)據(jù)劃分以及局部索引構(gòu)建的結(jié)果，在Namenode上構(gòu)建一個(gè)全局索引。

3 SQL數(shù)據(jù)庫劃分

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

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

3.1 SQL數(shù)據(jù)庫劃分規(guī)則

SQL數(shù)據(jù)庫劃分是構(gòu)造分布式索引的關(guān)鍵環(huán)節(jié)，劃分規(guī)則的好壞直接決定了索引的檢索效率，在進(jìn)行數(shù)據(jù)劃分時(shí)，應(yīng)盡量遵循如下兩個(gè)原則：

1）生成若干個(gè)大小基本相等的分區(qū)，且分區(qū)大小不超過HDFS數(shù)據(jù)塊大小。如果劃分分區(qū)超過HDFS數(shù)據(jù)塊大小可能導(dǎo)致該分區(qū)數(shù)據(jù)存儲(chǔ)到不同的HDFS上，影響查詢效率。如果分區(qū)大小差距過大，部分分區(qū)數(shù)據(jù)量太少，會(huì)導(dǎo)致索引節(jié)點(diǎn)數(shù)增加，索引層數(shù)高度增加，同時(shí)會(huì)導(dǎo)致熱區(qū)問題，影響查詢效率。

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

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

圖2 STR葉子節(jié)點(diǎn)分割示意圖

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

3.2 并行數(shù)據(jù)劃分

本文首先對(duì)SQL數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行充足隨機(jī)采樣，因?yàn)樽銐虻牟蓸訑?shù)據(jù)可以代表整體數(shù)據(jù)的分布趨勢(shì)及分布規(guī)律，通過MapReduce對(duì)任意采樣的數(shù)據(jù)塊實(shí)施數(shù)據(jù)排序，采樣的數(shù)據(jù)塊進(jìn)行X排序后，將X分組中x坐標(biāo)的最大值與下個(gè)相鄰分組的X最小值的平均值作為兩個(gè)分組直接的界線值，全部分組中的第一個(gè)分組與最后一個(gè)分組的界線值分別選擇起始X值與結(jié)束X值；同理可得到y(tǒng)坐標(biāo)的界線值。最終得到一個(gè)劃分函數(shù)func確定一個(gè)分區(qū)

4 基于改進(jìn)R樹的分布式索引構(gòu)建及存儲(chǔ)

通過數(shù)據(jù)劃分得到了劃分后的數(shù)據(jù)分區(qū)，將根據(jù)每一個(gè)數(shù)據(jù)分片的結(jié)果單獨(dú)構(gòu)建R樹索引，保證所有的數(shù)據(jù)都在索引范圍內(nèi)，采用一種改進(jìn)的R樹生成方式構(gòu)建局部索引，提升在分區(qū)中查詢數(shù)據(jù)的效率。

4.1 局部索引構(gòu)建與存儲(chǔ)

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

圖3 局部索引存儲(chǔ)格式

在進(jìn)行數(shù)據(jù)劃分時(shí)，已經(jīng)在每個(gè)數(shù)據(jù)分區(qū)中為局部索引預(yù)留了SQL數(shù)據(jù)庫，所以可以直接將局部索引和數(shù)據(jù)存儲(chǔ)在同一個(gè)HDFS塊中。數(shù)據(jù)及其局部索引的存儲(chǔ)格式如圖3所示，分為索引元數(shù)據(jù)部分、局部索引部分和數(shù)據(jù)部分。其中，第一部分為樹結(jié)構(gòu)區(qū)存儲(chǔ)R樹的結(jié)構(gòu)信息，包括索引的大小即樹結(jié)點(diǎn)數(shù)據(jù)區(qū)域的大小、樹的高度、樹中每個(gè)結(jié)點(diǎn)的容量以及SQL數(shù)據(jù)庫對(duì)象的個(gè)數(shù)。根據(jù)樹的高度以及結(jié)點(diǎn)容量可以計(jì)算出結(jié)點(diǎn)對(duì)象的個(gè)數(shù)。中間區(qū)域?yàn)闃浣Y(jié)點(diǎn)數(shù)據(jù)區(qū)域，該區(qū)域存放的是樹結(jié)點(diǎn)信息，每個(gè)結(jié)點(diǎn)對(duì)象存放其子節(jié)點(diǎn)的信息（子節(jié)點(diǎn)的位置指針及子節(jié)點(diǎn)的MBR），最后一個(gè)區(qū)域?yàn)閿?shù)據(jù)區(qū)域記錄每一個(gè)屬于該區(qū)域的數(shù)據(jù)。在信息查詢時(shí)一般不會(huì)加載數(shù)據(jù)，而是只把R樹的結(jié)構(gòu)信息加載到內(nèi)存中，當(dāng)只需要進(jìn)一步查詢時(shí)才加載具體的數(shù)據(jù)。

4.2 全局索引構(gòu)建與存儲(chǔ)

本文的設(shè)計(jì)思想是用戶在每一次對(duì)數(shù)據(jù)的操作都會(huì)先經(jīng)過全局索引的檢索，然后根據(jù)全局索引的檢索情況在對(duì)局部索引進(jìn)行檢索。本節(jié)將介紹全局索引的構(gòu)建和存儲(chǔ)。由于全局索引使用的頻率高且數(shù)據(jù)量很小，因此，全局索引構(gòu)建完成后可以將其常駐于Namenode節(jié)點(diǎn)的內(nèi)存中。

全局索引的存儲(chǔ)結(jié)構(gòu)與局部索引類似，具有樹結(jié)構(gòu)信息以及樹結(jié)點(diǎn)信息兩個(gè)部分組成，不同之處為在全局索引的樹葉子結(jié)點(diǎn)數(shù)據(jù)中存放的不是具體的數(shù)據(jù)的指針與外包矩形，而是存放的相應(yīng)的HDFS文件路徑以及局部索引根結(jié)點(diǎn)的MBR信息。從而實(shí)現(xiàn)全局索引與局部索引的關(guān)聯(lián)。全局索引的構(gòu)建在所有局部索引構(gòu)建完成之后進(jìn)行。由于分區(qū)數(shù)量不會(huì)過多。因此全局索引的大小不會(huì)過大，不需要分布式執(zhí)行。全局索引采用常規(guī)的R樹生成方式即可。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)借助虛擬機(jī)搭建了具有6個(gè)節(jié)點(diǎn)的Ha?doop集群，每個(gè)節(jié)點(diǎn)分配4G內(nèi)存和一定SQL數(shù)據(jù)庫的硬盤，節(jié)點(diǎn)上運(yùn)行Ununtu14.0操作系統(tǒng)以及Hadoop2.6.4，并支持Linux下Java8的操作環(huán)境Ha?doop集群中包括1個(gè)Master和5個(gè)Slave，Master主要負(fù)責(zé)數(shù)據(jù)的整體調(diào)度，Slave作為具體的執(zhí)行者負(fù)責(zé)存儲(chǔ)數(shù)據(jù)和處理數(shù)據(jù)。

5.2 區(qū)域查詢實(shí)驗(yàn)

由于本文索引采用多級(jí)分布式索引結(jié)構(gòu)，因此在進(jìn)行區(qū)域查詢時(shí)與普通單機(jī)SQL數(shù)據(jù)庫索引查詢操作不同。在區(qū)域查詢操作中首先通過全局索引將SQL數(shù)據(jù)庫查詢操作劃分到不同的數(shù)據(jù)節(jié)點(diǎn)中進(jìn)行查詢，最終將數(shù)據(jù)節(jié)點(diǎn)中查詢到的數(shù)據(jù)聚合為最終的數(shù)據(jù)。

實(shí)驗(yàn)使用谷歌地圖數(shù)據(jù)集［17］，大小約為9.3G，查詢范圍由0.0001%～1%變化，分別選取工作節(jié)點(diǎn)數(shù)目為2、4、6和單機(jī)狀態(tài)，測試節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)查詢時(shí)間的影響。實(shí)驗(yàn)數(shù)據(jù)如圖4所示。

圖4 區(qū)域查詢實(shí)驗(yàn)結(jié)果

由圖4可得出，當(dāng)查詢區(qū)域特別小時(shí)，單機(jī)狀態(tài)下查詢所需時(shí)間并沒有明顯劣勢(shì)，但是隨著查詢區(qū)域的擴(kuò)大，查詢操作耗時(shí)呈指數(shù)型增長，這是因?yàn)閱闻_(tái)計(jì)算機(jī)本身性能有限。通過對(duì)比2、4、6個(gè)工作節(jié)點(diǎn)的查詢耗時(shí)，可看出相同數(shù)據(jù)量、相同查詢區(qū)域的情況下，數(shù)據(jù)查詢時(shí)間隨著工作節(jié)點(diǎn)的增多而減少，這是因?yàn)榫唧w的查詢操作被分配到了數(shù)據(jù)節(jié)點(diǎn)中執(zhí)行，提高了檢索性能。由此得出，本文設(shè)計(jì)的分布式SQL數(shù)據(jù)庫索引提高了檢索性能，適用于處理海量數(shù)據(jù)。

5.3 k近鄰查詢實(shí)驗(yàn)

k近鄰查詢的基本思想是，給定一個(gè)參考點(diǎn)的坐標(biāo)，查詢離該點(diǎn)最近的k個(gè)數(shù)據(jù)。基于本文索引的k臨近查詢操作共分為3個(gè)步驟分別為全局knn操作，局部knn操作，局部knn結(jié)果檢查合并。其中全局knn操作由于計(jì)算量較小在Master節(jié)點(diǎn)執(zhí)行即可。局部knn操作和檢查在Map階執(zhí)行。結(jié)果合并階段在Reduce中執(zhí)行。

實(shí)驗(yàn)同樣使用谷歌地圖數(shù)據(jù)集，大小約為9.3G，n的范圍從1～10000變化，實(shí)驗(yàn)隨機(jī)選取若干點(diǎn)進(jìn)行多次實(shí)驗(yàn)，取最終的平均值，實(shí)驗(yàn)分別選取工作節(jié)點(diǎn)數(shù)目為2、4、6和單機(jī)狀態(tài)，測試節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)查詢時(shí)間的影響。實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

如圖5所示在k近鄰查詢實(shí)驗(yàn)中隨著k值的增加，查詢耗時(shí)也在增加。這是因?yàn)閗值越大，需要檢索的范圍越大，查詢操作耗費(fèi)的時(shí)間也就越多，并且耗時(shí)增幅越明顯。這是由于在k值比較小時(shí)，集群并未發(fā)揮全部性能。因此小幅度增大k值，查詢所需時(shí)間增長幅度較小。然而當(dāng)k值增大到一定程度，集群已經(jīng)發(fā)揮全部性能，此時(shí)繼續(xù)增長k值，查詢操作耗時(shí)就會(huì)出現(xiàn)線性增長的狀況。當(dāng)k值較大時(shí)k近鄰查詢所需時(shí)間隨著工作節(jié)點(diǎn)數(shù)量的增加而減小，而當(dāng)k值較小時(shí)，查詢操作的耗時(shí)幾乎不受節(jié)點(diǎn)數(shù)量的影響。這證實(shí)了n值較小時(shí)，k近鄰查詢只在比較少的節(jié)點(diǎn)中進(jìn)行。而當(dāng)k值較大時(shí)，k近鄰查詢將在集群所有節(jié)點(diǎn)中并行執(zhí)行。

圖5 k近鄰查詢實(shí)驗(yàn)結(jié)果

6 結(jié)語

由于傳統(tǒng)的單機(jī)SQL數(shù)據(jù)庫索引技術(shù)面對(duì)大規(guī)模數(shù)據(jù)時(shí)計(jì)算能力不足，索引效率低，因此本文還將SQL數(shù)據(jù)庫索引技術(shù)與云計(jì)算技術(shù)相結(jié)合，提出了基于Hadoop平臺(tái)的分布式SQL數(shù)據(jù)庫索引。本文從索引結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)劃分、局部和全局索引構(gòu)建和存儲(chǔ)等方面，詳細(xì)闡述了分布式SQL數(shù)據(jù)庫索引的實(shí)現(xiàn)，最后搭建Hadoop平臺(tái)進(jìn)行了測試。在今后的研究工作中，重點(diǎn)會(huì)放在對(duì)R樹算法更好的優(yōu)化過程中。同時(shí)，本文主要是針對(duì)二維數(shù)據(jù)上的研究，日后的研究將不僅僅局限在二維數(shù)據(jù)上，將研究的目光擴(kuò)展到更高維上。

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

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

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

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

［5］翁海星，宮學(xué)慶，朱燕超，等.集群環(huán)境下分布式索引的實(shí)現(xiàn)［J］. 計(jì)算機(jī)應(yīng)用，2016，36（01）：1-7+12.

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

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

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

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

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

［11］趙輝，楊樹強(qiáng)，陳志坤，等.基于MapReduce模型的范圍查詢分析優(yōu)化技術(shù)研究［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（03）：606-617.

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

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

［14］昌春艷，王沁，田錕，等.優(yōu)化STR模型的實(shí)證研究［J］.武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2013，35（04）：565-569.

［15］施逸飛，熊岳山，謝智歌，等.基于多核學(xué)習(xí)的快速網(wǎng)格分割算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，27（11）：2031-2038.

［16］黃良韜，趙志誠，趙亞群.基于隨機(jī)森林的密碼體制分層識(shí)別方案［J］. 計(jì)算機(jī)學(xué)報(bào)，2017（07）：1-19.

［17］李艷霞，劉學(xué)，黨壽江，等.網(wǎng)管系統(tǒng)中基于谷歌地圖的拓?fù)淇梢暬瘜?shí)現(xiàn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（02）：681-685.