基于批量提交數(shù)據(jù)的快速查詢算法研究與設計

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

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

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

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

此外，所有的批量數(shù)據(jù)都必須保存在磁盤上，這就要求盡可能地節(jié)省磁盤空間。在實際的數(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ù)的索引算法，通過該算法，實現(xiàn)了測點參數(shù)與屬性數(shù)據(jù)的分離，其中測點參數(shù)作為索引文件的內(nèi)容，而所有的屬性數(shù)據(jù)存儲在數(shù)據(jù)文件中，通過搜索索引文件可以很快地找到需要的屬性數(shù)據(jù)。算法測試表明:通過索引文件查找屬性數(shù)據(jù)文件，可以很好的解決下列問題:①實現(xiàn)批量提交數(shù)據(jù)在測點維度的快速查詢;②實現(xiàn)批量提交數(shù)據(jù)在時間維度的快速查詢;③實現(xiàn)單一測點在一段時間內(nèi)的快速查詢;④實現(xiàn)批量測點在某個時刻的快速查詢。

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

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

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

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

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

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

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

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

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

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

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

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

2.2 快速查詢算法

2.2.1 建立索引表文件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法改進

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

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

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

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

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

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

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

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

4 算法測試

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

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

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

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

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

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

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

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

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

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

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

5 算法分析

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

表5 算法查詢效率的比較

表6 算法存儲效率的比較

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

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

6 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

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