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

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

中圖分類號(hào)：TP274.2

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

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

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

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

（4）主要操作為存儲(chǔ)和查詢。

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

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

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

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

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

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

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

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

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

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

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

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

#define TimeBlockSize //一個(gè)時(shí)間塊大小

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

struct deviceTimeStruct {

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

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

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

}

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

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

struct TimeBlockIndext {

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

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

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

}

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

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

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

}

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

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

struct DeviceIndext {

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

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

}

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

int deviceID；//對(duì)象的編號(hào)

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

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

}

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

4.1 存儲(chǔ)操作實(shí)現(xiàn)

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

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

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

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

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

（5）添加索引記錄，修改時(shí)間塊索引文件，添加一個(gè)記錄項(xiàng)（根據(jù)塊號(hào)和索引記錄的長(zhǎng)度直接計(jì)算添加的位置）將上一步中的偏移地址記錄其中。

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

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

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

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

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

（1）根據(jù)查找數(shù)據(jù)的起始時(shí)間計(jì)算所在的數(shù)據(jù)塊的塊號(hào)。（起始時(shí)間/數(shù)據(jù)塊長(zhǎng)度）

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

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

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

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

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

5 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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