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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 快速查詢算法

2.2.1 建立索引表文件

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

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

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

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

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

c)讀出文件fi當(dāng)前位置的三個(gè)參數(shù):測(cè)點(diǎn)編號(hào)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個(gè)測(cè)點(diǎn)在某個(gè)時(shí)刻T的屬性數(shù)據(jù)，故n個(gè)分組主表文件都需要先后被讀取，為了提高查詢效率，必須通過(guò)索引表文件加快屬性數(shù)據(jù)的準(zhǔn)確定位。與測(cè)點(diǎn)維度查詢不同，時(shí)間維度的查詢需要查詢所有測(cè)點(diǎn) ，為提高查找索引表文件的效率，必須先將索引表文件導(dǎo)入內(nèi)存建立索引，然后通過(guò)查詢內(nèi)存索引表來(lái)提高查詢效率。如果要查詢所有測(cè)點(diǎn)在時(shí)刻T的屬性數(shù)據(jù)，則其查詢過(guò)程如下。

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

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

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

a)計(jì)算測(cè)點(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ù)測(cè)點(diǎn)維度的查詢

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

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

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

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

3 算法改進(jìn)

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

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

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

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

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

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

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

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

4 算法測(cè)試

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

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

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

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

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

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

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

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

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

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

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

5 算法分析

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

表5 算法查詢效率的比較

表6 算法存儲(chǔ)效率的比較

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

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

［6］杜方，陳躍國(guó)，杜小勇.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］.無(wú)線電通信技術(shù)，2013，39(1):73-76.

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

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