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

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

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

?

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

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

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

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

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

隨著電力信息通信與電力生產(chǎn)以及企業(yè)經(jīng)營管理的深度融合，以及物聯(lián)網(wǎng)和云計算為代表的新一代IT技術(shù)在電力行業(yè)中的廣泛應(yīng)用，電力行業(yè)中數(shù)據(jù)量呈指數(shù)級增長，也使數(shù)據(jù)來源更加多元化和復雜化[1]。電力大數(shù)據(jù)不僅反映行業(yè)內(nèi)部規(guī)律特征，指導電力生產(chǎn)和企業(yè)經(jīng)營管理，還反映經(jīng)濟社會發(fā)展狀況，是未來電力發(fā)展的重要參考依據(jù)。在對海量的信息檢索時，準確度、高效性、個性化需求等已成為信息檢索的新要求，索引的建立是提高檢索系統(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ù)的特點，在設(shè)計索引結(jié)構(gòu)時對不同數(shù)據(jù)類型的數(shù)據(jù)創(chuàng)建不同結(jié)構(gòu)的索引。首先根據(jù)電力數(shù)據(jù)的屬性建立第一層索引。其次對上層屬性所對應(yīng)的屬性值建立索引，如果是數(shù)值類型數(shù)據(jù)就建立B+樹索引，如果是字符型數(shù)據(jù)就建立倒排索引。這樣，不是所有的數(shù)據(jù)都建立樹型索引避免了由結(jié)點分裂所引起的時間開銷問題，除此之外，也減少了結(jié)點分裂的臨時結(jié)點所占的用額外存儲空間。當該索引構(gòu)建完成后進行數(shù)值型數(shù)據(jù)范圍檢索時，就會直接由下層的樹形索引部分完成，減小檢索時間和成本。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)Map過程。

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

表1 Map過程算法

(2)Combine過程

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

表2 Combine過程算法

(3)Reduce過程

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

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

3 實驗分析與驗證

3.1 混合索引的有效性驗證

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

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

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

(1)

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

(2)

則所有分裂結(jié)點的個數(shù)總共有：

(3)

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

(4)

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

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

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

logkn1+logm(n1×n2) .

(5)

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

logkn3+logm(n3×n4) .

(6)

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

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

(7)

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

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

3.2 分布式索引實驗驗證

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

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

表3 實驗數(shù)據(jù)對比分析

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

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

[2] 張文燚，項連志，王小芳.支持高效查詢檢索的大數(shù)據(jù)資源描述模型[J].哈爾濱工程大學學報，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].計算機工程，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].計算機學報，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ù)研究與實現(xiàn)[J].計算機科學，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].東北電力大學學報，2015，35(1)：73-77.

[15] 郭曉利，朝嘯.電網(wǎng)知識協(xié)同發(fā)現(xiàn)策略研究[J].東北電力大學學報，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-)，男，吉林省吉林市人，東北電力大學信息工程學院教授，博士，主要研究方向：電力信息化、計算機網(wǎng)絡(luò)技術(shù).

1005-2992(2016)05-0080-06

TP29

A