一種多對象時間序列數(shù)據(jù)存儲設(shè)計

摘 要：本文討論了在現(xiàn)有的數(shù)據(jù)存儲和索引技術(shù)的基礎(chǔ)上，結(jié)合固定周期產(chǎn)生狀態(tài)數(shù)據(jù)設(shè)備的檢測特點定義了一種存儲結(jié)構(gòu)和索引結(jié)構(gòu)，以獲得更高的空間利用率和查詢效率。首先深入分析狀態(tài)數(shù)據(jù)所具有的時間和設(shè)備二維性并定義了相應(yīng)的二維存儲結(jié)構(gòu)，分別針對每一維建立了索引，然后分析了基于此結(jié)構(gòu)的存儲和查詢方法。

關(guān)鍵詞：索引；二維存儲；存儲結(jié)構(gòu)

中圖分類號：TP274.2

隨著計算機技術(shù)在我國的全面發(fā)展與運用，在社會、經(jīng)濟、政治等諸多領(lǐng)域快速發(fā)展，在日常應(yīng)用中經(jīng)常遇到一類設(shè)備狀態(tài)監(jiān)控的問題。每個設(shè)備按照時間周期返回狀態(tài)數(shù)據(jù)，系統(tǒng)需要記錄系統(tǒng)中設(shè)備運行狀況，在設(shè)備出現(xiàn)問題時可以通過歷史記錄進行問題分析和問題定位的情況。當(dāng)前的應(yīng)用發(fā)展趨勢表明，被監(jiān)測設(shè)備的數(shù)目正在迅速增長，同時隨著技術(shù)的進步以及應(yīng)用的需求，數(shù)據(jù)回傳的周期也越來越短。對這類應(yīng)用數(shù)據(jù)存儲要求也越來越高。數(shù)據(jù)特點如下：多個設(shè)備數(shù)據(jù)相互獨立，設(shè)備本身變化不頻繁。但偶爾設(shè)備會出現(xiàn)問題，修理后重新啟動，狀態(tài)數(shù)據(jù)會中斷。

（1）設(shè)備狀態(tài)數(shù)據(jù)采集時間間隔固定。

（2）單設(shè)備按時間順序產(chǎn)生數(shù)據(jù)，不同設(shè)備的數(shù)據(jù)產(chǎn)生也基本有序。

（3）數(shù)據(jù)持續(xù)增加，在一個時間段內(nèi)增加頻率有規(guī)律可循，數(shù)據(jù)量大。

（4）主要操作為存儲和查詢。

1 數(shù)據(jù)文件存儲和查詢

對于要長期保存的數(shù)據(jù)，我們需要用數(shù)據(jù)文件保存，為了提高查詢的效率我們必然要針對數(shù)據(jù)文件建立索引。索引是對數(shù)據(jù)庫表中一列或多列的值進行排序的一種結(jié)構(gòu)，使用索引可快速訪問數(shù)據(jù)庫表中的特定值。不同的索引設(shè)計對數(shù)據(jù)的插入、查詢、刪除、修改等操作效率將產(chǎn)生巨大影響。高效的索引文件，應(yīng)該根據(jù)主文件數(shù)據(jù)結(jié)構(gòu)特點進行設(shè)計。

對數(shù)據(jù)文件建立索引首先想到的是B（B+，B-）樹。B樹是一種最常見的組織索引的方式。在B樹中，首先設(shè)定內(nèi)部（非葉子）節(jié)點包含子節(jié)點數(shù)量范圍。當(dāng)一個節(jié)點中數(shù)據(jù)插入或移除數(shù)據(jù)時，如果節(jié)點刪除或插入數(shù)據(jù)后節(jié)點保存數(shù)據(jù)數(shù)量超出規(guī)定的范圍，為了維持保存數(shù)據(jù)的數(shù)量在設(shè)定范圍內(nèi)，內(nèi)部節(jié)點可能會被連結(jié)或者分離。每個節(jié)點存儲多個數(shù)據(jù)，從而使查找樹的深度降低，減少查找層次提高查找效率。但針對于本文所描述的數(shù)據(jù)存儲情況，數(shù)據(jù)的插入操作基本是順序追加，而且沒有刪除操作，所以相對于B樹的插入、刪除操作就沒必要那么復(fù)雜，應(yīng)該做適當(dāng)簡化。

多對象的數(shù)據(jù)產(chǎn)生的頻率不同，使得數(shù)據(jù)具有二維特性，單獨的一維索引文件難以勝任。針對這些特點結(jié)合B樹和二分查找的特點，我們建立一種多對象時間序列數(shù)據(jù)二維存儲及索引結(jié)構(gòu)。多對象表示需要監(jiān)視多個設(shè)備；固定間隔時間序列數(shù)據(jù)，指的是每個設(shè)備獲得狀態(tài)數(shù)據(jù)按時間順序且間隔固定。

2 存儲與索引結(jié)構(gòu)的設(shè)計

數(shù)據(jù)按時間順序采集、存儲。查詢則主要是查找某個時間點或某個時間段的狀態(tài)數(shù)據(jù)，都是以時間為關(guān)鍵字的。所以，很自然的想到時間順序存儲，按時間和對象關(guān)鍵字建立索引。但這樣做的問題在于，隨著時間的推移記錄的數(shù)據(jù)量會非常龐大，導(dǎo)致索引文件也越來越大，給索引文件的建立維護及查詢效率都造成很大影響。同時，每一條記錄都帶有對象ID和產(chǎn)生時間也造占用大量存儲空間。

2.1 分時間塊存儲數(shù)據(jù)，針對時間塊建立索引。因?qū)ο螽a(chǎn)生數(shù)據(jù)頻率固定，為了減少時間索引的數(shù)量，采用固定時間段長度分塊存儲，每塊中包含本時間塊內(nèi)產(chǎn)生的所有數(shù)據(jù)。以時間塊中的初始時間點為關(guān)鍵字，建立索引。因時間段的產(chǎn)生是按時間順序的，所以本索引為順序索引。如果索引文件太大，則通過更大的時間段，建立多級索引。這樣大大減少了索引文件的大小。

2.2 對于塊內(nèi)數(shù)據(jù)，由于數(shù)據(jù)分別屬于不同對象，所以應(yīng)將相同對象數(shù)據(jù)放在一起。當(dāng)同一對象的數(shù)據(jù)存儲在一起，那么對象的ID也就只存儲一次即可；又因同一對象產(chǎn)生狀態(tài)數(shù)據(jù)的時間間隔固定，那么只需要存儲本快中起始數(shù)據(jù)的時間點即可，其余數(shù)據(jù)按產(chǎn)生順序依次存儲。這樣可以減少大量的存儲空間

2.3 塊內(nèi)相同對象的數(shù)據(jù)存儲在一起，為了方便對數(shù)據(jù)的定位，需要獲知每個對象在數(shù)據(jù)塊中的存儲位置和長度。所以需要針對塊內(nèi)對象，按對象ID和塊內(nèi)偏移地址建立對象索引。為了處理方便，固定時間塊的大小，那么在一個時間塊中每個對象最大可產(chǎn)生狀態(tài)數(shù)據(jù)量就是固定的（采集數(shù)據(jù)的頻率固定）。所以，所有時間塊中的對象存儲結(jié)構(gòu)可以是一樣的，從而可以一開始就計算出每個設(shè)備的存儲偏移量并建立一個相應(yīng)的對象索引文件。

3 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)說明

數(shù)據(jù)存儲主要有三類文件：存儲數(shù)據(jù)的主數(shù)據(jù)文件；時間塊的索引文件；時間塊內(nèi)的設(shè)備存儲索引文件。

#define deviceSize //對象數(shù)量

#define TimeBlockSize //一個時間塊大小

3.1 主數(shù)據(jù)文件mainData.data，以時間塊為存儲單位存儲數(shù)據(jù)。每當(dāng)有數(shù)據(jù)要存儲，如果需要添加新時間塊，主數(shù)據(jù)文件則以TimeBlockSize為單位進行擴容。每個時間塊中存儲了所有對象在本時間塊內(nèi)產(chǎn)生的狀態(tài)數(shù)據(jù)，每個對象的數(shù)據(jù)結(jié)構(gòu)如下：

struct deviceTimeStruct {

long beginTime；//在本時間塊內(nèi)本對象產(chǎn)生第一個數(shù)據(jù)的起始時間

long realNum；//按采集頻率不間斷采集的狀態(tài)數(shù)據(jù)的數(shù)量。

Element * element；//實際采集的數(shù)據(jù)

}

如果設(shè)備因故障或其他原因暫停后又重啟，那么狀態(tài)數(shù)據(jù)是不連續(xù)的，此時需要創(chuàng)建新的deviceTimeStruct來存儲采集到的狀態(tài)數(shù)據(jù)。

3.2 時間塊索引文件TimblockIndext.inx結(jié)構(gòu)

struct TimeBlockIndext {

long TimeIndextElementNum；//索引塊的數(shù)量，由數(shù)據(jù)的時間跨度決定

long realuseNum；//實際存儲塊數(shù)量，用于計算主文件擴容時新塊的起始位置

TimeIndextElement * timeElement；//具體索引記錄

}

struct TimeIndextElement{ //索引記錄結(jié)構(gòu)

bool flage；//標(biāo)志位，true表示本時間塊啟用，1表示本時間塊未啟用

long offsetAddress；//本時間塊在數(shù)據(jù)文件中的偏移地址

}

本索引文件按時間順序建立，所以自然想到可以按二分查找的方法進行查詢。但是因為索引文件存儲在外存，直接用二分查找會產(chǎn)生大量的讀外存操作會耗費大量時間。因此借鑒了B樹的做法，每當(dāng)找到一個中間點時，不是僅讀取一個數(shù)據(jù)，而是讀取連續(xù)的多個數(shù)據(jù)進內(nèi)存進行判斷。這樣即大大減少了查找層次又利用的二分查找的高效。

3.3 時間塊內(nèi)對象存儲位置索引文件DeviceIndext.inx結(jié)構(gòu)

struct DeviceIndext {

long lastOffsetAddress；//增加新對象時在數(shù)據(jù)庫中偏移量的位置

deviceIndetElemen* devElement；//具體索引記錄。

}

struct deviceIndElemen {//索引記錄結(jié)構(gòu)

int deviceID；//對象的編號

int rate；//對象產(chǎn)生數(shù)據(jù)的頻率

long offsetAddress；//本對象數(shù)據(jù)在時間塊中存儲的偏移地址

}

4 主要操作實現(xiàn)方法

4.1 存儲操作實現(xiàn)

數(shù)據(jù)的到來基本是按時間順序的，但是數(shù)據(jù)所屬的對象是沒有規(guī)律的。針對這種特點，為了提高效率，減少訪問外存的時間，在設(shè)計時我們使用了緩存的方法。以一個時間塊為單位，在內(nèi)存中形成一個時間塊的映射，隨著數(shù)據(jù)的產(chǎn)生，將屬于本快中的數(shù)據(jù)填入其中。等到一個時間塊結(jié)束時，啟動塊寫進程來將緩沖塊中數(shù)據(jù)寫入外部文件，其中塊寫進程的主要流程如下：

（1）讀取緩存塊當(dāng)前存儲數(shù)據(jù)所屬的時間段的起始時間

（2）計算緩沖塊所對應(yīng)的數(shù)據(jù)塊的塊號

（3）根據(jù)塊號在時間塊索引文件中查詢相應(yīng)的塊記錄，如果相應(yīng)的塊已經(jīng)創(chuàng)建則轉(zhuǎn)到（7），否則轉(zhuǎn)到（4）

（4）創(chuàng)建新數(shù)據(jù)塊，首先計算擴充主數(shù)據(jù)文件一個時間塊大小的空間，記錄起始偏移位置。

（5）添加索引記錄，修改時間塊索引文件，添加一個記錄項（根據(jù)塊號和索引記錄的長度直接計算添加的位置）將上一步中的偏移地址記錄其中。

（6）從時間塊索引文件中讀取本塊在主數(shù)據(jù)文件中的偏移位置

（7）根據(jù)偏移位置，打開主數(shù)據(jù)文件并定位偏移處。

（8）將緩存區(qū)中的數(shù)據(jù)，寫入數(shù)據(jù)文件。結(jié)束

4.2 查詢操作實現(xiàn)

因為本存儲結(jié)構(gòu)的設(shè)計根本思想是將每個數(shù)據(jù)存儲位置都提前進行設(shè)計，所以查找也就變成了計算其存儲位置。過程可簡化為如下步驟：

（1）根據(jù)查找數(shù)據(jù)的起始時間計算所在的數(shù)據(jù)塊的塊號。（起始時間/數(shù)據(jù)塊長度）

（2）根據(jù)數(shù)據(jù)塊號，從時間塊索引中查找數(shù)據(jù)塊的偏移地址

（3）根據(jù)對象編號計算出其數(shù)據(jù)在數(shù)據(jù)塊中的偏移地址

（4）兩個偏移地址相加即為數(shù)據(jù)所屬對象存儲的起始位置

（5）根據(jù)產(chǎn)生數(shù)據(jù)頻率和本對象存儲第一個數(shù)據(jù)的時間計算查找數(shù)據(jù)是本段中存儲的第幾個數(shù)據(jù)，從而計算出偏移地址

（6）根據(jù)偏移地址，讀取數(shù)據(jù)。結(jié)束

5 總結(jié)

這種時間和對象二維結(jié)構(gòu)的設(shè)計，充分利用了對象數(shù)據(jù)產(chǎn)生有固定頻率特性，減少了大量存儲空間；結(jié)構(gòu)固定，使用預(yù)分配空間的方式，建立二維索引，提高了查詢效率。但是，固定結(jié)構(gòu)也必然存在著不夠靈活的問題。這些問題可以通過增加輔助存儲空間和存儲信息的方法解決。另外可以使用緩存、多進程并行操作等技術(shù)進一步提高系統(tǒng)效率。

參考文獻：

[1]彭秀萍，劉亞鋒.選擇數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)的一般原則研究[J].成都大學(xué)學(xué)報（自然科學(xué)版），2007（3）.

[2]王振東.鐵路調(diào)度指揮系統(tǒng)中日志數(shù)據(jù)庫的設(shè)計與優(yōu)化[D].中國鐵道科學(xué)研究院，2011.

[3]劉純悅，葛海通，嚴(yán)曉浪.面向視頻處理的高效二維流存儲系統(tǒng)[J].江南大學(xué)學(xué)報（自然科學(xué)版），2008（1）.

[4]丁治明.一種海量傳感器數(shù)據(jù)存儲與查詢方法[P].CN201210093419.7，2012（8）.

作者簡介：張青（1976-），男，山東泰安市人，山東科技大學(xué)軟件工程碩士，講師，研究方向：軟件工程。

作者單位：泰山職業(yè)技術(shù)學(xué)院 信息工程系，山東泰安 271001