曲朝陽，孫立擎 ，許劭慶，藺樹全，尹相愛

(1.東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012；2.國網(wǎng)吉林省電力有限公司 信息通信公司，吉林 吉林 132012；3.國網(wǎng)吉林省電力有限公司 吉林供電公司，吉林 吉林 132012)

?

基于B+樹的電力大數(shù)據(jù)分布式索引

曲朝陽1，孫立擎1，許劭慶2，藺樹全3，尹相愛3

(1.東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012；2.國網(wǎng)吉林省電力有限公司 信息通信公司，吉林 吉林 132012；3.國網(wǎng)吉林省電力有限公司 吉林供電公司，吉林 吉林 132012)

隨著電力信息化的發(fā)展，電力數(shù)據(jù)來源廣泛，具備體量大、類型多的特點(diǎn)，其中設(shè)備監(jiān)測數(shù)據(jù)以及業(yè)務(wù)數(shù)據(jù)大多是浮點(diǎn)型、字符型數(shù)據(jù)，具有一定的時(shí)序性和結(jié)構(gòu)化的特點(diǎn)。在數(shù)據(jù)檢索時(shí)可能是對不同類型數(shù)據(jù)的聯(lián)合查詢，同時(shí)在大規(guī)模數(shù)據(jù)檢索時(shí)存在查詢效率不高，檢索結(jié)果無法滿足跨范圍匹配的問題，對此本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于B+樹和倒排索引的分布式混合索引結(jié)構(gòu)，引入層次化很合索引的思想，將數(shù)據(jù)集中的數(shù)據(jù)屬性和屬性值劃分開來，并實(shí)現(xiàn)索引的并行化，提高了數(shù)據(jù)的索引構(gòu)建時(shí)間和檢索速度。

電力大數(shù)據(jù)，檢索，分布式索引

隨著電力信息通信與電力生產(chǎn)以及企業(yè)經(jīng)營管理的深度融合，以及物聯(lián)網(wǎng)和云計(jì)算為代表的新一代IT技術(shù)在電力行業(yè)中的廣泛應(yīng)用，電力行業(yè)中數(shù)據(jù)量呈指數(shù)級增長，也使數(shù)據(jù)來源更加多元化和復(fù)雜化[1]。電力大數(shù)據(jù)不僅反映行業(yè)內(nèi)部規(guī)律特征，指導(dǎo)電力生產(chǎn)和企業(yè)經(jīng)營管理，還反映經(jīng)濟(jì)社會發(fā)展?fàn)顩r，是未來電力發(fā)展的重要參考依據(jù)。在對海量的信息檢索時(shí)，準(zhǔn)確度、高效性、個(gè)性化需求等已成為信息檢索的新要求，索引的建立是提高檢索系統(tǒng)存儲效率和系統(tǒng)檢索性能、加快數(shù)據(jù)查詢速度的重要技術(shù)手段之一[2]，針對大規(guī)模數(shù)據(jù)檢索查詢效率不高、檢索結(jié)果無法滿足跨范圍匹配的問題，本文提出了一種適合電力大數(shù)據(jù)的分布式索引結(jié)構(gòu)。

1 混合索引構(gòu)建

1.1 構(gòu)建思想

針對電力數(shù)據(jù)的特點(diǎn)，在設(shè)計(jì)索引結(jié)構(gòu)時(shí)對不同數(shù)據(jù)類型的數(shù)據(jù)創(chuàng)建不同結(jié)構(gòu)的索引。首先根據(jù)電力數(shù)據(jù)的屬性建立第一層索引。其次對上層屬性所對應(yīng)的屬性值建立索引，如果是數(shù)值類型數(shù)據(jù)就建立B+樹索引，如果是字符型數(shù)據(jù)就建立倒排索引。這樣，不是所有的數(shù)據(jù)都建立樹型索引避免了由結(jié)點(diǎn)分裂所引起的時(shí)間開銷問題，除此之外，也減少了結(jié)點(diǎn)分裂的臨時(shí)結(jié)點(diǎn)所占的用額外存儲空間。當(dāng)該索引構(gòu)建完成后進(jìn)行數(shù)值型數(shù)據(jù)范圍檢索時(shí)，就會直接由下層的樹形索引部分完成，減小檢索時(shí)間和成本。

B+樹由于葉子結(jié)點(diǎn)的有序性保證了它對數(shù)值型數(shù)據(jù)檢索時(shí)具有優(yōu)勢，在進(jìn)行數(shù)據(jù)查找時(shí)具有穩(wěn)定的I/O開銷，較好的支持索引更新。同時(shí)其索引層次能夠保持與數(shù)據(jù)文件大小相適應(yīng)[3，4]；倒排索引對完成數(shù)值型數(shù)據(jù)的范圍檢索不能提供很好地支持，但索引的實(shí)現(xiàn)相對簡單、查詢速度快，檢索可以一次定位，對字符型數(shù)據(jù)的索引構(gòu)建提供良好的支持?；旌纤饕Y(jié)合用并延續(xù)了B+樹和倒排索引兩種結(jié)構(gòu)的優(yōu)點(diǎn)，同時(shí)又避開了這兩種結(jié)構(gòu)各自的不足。在達(dá)到提高索引創(chuàng)建速度和空間利用率的同時(shí)還能滿足數(shù)值型數(shù)據(jù)的范圍查詢需求。

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

根據(jù)上述索引的構(gòu)建思想，本文設(shè)計(jì)的電力大數(shù)據(jù)索引結(jié)構(gòu)如圖1所示：

圖1 索引結(jié)構(gòu)

第一層樹形索引結(jié)構(gòu)是為要建立索引的數(shù)據(jù)對象所包含的屬性建立的，其中所有的具體屬性都存儲在非葉子結(jié)點(diǎn)中，而B+樹的所有葉子結(jié)點(diǎn)中存儲三部分信息Ai、PType、Pointer，表示的含義分別為：

(1)Ai是索引對象的數(shù)據(jù)屬性，其中n為數(shù)據(jù)集中所包含的所有屬性個(gè)數(shù)，i∈[1，n]；

(2)PType表示指針類型，具體類型有PType { Inverted _ index，B+-tree }；

(3)Pointer指針，指向第二層索引，根據(jù)屬性值的不同數(shù)據(jù)類型，該指針指向不同的索引結(jié)構(gòu)，即指向倒排表表頭或B+樹的根結(jié)點(diǎn)。

第二層索引是為各個(gè)屬性值建立的索引，包括為數(shù)值型數(shù)據(jù)建立的B+樹索引結(jié)構(gòu)和為字符型數(shù)據(jù)建立的倒排表索引結(jié)構(gòu)。其中B+樹索引結(jié)構(gòu)的非葉子結(jié)點(diǎn)只包含具體的數(shù)據(jù)值，葉子結(jié)點(diǎn)都是有序排列的且每個(gè)葉子結(jié)點(diǎn)中都包含三部分信息ARVS、Loc、Doc，表示的含義分別是：

(1)ARVS為第R個(gè)屬性的第S個(gè)屬性值，R∈[1，n2]、S∈[1，p]，n2為數(shù)據(jù)集中包含的數(shù)值屬性的個(gè)數(shù)，P為第R個(gè)屬性的屬性值的個(gè)數(shù)。

(2)Loc為包含此屬性值的文件所在的位置信息。

(3)Doc為包含此屬性值的文件編號，每個(gè)文件編號是唯一的。

倒排索引分為兩個(gè)部分，一個(gè)是由不同的關(guān)鍵詞組成的索引表，稱為詞典，其中保存了各種中文關(guān)鍵字以及這些詞匯所對應(yīng)的統(tǒng)計(jì)信息。另一個(gè)部分是由每個(gè)索引詞出現(xiàn)過的文檔集合，及其位置信息組成，也稱為記錄表。第二層的倒排索引結(jié)構(gòu)中具體包含AiVj、Doc、Loc、F四部分信息，表示的含義分別為：

(1)AiVj為第i個(gè)屬性的第j個(gè)屬性值，i∈[1，n1]、j∈[1，m]，n1為字符屬性的個(gè)數(shù)，m為第i個(gè)屬性包含的屬性值的個(gè)數(shù)。

(2)Doc為所查詢條件的屬性值所在的文件編號，每個(gè)文件編號唯一。

(3)Loc為包含查詢關(guān)鍵詞的文件所在的位置信息。

(4)F為查詢關(guān)鍵詞在文件中出現(xiàn)的頻率。

2 索引的并行化實(shí)現(xiàn)

隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，使得對數(shù)據(jù)的檢索查詢也越來越復(fù)雜，采用集中式處理方法具有檢索速度慢、容易出現(xiàn)訪問瓶頸、可擴(kuò)展性不強(qiáng)等多方面的不足[5]。分布式技術(shù)以其特有的高性能數(shù)據(jù)處理特點(diǎn)，正逐漸成為解決這類復(fù)雜問題的有效手段。分布式索引在邏輯上是一個(gè)統(tǒng)一的整體，在物理上則是分別存儲在不同的物理結(jié)點(diǎn)機(jī)上[6]。如圖2所示。

圖2 分布式索引物理結(jié)構(gòu)

本文實(shí)現(xiàn)索引的并行化的主要思想是將上述混合索引分布式地存儲在各個(gè)服務(wù)器上，且客戶端保留所有這些索引節(jié)點(diǎn)的副本。在實(shí)際存儲數(shù)據(jù)的物理節(jié)點(diǎn)上建立本地索引，然后在服務(wù)器端建立全局索引。全局索引采用倒排索引結(jié)構(gòu)，將本地索引以關(guān)鍵字的形式存儲在全局索引中，當(dāng)用戶查詢數(shù)據(jù)時(shí)，通過服務(wù)器端的全局索引定位到本地索引，進(jìn)行數(shù)據(jù)查詢。

利用MapReduce編程模型在Hadoop平臺上編程實(shí)現(xiàn)分布式索引的構(gòu)建，一個(gè)MapReduce作業(yè)一般由Map、Combine和Reduce三個(gè)過程構(gòu)成，這三個(gè)過程都以作為輸入和輸出[7，8]。

(1)Map過程。

以不同的文檔作為輸入數(shù)據(jù)，通過調(diào)用Map函數(shù)，把輸入的數(shù)據(jù)按照文檔ID自動(dòng)分割成N片，并以key-value對的形式分發(fā)到不同的TaskTracker節(jié)點(diǎn)上，使得輸入的數(shù)據(jù)能在多個(gè)節(jié)點(diǎn)上同時(shí)進(jìn)行處理。具體算法如表1所示：

表1 Map過程算法

(2)Combine過程

Combine過程以上述的Map操作所產(chǎn)生的結(jié)果作為自己的輸入。Combine過程主要將輸入的key-value鍵值對中Key值相同的Value進(jìn)行累加計(jì)算，實(shí)現(xiàn)了關(guān)鍵字在各自文檔中詞頻統(tǒng)計(jì)的功能。具體算法過程如表2所示：

表2 Combine過程算法

(3)Reduce過程

Reduce過程將所有Combine操作所產(chǎn)生的結(jié)果作為自己的輸入，然后對輸入序列中相同Key值的Value進(jìn)行字符串處理，使之組合形成索引格式中文檔信息部分的內(nèi)容。

最后，Reduce操作將相同關(guān)鍵字的所有<文檔名：詞頻>值進(jìn)行連接合并計(jì)算，最終形成鍵值對，其格式為<關(guān)鍵字，文檔0：詞頻；文檔1：詞頻，…>，然后將結(jié)果輸出為索引文件并存儲到HDFS文件系統(tǒng)中。

3 實(shí)驗(yàn)分析與驗(yàn)證

3.1 混合索引的有效性驗(yàn)證

索引構(gòu)建的好壞將直接影響到數(shù)據(jù)的組織效果和查詢效率，本文提出的雙層混合索引結(jié)構(gòu)在有效性驗(yàn)證時(shí)，分別從索引構(gòu)建的時(shí)間性能和數(shù)據(jù)的查詢效率上進(jìn)行了比較和分析[9，10]。

(1)時(shí)間性能分析與比較

設(shè)n1、n2分別為數(shù)值型屬性個(gè)數(shù)和每個(gè)屬性的屬性值的平均個(gè)數(shù)，n3、n4分別為字符型屬性的個(gè)數(shù)以及每個(gè)屬性包含的屬性值的平均個(gè)數(shù)。則所有的屬性值的個(gè)數(shù)為N=n1×n2+n3×n4。設(shè)第一層B+樹索引結(jié)構(gòu)的階為k，第二層B+樹索引結(jié)構(gòu)的階為m[11-12]。此時(shí)第一層B+樹索引需要進(jìn)行分裂的結(jié)點(diǎn)就有FBdiv個(gè)，由公式(1)計(jì)算得出：

(1)

第二層B+樹的高度為logmn2，假設(shè)所有非葉子結(jié)點(diǎn)都有m個(gè)子結(jié)點(diǎn)。此時(shí)B+樹要進(jìn)行分裂的節(jié)點(diǎn)有SBdiv個(gè)，由公式(2)計(jì)算得出：

(2)

則所有分裂結(jié)點(diǎn)的個(gè)數(shù)總共有：

(3)

如果數(shù)據(jù)集的整個(gè)索引都采用傳統(tǒng)的B+樹結(jié)構(gòu)進(jìn)行索引[13-14]，即為所有的屬性值都建立樹形索引結(jié)構(gòu)，則分裂節(jié)點(diǎn)的總個(gè)數(shù)為：

(4)

將公式(3)和公式(4)進(jìn)行比較可知，本文設(shè)計(jì)的混合索引結(jié)構(gòu)在索引創(chuàng)建時(shí)間上相對單一索引結(jié)構(gòu)而言具有較為明顯的優(yōu)越性。

(2)查詢效率分析與比較

如果按檢索條件查詢返回的結(jié)果為數(shù)值型屬性時(shí)[13]，在上述混合索引結(jié)構(gòu)中其算法查找的時(shí)間復(fù)雜度約為：

logkn1+logm(n1×n2) .

(5)

如果查找條件返回的結(jié)果為字符型屬性時(shí)，在上述混合索引結(jié)構(gòu)中其算法查找的時(shí)間復(fù)雜度約為：

logkn3+logm(n3×n4) .

(6)

那么該混合索引結(jié)構(gòu)的查找時(shí)間復(fù)雜度介于公式(5)和公式(6)之間。如果采用傳統(tǒng)的全部B+樹結(jié)構(gòu)索引，無論是查找數(shù)值類型屬性數(shù)據(jù)還是字符類型屬性的數(shù)據(jù)，其查找的時(shí)間復(fù)雜度都約為：

logk(n1+n3)+logm(n1×n2+n3×n4) .

(7)

查找數(shù)值屬性的數(shù)據(jù)時(shí)將公式(5)和公式(7)進(jìn)行比較，可以看出B+樹索引的查找效率明顯低于混合索引結(jié)構(gòu)的查詢效率。公式(6)和公式(7)兩者的大小與m的取值范圍有關(guān)。當(dāng)m=2時(shí)，公式(7)的值大于公式(6)，即在查找字符型屬性數(shù)據(jù)時(shí)本文提出的索引結(jié)構(gòu)查詢效率較高。

通過上述在理論上的性能分析與比較，表明本文設(shè)計(jì)的索引具有更有效的空間利用率和更高的檢索性能[14-15]。

3.2 分布式索引實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)中采用實(shí)驗(yàn)室局域網(wǎng)中的四臺計(jì)算機(jī)來模擬分布式計(jì)算平臺，每臺機(jī)器的通信帶寬為10 Mbps，處理器為Inter(R) Core(TM) i5 CPU，2.40 HZ，內(nèi)存2.00 GB，硬盤320 GB，每臺計(jì)算機(jī)間通過一臺以太網(wǎng)交換機(jī)相連。使用其中一臺作為NameNode節(jié)點(diǎn)，四臺均作為DataNode節(jié)點(diǎn)參與計(jì)算。

在軟件方面，在四臺計(jì)算機(jī)中安裝Linux操作系統(tǒng)，并且搭建了Hadoop集群環(huán)境，采用Java編程環(huán)境實(shí)現(xiàn)索引方案。實(shí)驗(yàn)通過對不同數(shù)據(jù)量分別在分布式環(huán)境和單機(jī)環(huán)境的檢索時(shí)間進(jìn)行比較來驗(yàn)證本索引方案的有效性。實(shí)驗(yàn)數(shù)據(jù)是釆用的是500M數(shù)據(jù)量以及1.0G數(shù)據(jù)量的風(fēng)電數(shù)據(jù)集和設(shè)備狀態(tài)檢修數(shù)據(jù)集中數(shù)據(jù)序列進(jìn)行索引，選擇平均風(fēng)速、平均有功功率、總發(fā)電量最大值、平均環(huán)境溫度、設(shè)備檢修記錄等10個(gè)屬性，選取的屬性中既包含數(shù)值型數(shù)據(jù)也包含字符型數(shù)據(jù)，隨機(jī)抽取1000條序列進(jìn)行數(shù)據(jù)檢索測試，具體的實(shí)驗(yàn)結(jié)果如表3所示：

表3 實(shí)驗(yàn)數(shù)據(jù)對比分析

上表中的數(shù)據(jù)量是部分原始數(shù)據(jù)量，由實(shí)驗(yàn)數(shù)據(jù)可以看出，隨著數(shù)據(jù)量和搜索序列的增加，搜索時(shí)間會呈現(xiàn)線性的增長，而且還會因?yàn)閮?nèi)存空間的限制而無法操作，表中的“-”表示的是內(nèi)存限制，無法進(jìn)行操作的標(biāo)志。但是分布式模式下在同等數(shù)據(jù)量的情況下，分布式索引具有明顯的優(yōu)勢，在時(shí)間和空間上都有較好的表現(xiàn)。

[1] 黃斌，彭宇行，彭小寧.云計(jì)算中海量數(shù)據(jù)高效索引方法[J].計(jì)算機(jī)應(yīng)用究，2014，29(10)：3075-3077.

[2] 張文燚，項(xiàng)連志，王小芳.支持高效查詢檢索的大數(shù)據(jù)資源描述模型[J].哈爾濱工程大學(xué)學(xué)報(bào)，2014，35(5)：594-601.

[3] Wang J B，Wu S，Gao H，et al.Indexing Multi-dimensional Data Base on DB-tree in a Cloud System[C].Proceedings of the SIGMOD Conference.Indianapolis，2010:591-602.

[4] 長孫妮妮，張毅坤，華燈鑫，等.一種基于B+樹的混合索引結(jié)構(gòu)[J].計(jì)算機(jī)工程，2012，38(14)：35-37，40.

[5] Chen D W，Zhuang J.A Real Time Index Model for Big Data Based on DC-Tree[C].International Conference on Advanced Cloud and Big Data，2013:99-104.

[6] C.Zhang，F(xiàn).Wang.A multilevel approach for learning from labeled and unlabeled data on graphs[J].Pattern Recognition，2010，43(6):2301-2314.

[7] Wang J，Zhang Y，Gao Y.pLSM:A Highly Efficient LSM-Tree Index Supporting Real-Time BigData Analysis[C].IEEE 37th Annual Computer Software and Applications Conference，2013:240-245.

[8] 丁琳琳，信俊昌，王國仁，等.基于Map-Reduce的海量數(shù)據(jù)高效Skyline查詢處理[J].計(jì)算機(jī)學(xué)報(bào)，2011，34(10)：1785-1796.

[9] Lin J，Dyer C.Data-Itensive Text Processing with MapReduce[M].California:Morgan and Claypool Publishers，2010:24-25.

[10] Peter M，Barcelona S.Distributed indexing for semantic search[C].In:Proc.of the 3rd Int’l Semantic Search Workshop.New York:ACM，2010：1-4.

[11] 吳煒，蘇永紅，李瑞軒，等.基于DHT的分布式索引技術(shù)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)，2010，37(2)：65-70.

[12] Hsu YT，Pan YC，Wei LY，Peng WC，Lee WC.Key formulation schemes for spatial index in cloud data managements[C].In:Proc.of the 13th IEEE Conf.on Mobile Data Management.Washington:IEEE Computer Society，2012：21-26.

[13] Diana M，Denis S，Gylfi G，Laurent A.Indexing and searching 100M images with map-reduce[C].In:Proc.of the 3rd ACM Conf.on Int’l Conf.on Multimedia Retrieval.New York:ACM，2013：17-24.

[14] 曲朝陽，張率，劉洪濤.基于用電影響因素回歸的小區(qū)用電預(yù)測模型[J].東北電力大學(xué)學(xué)報(bào)，2015，35(1)：73-77.

[15] 郭曉利，朝嘯.電網(wǎng)知識協(xié)同發(fā)現(xiàn)策略研究[J].東北電力大學(xué)學(xué)報(bào)，2014，34(1)：94-96.

Power Big Data Distributed Index Based on B+ Tree And Inverted Index

QU Zhao-yang1，SUN Li-qing1，XU Shao-qing2，LIN Shu-quan3，YIN Xiang-ai3

(1.College of Information Engineering，Northeast Dianli University，Jilin Jilin 132012；2.Information and communication company in Jilin Electric Power Corporation Limited，Jilin Jilin 132012；3.State Grid Jilin Electric Power Co.，Ltd.Jilin power supply company，Jilin Jilin 132012)

With the development of electric power information technology，electric power data comes from a variety of sources，and have the characteristics of large volume and a lot of types，equipment monitoring data and business data mostly floating-point type，character type，has the characteristics of sequential and structured.In the data retrieval，it is possible to combine the different types of data，the query efficiency is not high According to the characteristics of electric power data，this paper proposes a distributed hybrid index structure based on inverted index and B+-Tree，introducing the idea of hierarchical indexing，the data stream contains attributes and attribute values separated to improve the retrieval speed.

Power big data；Search；Distributed index

2016-04-12

曲朝陽(1964-)，男，吉林省吉林市人，東北電力大學(xué)信息工程學(xué)院教授，博士，主要研究方向：電力信息化、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù).

1005-2992(2016)05-0080-06

TP29

A