譚 威，王防修，石文文，付威威

(武漢輕工大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北武漢 430023)

二維數(shù)據(jù)主要來自于一類按照時(shí)間周期返回?cái)?shù)據(jù)的傳感器［1］，這類傳感器會被安裝在需要實(shí)時(shí)監(jiān)控的設(shè)備上，比如儀表盤、鍋爐等，通過傳感器適時(shí)傳回監(jiān)測設(shè)備提交的屬性數(shù)據(jù)。又比如某一時(shí)刻的溫度、鍋爐的壓力等，系統(tǒng)可以完整地記錄下監(jiān)測設(shè)備的整個運(yùn)行狀況，在監(jiān)控現(xiàn)場出現(xiàn)異常狀況時(shí)可以通過監(jiān)測設(shè)備提交的歷史記錄進(jìn)行故障定位和故障分析。當(dāng)前的應(yīng)用發(fā)展趨勢表明，被監(jiān)測個體的數(shù)目正在迅速增長，同時(shí)隨著技術(shù)的進(jìn)步以及應(yīng)用的需求，數(shù)據(jù)回傳的周期也越來越短，這就要求對眾多監(jiān)測設(shè)備提交的大量數(shù)據(jù)能夠適時(shí)存儲［2-5］和快速查詢［6-10］。

所稱批量提交數(shù)據(jù)，就是指應(yīng)用環(huán)境中每個測點(diǎn)在一段時(shí)間內(nèi)提交了大量數(shù)據(jù)。監(jiān)測設(shè)備數(shù)量越多，則所有測點(diǎn)在一段時(shí)間內(nèi)批量提交的數(shù)據(jù)量就越大。雖然每個設(shè)備采樣周期固定，但不同設(shè)備的采樣周期會有不同。因此，如何對監(jiān)測設(shè)備提交的批量數(shù)據(jù)進(jìn)行快速查詢是監(jiān)控系統(tǒng)適時(shí)處理問題的關(guān)鍵。

此外，所有的批量數(shù)據(jù)都必須保存在磁盤上，這就要求盡可能地節(jié)省磁盤空間。在實(shí)際的數(shù)據(jù)處理中，為了提高查詢效率，必須使，內(nèi)存和磁盤在容量上存在較大差距，要求降低索引之間的耦合度，內(nèi)存索引和磁盤索引能夠?qū)崿F(xiàn)快速切換，在較小內(nèi)存情況下也可以正常工作。降低數(shù)據(jù)和索引的耦合度，索引和數(shù)據(jù)分開存儲［11］。為了節(jié)省存儲空間，盡量使所提交的數(shù)據(jù)占盡可能少的外存空間。

總之，根據(jù)批量提交數(shù)據(jù)的結(jié)構(gòu)特征，本文提出了一種基于批量提交數(shù)據(jù)的索引算法，通過該算法，實(shí)現(xiàn)了測點(diǎn)參數(shù)與屬性數(shù)據(jù)的分離，其中測點(diǎn)參數(shù)作為索引文件的內(nèi)容，而所有的屬性數(shù)據(jù)存儲在數(shù)據(jù)文件中，通過搜索索引文件可以很快地找到需要的屬性數(shù)據(jù)。算法測試表明:通過索引文件查找屬性數(shù)據(jù)文件，可以很好的解決下列問題:①實(shí)現(xiàn)批量提交數(shù)據(jù)在測點(diǎn)維度的快速查詢;②實(shí)現(xiàn)批量提交數(shù)據(jù)在時(shí)間維度的快速查詢;③實(shí)現(xiàn)單一測點(diǎn)在一段時(shí)間內(nèi)的快速查詢;④實(shí)現(xiàn)批量測點(diǎn)在某個時(shí)刻的快速查詢。

1 批量數(shù)據(jù)存儲與查詢的數(shù)學(xué)模型

對于一個起始時(shí)刻為begin_time，采樣周期為time_gap，編號為ID的測點(diǎn)而言，為方便查詢，使該測點(diǎn)批量提交屬性數(shù)據(jù)的起始地址為

其中M表示每個測點(diǎn)提交的數(shù)據(jù)量，而size表示一個屬性數(shù)據(jù)的大小。

明確了屬性數(shù)據(jù)的存儲結(jié)構(gòu)以后，則查詢ID在時(shí)刻T提交的屬性數(shù)據(jù)時(shí)，該屬性數(shù)據(jù)在數(shù)據(jù)文件中的地址為

2 批量提交數(shù)據(jù)的快速查詢

2.1 批量提交數(shù)據(jù)的分組存儲策略

假設(shè)總共有N個測點(diǎn)，每個測點(diǎn)的采樣周期不一定相同。如果每個測點(diǎn)批量提交的屬性數(shù)據(jù)有M個，那么這些數(shù)據(jù)可以分組存儲到不同的主表文件中，也可以存儲在同一個主表文件中。此處采用分組存儲的方式保存批量數(shù)據(jù)。具體過程如下:

步驟1 根據(jù)距離的遠(yuǎn)近，將相對比較集中的測點(diǎn)歸為一組。假設(shè)N個測點(diǎn)被分為n組，且每組的測點(diǎn)個數(shù)為Ni，i=1，2，…，n，則滿足下列關(guān)系:

步驟3 初始化主表文件計(jì)數(shù)器i=1。

步驟4 用分組主表文件fi保存第i組測點(diǎn)批量提交的屬性數(shù)據(jù)，使得該文件的奇數(shù)行保存測點(diǎn)編號、數(shù)據(jù)提交的起始時(shí)刻、采樣周期三個參數(shù)，而偶數(shù)行保存對應(yīng)測點(diǎn)批量提交的M個屬性數(shù)據(jù)，而數(shù)據(jù)之間用空格隔開，則文件fi的數(shù)據(jù)總量為:

步驟5 如果i＜n，則使i=i+1，并重復(fù)步驟4。

最后，得到n個分組主表文件的數(shù)據(jù)量總和為:

2.2 快速查詢算法

2.2.1 建立索引表文件

設(shè)l1表示分組主表文件中奇數(shù)行三個參數(shù)的累加長度，l2表示偶數(shù)行數(shù)據(jù)的長度。則為N個測點(diǎn)建立索引的過程如下:

步驟1 初始化分組主表文件指示器i=1。

步驟2 讀分組主表文件fi的相關(guān)數(shù)據(jù)信息:

a)初始化測點(diǎn)計(jì)數(shù)器j=1和l1=0 l=1;

b)將fi的文件指針定位在l2(j－1)+l1;

c)讀出文件fi當(dāng)前位置的三個參數(shù):測點(diǎn)編號ID，起始時(shí)刻begin_time，采樣周期time_gap;

d)將begin_time，time_gap，l2(j－1)+l1保存在索引表文件Ind的第ID行;

e)如果j＜M，則j=j+1，重復(fù)b)至d)。

步驟3 如果i＜n，則i=i+1，且重復(fù)步驟2。

最后，得到索引表文件的數(shù)據(jù)量為i=3N。

2.2.2 批量數(shù)據(jù)在時(shí)間維度的快速查詢

由于要查詢N個測點(diǎn)在某個時(shí)刻T的屬性數(shù)據(jù)，故n個分組主表文件都需要先后被讀取，為了提高查詢效率，必須通過索引表文件加快屬性數(shù)據(jù)的準(zhǔn)確定位。與測點(diǎn)維度查詢不同，時(shí)間維度的查詢需要查詢所有測點(diǎn) ，為提高查找索引表文件的效率，必須先將索引表文件導(dǎo)入內(nèi)存建立索引，然后通過查詢內(nèi)存索引表來提高查詢效率。如果要查詢所有測點(diǎn)在時(shí)刻T的屬性數(shù)據(jù)，則其查詢過程如下。

步驟1 將索引表文件導(dǎo)入計(jì)算機(jī)內(nèi)存，建立索引表 Indi，i=1，2，…，N 。

步驟2 初始化分組主表文件指示器i=1和測點(diǎn)計(jì)數(shù)器j=1。

步驟3 查詢文件fi中所有測點(diǎn)在時(shí)刻T提交的屬性數(shù)據(jù):

a)計(jì)算測點(diǎn)Indj·ID在時(shí)刻T提交的數(shù)據(jù)位置

b)如果1≤loc≤M，則從文件fi讀屬性數(shù)據(jù)的物理地址為

c)如果文件fi未被讀完，則j=j+1，重復(fù)a)和b)。

步驟4 如果i＜n，表示分組文件未處理完，則i=i+1，重復(fù)步驟3。

2.2.3 批量數(shù)據(jù)測點(diǎn)維度的查詢

如果要查詢測點(diǎn)ID批量提交的屬性數(shù)據(jù)，則只需要使用索引表文件一次，故不需要將索引文件讀入計(jì)算機(jī)內(nèi)存。首先根據(jù)測點(diǎn)號ID所對應(yīng)的主表文件在起始時(shí)刻提交的屬性數(shù)據(jù)的地址，然后順序讀出該測點(diǎn)在不同時(shí)刻提交的屬性數(shù)據(jù)。具體的求解過程如下。

步驟1 從索引表文件的第ID行立即找到該測點(diǎn)的begin_time，time_gap，以及在分組主表文件中的起始地址address。

步驟2 通過順序查找或折半查找求出測點(diǎn)ID所在的分組主表文件fi。

步驟3 從文件fi的address開始依次讀入M個屬性數(shù)據(jù)。

3 算法改進(jìn)

3.1 批量數(shù)據(jù)的歸并存儲和索引表的建立

由于分組主表文件都是文本文件，為方便查詢，要求每個分組主表文件中的數(shù)據(jù)必須是等長的，這必然導(dǎo)致該算法的使用范圍受到限制。同時(shí)，用文本表示數(shù)據(jù)需要花費(fèi)更多的存儲空間。如果用一個二進(jìn)制主表文件保存全部屬性數(shù)據(jù)，則既擴(kuò)大了算法的使用范圍，又可以節(jié)省存儲空間。

對于n個測點(diǎn)而言，如果每個測點(diǎn)提交M個屬性數(shù)據(jù)，則總共要提交Mn個屬性數(shù)據(jù)。保存數(shù)據(jù)和建立索引表的過程如下。

1)對n個測點(diǎn)從1至n連續(xù)編號，然后在索引表文件中依次保存每個測點(diǎn)起始時(shí)間和采樣周期。

2)依次保存每個測點(diǎn)批量提交的屬性數(shù)據(jù)，則得到一個n×M的二維矩陣。因?yàn)槊總€屬性數(shù)據(jù)占4個字節(jié)，故數(shù)據(jù)文件大小為4Mn。

3)對于一個測點(diǎn)ID而言，直接從索引表文件的位置8(ID－1)讀取該測點(diǎn)的起始時(shí)間begin_time和采樣周期time_gap。同理，直接從主表文件的位置4M(ID－1)開始讀出該測點(diǎn)提交的所有屬性數(shù)據(jù)。

3.2 批量數(shù)據(jù)在時(shí)間維度和測點(diǎn)維度的查詢

在建立了索引表文件和主表文件后，接下來就是如何使用索引表文件快速地對主表文件進(jìn)行時(shí)間維度和測點(diǎn)維度的數(shù)據(jù)查詢問題。

4 算法測試

假設(shè)存在10 000個監(jiān)測設(shè)備，對每個設(shè)備使用隨機(jī)數(shù)方式產(chǎn)生10 000個屬性數(shù)據(jù)，每個設(shè)備采樣周期固定，不同設(shè)備的采樣周期在100至1 000之間隨機(jī)選擇，針對這些數(shù)據(jù)實(shí)現(xiàn)批量提交數(shù)據(jù)的快速查詢。本算法的測試數(shù)據(jù)由2013第二屆中國軟件杯設(shè)計(jì)大賽的第二題提供，可以從中國軟件杯的官網(wǎng)上直接下載得到。

針對現(xiàn)有的批量數(shù)據(jù)，進(jìn)行如下的實(shí)驗(yàn)。

1)測試單個測點(diǎn)在不同時(shí)刻提交的屬性數(shù)據(jù)，如表1所示。

2)測試所有測點(diǎn)在同一時(shí)刻提交的屬性數(shù)據(jù)，如表2所示。

3)測試單個測點(diǎn)在一段時(shí)間內(nèi)提交的屬性數(shù)據(jù)，如表3所示。

4)測試不同測點(diǎn)在同一時(shí)刻提交的屬性數(shù)據(jù)，如表4所示。

表1 測點(diǎn)維度查詢的部分結(jié)果

表2 部分測點(diǎn)在某個時(shí)刻的屬性數(shù)據(jù)

表3 單個測點(diǎn)在一段時(shí)間內(nèi)的查詢結(jié)果

表4 多個測點(diǎn)在某一個時(shí)刻的查詢結(jié)果

表1與表3的區(qū)別在于:前者反映的是一個測點(diǎn)在所有時(shí)刻提交的屬性數(shù)據(jù)，而后者是查詢一個測點(diǎn)在一段時(shí)間內(nèi)提交的屬性數(shù)據(jù)。表2與表4的區(qū)別在于:前者反映的是所有測點(diǎn)在某一時(shí)刻提交的屬性數(shù)據(jù)，而后者是查詢幾個不同測點(diǎn)在某一時(shí)刻提交的屬性數(shù)據(jù)。其中，表1和表2只給出少量的部分結(jié)果，受篇幅所限無法將其結(jié)果全部列舉。算法測試的主要目的是通過上述四個表反映出本算法的輸入和輸出。

5 算法分析

如果通過索引表文件查詢分組主表文件，則要求每個分組主表文件必須具有一定的格式:①除參數(shù)外，每行屬性數(shù)據(jù)的長度必須相同;②屬性數(shù)據(jù)之間的空格、必須相同;③屬性數(shù)據(jù)等長。如果分組主表文件不滿足這些格式要求，則無法通過直接查詢分組主表文件得到需要的屬性數(shù)據(jù);反之，即使能查詢到所需要的數(shù)據(jù)，但其查詢效率與存儲效率較低，如果采用改進(jìn)算法，則對二進(jìn)制主表文件的格式就沒有上述要求。將分組主表文件合并成一個二進(jìn)制主表文件，可以提高算法的查詢效率和存儲效率，具體的查詢效率如表5所示，存儲效率見表6。此外，與分組主表文件相比，屬性數(shù)據(jù)在二進(jìn)制主表文件中占用較小的內(nèi)存空間。

表5 算法查詢效率的比較

表6 算法存儲效率的比較

從表5可以看出，測點(diǎn)維度的查詢效率明顯高于時(shí)間維度的查詢。之所以會出現(xiàn)這種情況，完全是由主表文件的存儲結(jié)構(gòu)決定的。

表6中體現(xiàn)改進(jìn)后的算法所占磁盤空間是改進(jìn)前的一半，其中磁盤空間=主表+索引表。

6 結(jié)束語

鑒于批量提交數(shù)據(jù)在適時(shí)監(jiān)控系統(tǒng)中的存儲特性，本文研究了大批量數(shù)據(jù)存儲與查詢領(lǐng)域中一個較少關(guān)注的重要問題，即在眾多測點(diǎn)同一時(shí)刻提交大量數(shù)據(jù)的背景下，如何實(shí)現(xiàn)批量提交數(shù)據(jù)的快速查詢。在每個測點(diǎn)采樣周期固定的基礎(chǔ)上，采用數(shù)據(jù)位置索引的方式詳細(xì)描述了測點(diǎn)分類、數(shù)據(jù)存儲、索引建立等過程，設(shè)計(jì)了索引表與主表分開存儲的改進(jìn)算法。算例測試表明，使用改進(jìn)后的算法，可以使批量提交數(shù)據(jù)的查詢效率和存儲效率得到明顯提高。本文研究是在批量提交數(shù)據(jù)的條件下進(jìn)行的，需要考慮各測點(diǎn)在提交數(shù)據(jù)時(shí)的不同步性。然而，批量提交數(shù)據(jù)的存儲方式使得測點(diǎn)維度的查詢效率明顯高于時(shí)間維度的查詢?；诖?，如何提高時(shí)間維度的查詢效率，是筆者下一步研究的重點(diǎn)。此外，本文未來還將考慮重啟后批量提交數(shù)據(jù)的快速查詢問題。

［1］郝晉峰，康建設(shè).改進(jìn)的二進(jìn)制粒子群算法的傳感器優(yōu)化配置［J］.火力與指揮控制，2013，38(8):65-68.

［2］沃焱，韓國強(qiáng).一種海量傳感器數(shù)據(jù)存儲與查詢方法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，28(1).:89-93.

［3］苗雯娟，張曉利.基于SQLServer二進(jìn)制文件存儲技術(shù)的研究［J］.高等教育，2011，109(11):111-113.

［4］蔣濤，高云君 ，張彬.一種基于Hadoop的紡織海量生產(chǎn)數(shù)據(jù)存儲設(shè)計(jì)［J］.微型電腦應(yīng)用，2013，30(6):53-57.

［5］張潔.云計(jì)算環(huán)境下的數(shù)據(jù)存儲保護(hù)機(jī)制研究與仿真［J］.計(jì)算機(jī)仿真，2013，30(8):254-257.

［6］杜方，陳躍國，杜小勇.RDF數(shù)據(jù)查詢處理技術(shù)綜述［J］.軟件學(xué)報(bào)，2013，24(6):1222-1242.

［7］蔣濤，高云君，張彬.不確定數(shù)據(jù)查詢處理［J］.電子學(xué)報(bào)，2013，5(5):966-975.

［8］高志君，鄭純軍.基于空間索引的WSN數(shù)據(jù)查詢機(jī)制［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34(3).

［9］倪睿熙.一種基于JSON的異構(gòu)數(shù)據(jù)查詢方法［J］.無線電通信技術(shù)，2013，39(1):73-76.

［10］孫莉，李靜，劉國華.列存儲數(shù)據(jù)查詢中的連接策略優(yōu)化方法［J］.計(jì)算機(jī)研究與發(fā)展，2013，50(8):1647-1656.

［11］孫莉，李靜，劉國華.信息檢索中快速索引文件的設(shè)計(jì)研究［J］.計(jì)算機(jī)工程與科學(xué)，2011，104(2):427-429.