田赤英

（中國大洋礦產(chǎn)資源研究開發(fā)協(xié)會(huì) 北京 100860）

一種面向海洋監(jiān)控視頻的索引機(jī)制?

田赤英

（中國大洋礦產(chǎn)資源研究開發(fā)協(xié)會(huì) 北京 100860）

數(shù)據(jù)作為一種資產(chǎn)其蘊(yùn)含的價(jià)值越來越重要，把收集到的數(shù)據(jù)存儲(chǔ)下來用于后續(xù)的數(shù)據(jù)分析與挖掘具有重要意義。論文針對(duì)海量的海洋監(jiān)控視頻，提出一種存儲(chǔ)方案來滿足查詢需求。在此基礎(chǔ)上，文中提出一種索引結(jié)構(gòu)RB-Tree，使得基于該索引可實(shí)現(xiàn)海量數(shù)據(jù)的快速檢索。此外，文章從理論層面對(duì)索引查詢的時(shí)間代價(jià)進(jìn)行分析，并與基于傳統(tǒng)B+Tree、R-Tree索引的查詢時(shí)間代價(jià)進(jìn)行對(duì)比，說明RB-Tree在海量視頻數(shù)據(jù)管理上的優(yōu)勢。

海量視頻數(shù)據(jù)；監(jiān)控視頻；B+Tree索引；R-Tree索引；RB-Tree索引

1 引言

海洋調(diào)查船是用于海洋科學(xué)考察、應(yīng)用技術(shù)研究以及測量或勘探等船舶的統(tǒng)稱［1］。大洋綜合資源調(diào)查船是集多學(xué)科、多功能、多技術(shù)手段為一體、滿足以大洋資源為主同時(shí)兼顧相關(guān)深海多學(xué)科交叉研究需求的全球級(jí)現(xiàn)代化海洋調(diào)查船，承載海洋地質(zhì)、海洋地球物理、海洋化學(xué)、海洋生物、物理海洋、海洋氣象、海洋聲學(xué)等綜合調(diào)查任務(wù)［2］。在該船的信息化系統(tǒng)中，數(shù)據(jù)可分為實(shí)時(shí)采集數(shù)據(jù)、人工上傳數(shù)據(jù)和實(shí)時(shí)視頻數(shù)據(jù)三大類，其中實(shí)時(shí)視頻數(shù)據(jù)包含衛(wèi)星電視、海底攝像等各種制式的視頻信息。對(duì)于各種不同制式的視頻數(shù)據(jù)，現(xiàn)有系統(tǒng)聚焦于如何將視頻信息實(shí)時(shí)發(fā)送給遠(yuǎn)程用戶進(jìn)行觀看。然而，隨著存儲(chǔ)設(shè)備成本的下降，人們更傾向于將所有獲取到的數(shù)據(jù)存儲(chǔ)下來用于挖掘和分析。

對(duì)于海量視頻數(shù)據(jù)，其價(jià)值的完整體現(xiàn)需要多種技術(shù)的協(xié)同。文件系統(tǒng)提供最底層存儲(chǔ)能力的支持；為了便于數(shù)據(jù)管理，需要在文件系統(tǒng)之上建立數(shù)據(jù)庫系統(tǒng)；通過索引等的構(gòu)建，對(duì)外提供高效的數(shù)據(jù)查詢等常用功能；最終通過數(shù)據(jù)分析技術(shù)從數(shù)據(jù)庫中的大數(shù)據(jù)提取出有益的知識(shí)［3］。在底層文件系統(tǒng)層，可以借助GFS文件系統(tǒng)［4］實(shí)現(xiàn)視頻類大文件的存儲(chǔ)。在文件系統(tǒng)之上，為支持海量數(shù)據(jù)，采用 NoSQL 方式管理數(shù)據(jù)［5～6］。典型的 NoSQL數(shù)據(jù)庫包括基于鍵值對(duì)模型、列式存儲(chǔ)模型、文檔模型和圖模型四種類型的數(shù)據(jù)庫［7～9］，由于視頻文件屬于非結(jié)構(gòu)化數(shù)據(jù)，查詢并不涉及視頻內(nèi)容，故可采用鍵值對(duì)模型對(duì)海量視頻數(shù)據(jù)進(jìn)行建模。在利用鍵值對(duì)進(jìn)行建模存儲(chǔ)時(shí)，面臨以下挑戰(zhàn)：

1）實(shí)時(shí)監(jiān)控產(chǎn)生的視頻數(shù)據(jù)具有時(shí)間段、地理位置等屬性，如何定義視頻數(shù)據(jù)的鍵，以支持基于時(shí)間段、地理位置的查詢；

2）對(duì)于海量視頻數(shù)據(jù)，需要構(gòu)建索引來加快查詢，如何設(shè)計(jì)索引結(jié)構(gòu)。

2 數(shù)據(jù)建模與查詢

實(shí)時(shí)視頻本身具有時(shí)間、地點(diǎn)的屬性，在對(duì)這些視頻數(shù)據(jù)進(jìn)行查詢時(shí)，需要查詢某個(gè)時(shí)間段內(nèi)某個(gè)區(qū)域的視頻。在以鍵值對(duì)方式存儲(chǔ)文件時(shí)，為支持基于地理區(qū)域和時(shí)間區(qū)間的查詢，定義鍵時(shí)需要將這兩種因素考慮在內(nèi)。此外，由于同一時(shí)間可能有多個(gè)設(shè)備對(duì)同一區(qū)域進(jìn)行監(jiān)控，因此若僅考慮地理區(qū)域和時(shí)間因素設(shè)計(jì)的鍵不具有唯一性，此時(shí)，需另外考慮設(shè)備ID號(hào)。因此本文對(duì)視頻數(shù)據(jù)以鍵值對(duì)方式進(jìn)行建模，具體如下：

＜key，value＞=＜設(shè)備ID號(hào)+地理區(qū)域+時(shí)間區(qū)間，視頻文件的物理存放地址＞

其中，設(shè)備ID號(hào)是把各種不同設(shè)備的標(biāo)識(shí)號(hào)映射為長度固定的標(biāo)識(shí)號(hào)；地理區(qū)域?yàn)榫匦螀^(qū)域?qū)屈c(diǎn)的坐標(biāo)，即（(x1，y1)，(x2，y2)）；時(shí)間區(qū)間為［起始時(shí)間，結(jié)束時(shí)間］，時(shí)間以“年月日時(shí)分秒”來表示。

例1。對(duì)于某設(shè)備，假定其映射后得到的設(shè)備標(biāo)識(shí)號(hào)為000001，其在2016年8月8日的16：00：00到 16：10：00分之間對(duì)區(qū)域（（385，691），（387，689））進(jìn)行拍攝，所形成的視頻文件的key表示為“000001385691387689201608081600002016080816 1000”。

由例1可以看到，該key的長度較長，為提高查詢效率，需對(duì)key進(jìn)行壓縮，縮短其長度。對(duì)于接收的監(jiān)控視頻，當(dāng)緩存中視頻流達(dá)到規(guī)定的最大長度限制k時(shí)，會(huì)創(chuàng)建一個(gè)文件將其寫入硬盤。因此，每個(gè)視頻文件的時(shí)長較短。假定一個(gè)視頻文件的時(shí)長不超過10min，則時(shí)間區(qū)間可表示為（起始時(shí)間，時(shí)間長度），其中時(shí)間長度位數(shù)為三位，最大取值為600（10min×60s/min）。例1中視頻文件的key經(jīng)壓縮后可表示為“00000138569138768920160808160000600”，縮短了11位。

基于定義的存儲(chǔ)模型，面向海洋監(jiān)控視頻的查詢定義為：給定一個(gè)地理區(qū)域s，查詢?cè)搮^(qū)域內(nèi)包含時(shí)間段（t1，t2］之間監(jiān)控內(nèi)容的視頻文件。

在查詢某個(gè)時(shí)間段內(nèi)某個(gè)區(qū)域的視頻文件時(shí)，要從key中抽取出表示地理區(qū)域和時(shí)間區(qū)間的子串，判斷是否與查詢條件中的區(qū)域和時(shí)間段有重疊。假定一個(gè)查詢，查找時(shí)間段2016年8月8日15：45：00到2016年8月8日16：05：00之間在區(qū)域（（386，690），（389，688））內(nèi)拍攝的視頻文件。首先判斷區(qū)域（（386，690），（389，688））與key中第7到18位所代表的區(qū)域（（385，691），（387，689））是否有重疊；若重疊，則繼續(xù)判斷時(shí)間區(qū)間［2016-08-08 15：45：00，2016-08-08 16：05：00］與key中第19到35位所代表的時(shí)間區(qū)間是否有重疊。若時(shí)間區(qū)間也重疊，則返回該視頻文件作為結(jié)果。

3 RB-Tree索引

在本文所定義的查詢中，若視頻文件的最大和最小時(shí)間點(diǎn)至少有一個(gè)位于查詢聲明的時(shí)間區(qū)間中，且視頻對(duì)應(yīng)矩形監(jiān)測區(qū)域的四個(gè)頂點(diǎn)坐標(biāo)中至少有一個(gè)位于查詢聲明的地理區(qū)域中，則屬于滿足條件的查詢結(jié)果。在傳統(tǒng)的鍵值對(duì)＜key，value＞存儲(chǔ)模型中，為了加快key的查找，常常在key上構(gòu)建B+Tree索引。在B+Tree中，葉子節(jié)點(diǎn)中對(duì)象取值為其父節(jié)點(diǎn)定義的取值范圍內(nèi)的值。在本文中，每個(gè)視頻文件對(duì)應(yīng)一個(gè)時(shí)間區(qū)間，因此要對(duì)B+Tree進(jìn)行修改，構(gòu)建類B+Tree，其與B+Tree的區(qū)別在于葉子節(jié)點(diǎn)中對(duì)象的值是一個(gè)時(shí)間區(qū)間。對(duì)于地理區(qū)域的查詢，屬于空間查詢，B+Tree并不適用。此時(shí)需考慮利用R-Tree來構(gòu)建索引。在R-Tree中，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)存儲(chǔ)一個(gè)矩形地理區(qū)域中所有對(duì)象的指針，若某非葉結(jié)點(diǎn)的孩子節(jié)點(diǎn)是非葉節(jié)點(diǎn)，則其所有孩子節(jié)點(diǎn)代表的矩形地理區(qū)域均包含在該節(jié)點(diǎn)對(duì)應(yīng)的地理區(qū)域中。

對(duì)于海量視頻數(shù)據(jù)來說，單純考慮修改B+Tree對(duì)時(shí)間范圍進(jìn)行索引或利用R-Tree對(duì)地理區(qū)域進(jìn)行索引，雖然在一定程度上可以提高查詢效率，但仍有提升空間。因此，本文提出一種混合索引樹RB-Tree，使得其可以對(duì)時(shí)間范圍和地理區(qū)域同時(shí)進(jìn)行索引，提高查詢效率。

3.1 RB-Tree索引的構(gòu)建

由于地理區(qū)域是固定不變的，可以考慮把地圖以面積為s的矩形進(jìn)行劃分，每個(gè)矩形塊對(duì)應(yīng)的區(qū)域稱之為單位地理區(qū)域。在構(gòu)建RB-Tree時(shí)，以單位地理區(qū)域?yàn)樽钚【仃噮^(qū)域，構(gòu)建R-Tree。與傳統(tǒng)R-Tree不同的地方在于，每個(gè)視頻文件并不直接作為矩陣區(qū)域中的對(duì)象。為支持基于時(shí)間區(qū)間的快速查詢，對(duì)每個(gè)單位地理區(qū)域，為區(qū)域內(nèi)所有視頻文件構(gòu)建類B+Tree，R-Tree中各節(jié)點(diǎn)僅包含對(duì)應(yīng)地理區(qū)域中類B+Tree根節(jié)點(diǎn)的指針。構(gòu)建類B+Tree時(shí)，把若干連續(xù)時(shí)間的視頻文件作為對(duì)象集，并以這些視頻所在的時(shí)間區(qū)間作為標(biāo)識(shí)創(chuàng)建葉子節(jié)點(diǎn)，然后自底向上依次創(chuàng)建上層節(jié)點(diǎn)。至此，完成RB-Tree的構(gòu)建。下面給出RB-Tree的定義：

定義 1（RB-Tree）：一棵樹是 RB-Tree，需具有以下特征：

1）樹中節(jié)點(diǎn)包含的對(duì)象是一棵類B+Tree；

2）類B+Tree中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)時(shí)間區(qū)間，非葉子節(jié)點(diǎn)包含時(shí)間區(qū)間內(nèi)的n個(gè)時(shí)間點(diǎn)，存在指針分別指向每個(gè)時(shí)間點(diǎn)之前和之后的時(shí)間區(qū)間對(duì)應(yīng)的節(jié)點(diǎn)；

3）類B+Tree中每個(gè)葉子節(jié)點(diǎn)包含一個(gè)對(duì)象集，對(duì)應(yīng)位于指定時(shí)間區(qū)間的所有視頻文件的key及其物理地址。

RB-Tree的具體構(gòu)建算法如下：

1）把視頻文件分組，位于相同單位地理區(qū)域的視頻文件分為一組，當(dāng)某視頻文件的地理區(qū)域跨越多個(gè)單位地理區(qū)域時(shí)，將其放入多個(gè)對(duì)應(yīng)分組中；

2）對(duì)步驟1）得到的每個(gè)分組中視頻文件再次進(jìn)行分組，使得每組包含m個(gè)視頻文件（最后一組包含小于等于m個(gè)）；

3）為每組視頻文件創(chuàng)建葉子節(jié)點(diǎn)，節(jié)點(diǎn)把能夠包含組內(nèi)視頻文件對(duì)應(yīng)時(shí)間區(qū)間的最小時(shí)間區(qū)間作為標(biāo)識(shí)，節(jié)點(diǎn)中包含指向各視頻文件的指針；

4）葉子節(jié)點(diǎn)根據(jù)時(shí)間先后順序用指針進(jìn)行關(guān)聯(lián)；

5）把節(jié)點(diǎn)按其時(shí)間范圍排序，以相鄰m個(gè)為一組進(jìn)行分組，對(duì)應(yīng)每組創(chuàng)建一個(gè)父親節(jié)點(diǎn)，把包含分組內(nèi)節(jié)點(diǎn)對(duì)應(yīng)時(shí)間區(qū)間的最小時(shí)間區(qū)間作為父親節(jié)點(diǎn)的標(biāo)識(shí)，以各孩子節(jié)點(diǎn)時(shí)間區(qū)間的最大邊界值形成時(shí)間點(diǎn)集合T；

6）在集合T中任意兩個(gè)相鄰時(shí)間點(diǎn)之間創(chuàng)建一個(gè)指針，指向時(shí)間區(qū)間在兩個(gè)時(shí)間點(diǎn)之間的孩子節(jié)點(diǎn)；

7）對(duì)于集合T最鄰近所屬節(jié)點(diǎn)時(shí)間區(qū)間最大和最小邊界值的兩個(gè)時(shí)間點(diǎn)，分別創(chuàng)建指向時(shí)間區(qū)間在邊界值和相鄰時(shí)間點(diǎn)之間的節(jié)點(diǎn)的指針；

8）以5）中創(chuàng)建的節(jié)點(diǎn)為孩子，構(gòu)建上層父節(jié)點(diǎn)，使得每個(gè)父節(jié)點(diǎn)的孩子個(gè)數(shù)為m（同一層中最后一個(gè)節(jié)點(diǎn)的孩子數(shù)小于等于m），若新創(chuàng)建的節(jié)點(diǎn)個(gè)數(shù)大于1，轉(zhuǎn)5），否則，轉(zhuǎn)9）；

9）為每個(gè)單位地理區(qū)域創(chuàng)建一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)中包含指向該區(qū)域中的類B+Tree根節(jié)點(diǎn)的指針，并記錄每個(gè)根節(jié)點(diǎn)對(duì)應(yīng)的時(shí)間區(qū)間。

10）以存在公共交點(diǎn)的相鄰m′個(gè)單位地理區(qū)域?yàn)閱卧瑒?chuàng)建上層節(jié)點(diǎn)，直至完成R-Tree的構(gòu)建。其中，非葉節(jié)點(diǎn)包含指向孩子節(jié)點(diǎn)的指針及其對(duì)應(yīng)的地理區(qū)域。

值得注意的是，在查詢某地理區(qū)域內(nèi)位于某時(shí)間區(qū)間的視頻文件時(shí)，既可以先基于地理區(qū)域進(jìn)行條件過濾，也可以先基于時(shí)間區(qū)間進(jìn)行條件過濾。由RB-Tree的構(gòu)建可以看到，本文傾向于先基于地理區(qū)域進(jìn)行條件過濾。這樣做是因?yàn)榈乩韰^(qū)域是固定不變的，而時(shí)間是一直變化的。若先基于時(shí)間區(qū)間構(gòu)建類B+Tree，再對(duì)葉子節(jié)點(diǎn)中包含的對(duì)象構(gòu)建R-tree，則需頻繁構(gòu)建新的R-Tree。而先基于地理區(qū)域構(gòu)建R-Tree，則每次只需對(duì)若干個(gè)B+Tree進(jìn)行插入節(jié)點(diǎn)的操作，而對(duì)多個(gè)B+Tree進(jìn)行插入操作更易并行化，從而加快更新速度。

在RB-Tree中，類B+Tree的每一層之所以都僅有一個(gè)節(jié)點(diǎn)包含的指向孩子節(jié)點(diǎn)或視頻文件的指針數(shù)量小于等于m，是因?yàn)樵赗B-Tree中不存在修改和刪除操作，僅隨時(shí)間推移而不斷插入新的對(duì)象，在后續(xù)章節(jié)會(huì)詳細(xì)介紹RB-Tree的更新。

3.2 RB-Tree索引的查詢

在進(jìn)行查詢時(shí)，由于不關(guān)心設(shè)備ID號(hào)，僅以地理區(qū)域和時(shí)間區(qū)間為查詢條件，且在RB-Tree構(gòu)建過程中，地理區(qū)域是基于單位地理區(qū)域進(jìn)行劃分的，因此，構(gòu)建樹的過程中僅需考慮key中時(shí)間區(qū)間相關(guān)的部分?；赗B-Tree的查詢算法具體如下：

1）根據(jù)查詢條件中給定的地理區(qū)域s，從RB-Tree根節(jié)點(diǎn)開始，逐層向下，尋找與s有重疊的子節(jié)點(diǎn)，直至葉子節(jié)點(diǎn)為止；

2）檢索葉子節(jié)點(diǎn)中記錄的各個(gè)類B+Tree的時(shí)間區(qū)間，根據(jù)指向類B+Tree的指針獲取特定的類B+Tree的根節(jié)點(diǎn)；

3）對(duì)于查詢條件中給定的時(shí)間區(qū)間（t1，t2］，依次把t1、t2與節(jié)點(diǎn)包含的時(shí)間點(diǎn)集中各時(shí)間點(diǎn)進(jìn)行比較，找出所有與時(shí)間區(qū)間（t1，t2］有重疊的下層孩子節(jié)點(diǎn)，若孩子節(jié)點(diǎn)是非葉節(jié)點(diǎn)，轉(zhuǎn)3），否則，轉(zhuǎn)4）；

4）順序讀取節(jié)點(diǎn)中包含的key，判斷該key對(duì)應(yīng)的時(shí)間區(qū)間是否與（t1，t2］有重疊，若重疊，則根據(jù)key對(duì)應(yīng)的value返回視頻文件。

3.3 RB-Tree索引的更新

監(jiān)控視頻文件隨時(shí)間不斷增加，不存在修改或刪除，因此只需考慮增加新的視頻文件后如何進(jìn)行RB-Tree的更新。RB-Tree包含R-Tree和類B+Tree，插入新的視頻文件會(huì)引起類B+Tree葉子節(jié)點(diǎn)的更新，該更新會(huì)逐層向上傳遞，直至類B+Tree的根節(jié)點(diǎn)。

在RB-Tree中，類B+Tree的非葉節(jié)點(diǎn)至多包含m個(gè)孩子，當(dāng)某節(jié)點(diǎn)隨時(shí)間推移插入的孩子節(jié)點(diǎn)達(dá)到m時(shí)，在此插入會(huì)導(dǎo)致新的非葉節(jié)點(diǎn)的創(chuàng)建。RB-Tree索引的更新算法如下：

1）新增一個(gè)視頻文件時(shí)，根據(jù)其所屬單位地理區(qū)域找到相應(yīng)的類B+Tree；

2）找到類B+Tree中與插入的視頻文件時(shí)間區(qū)間最接近的葉子節(jié)點(diǎn)i；

3）若節(jié)點(diǎn)i中對(duì)象個(gè)數(shù)小于m，則更新對(duì)應(yīng)葉子節(jié)點(diǎn)信息，插入該視頻文件的指針；

（1）更新其父節(jié)點(diǎn)中對(duì)應(yīng)該節(jié)點(diǎn)的時(shí)間區(qū)間，若父節(jié)點(diǎn)為根節(jié)點(diǎn)，轉(zhuǎn)2），否則，以其父節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)1）；

（2）更新RB-Tree中指向該類B+Tree根節(jié)點(diǎn)的葉子節(jié)點(diǎn)中對(duì)應(yīng)的時(shí)間區(qū)間，停止；

4）若節(jié)點(diǎn)i中對(duì)象個(gè)數(shù)等于m，創(chuàng)建新的葉子節(jié)點(diǎn)o，記錄指向新增的視頻文件的指針，并令其時(shí)間區(qū)間為新增視頻文件對(duì)應(yīng)的時(shí)間區(qū)間；

（1）在上層節(jié)點(diǎn)中尋找時(shí)間區(qū)間與節(jié)點(diǎn)o最接近的節(jié)點(diǎn)p；

（2）若節(jié)點(diǎn)p中孩子節(jié)點(diǎn)個(gè)數(shù)小于m，則為其添加指向節(jié)點(diǎn)o的指針，把p的時(shí)間區(qū)間最大邊界值作為新的時(shí)間點(diǎn)插入現(xiàn)有時(shí)間點(diǎn)集中并更新p時(shí)間區(qū)間，令o的時(shí)間區(qū)間最大邊界值作為p的時(shí)間區(qū)間的最大邊界值，否則，轉(zhuǎn)（3）；

（3）創(chuàng)建新的節(jié)點(diǎn)q，添加指向o的指針，并更新q的時(shí)間區(qū)間為o的時(shí)間區(qū)間；

（4）若p不是根節(jié)點(diǎn)，轉(zhuǎn)（1），否則，創(chuàng)建新的根節(jié)點(diǎn)r，令p、q為其孩子節(jié)點(diǎn)，添加時(shí)間區(qū)間和時(shí)間點(diǎn)集，并更新RB-Tree葉子節(jié)點(diǎn)中指向被更新的類B+Tree的時(shí)間區(qū)間和地址指針，停止。

4 RB-Tree索引查詢代價(jià)分析

為了便于進(jìn)行查詢代價(jià)的分析，本節(jié)首先定義如表1所示符號(hào)。

表1

在RB-Tree中，葉子節(jié)點(diǎn)僅包含指向類B+Tree根節(jié)點(diǎn)的指針，磁盤中每次獲取節(jié)點(diǎn)需要讀取至少一頁的數(shù)據(jù)，故當(dāng)葉子節(jié)點(diǎn)中指針數(shù)量為「Spage/（ST+Sadd）?時(shí)，可以最大程度減少I/O次數(shù)。對(duì)于非葉節(jié)點(diǎn)，除了包含指向其孩子節(jié)點(diǎn)的指針外，還包含表示各孩子節(jié)點(diǎn)對(duì)應(yīng)的地理區(qū)域，因此，當(dāng)非葉節(jié)點(diǎn)包含的孩子節(jié)點(diǎn)數(shù)量為「Spage/（Sarea+Sadd）?時(shí)，可以最大程度減少I/O次數(shù)。假定總的葉子節(jié)點(diǎn)數(shù)量為n，當(dāng)僅需訪問一個(gè)目標(biāo)葉子節(jié)點(diǎn)時(shí)，從RB-Tree的根節(jié)點(diǎn)開始查找葉子節(jié)點(diǎn)，樹中每層均需訪問一個(gè)節(jié)點(diǎn)，需要I/O的次數(shù)為

對(duì)于RB-Tree葉子節(jié)點(diǎn)所指向的類B+Tree，其葉子節(jié)點(diǎn)包含指向視頻文件的指針以及對(duì)應(yīng)視頻文件的key，故當(dāng)葉子節(jié)點(diǎn)中指針數(shù)量為「Spage/（Skey+Sadd）?時(shí)，可以最大程度減少I/O次數(shù)。對(duì)于非葉節(jié)點(diǎn)，除了包含指向其孩子節(jié)點(diǎn)的指針外，還包含一個(gè)覆蓋全部孩子節(jié)點(diǎn)時(shí)間區(qū)間的時(shí)間區(qū)間以及一個(gè)時(shí)間區(qū)間內(nèi)的時(shí)間點(diǎn)集合，時(shí)間點(diǎn)集合中時(shí)間點(diǎn)的數(shù)量為孩子節(jié)點(diǎn)數(shù)量減一，故當(dāng)非葉節(jié)點(diǎn)包含的孩子節(jié)點(diǎn)數(shù)量為「（Spage-ST-Sadd）/（St+Sadd）?時(shí)，可以最大程度減少I/O次數(shù)。在RB-Tree的葉子節(jié)點(diǎn)中，假定一棵類B+Tree的葉子節(jié)點(diǎn)數(shù)量為n′，順序讀取每棵類B+Tree對(duì)應(yīng)的時(shí)間區(qū)間，當(dāng)僅需訪問一個(gè)類B+Tree中的葉子節(jié)點(diǎn)時(shí)，從類B+Tree的根節(jié)點(diǎn)開始查找葉子節(jié)點(diǎn)，樹中每層均需訪問一個(gè)節(jié)點(diǎn)，需要I/O的次數(shù)為

因此，一次查詢需要的I/O的次數(shù)為

在上述RB-Tree中，一棵類B+Tree中包含的視頻文件最多有n′×「Spage/（Skey+Sadd）?個(gè)，一個(gè)RB-Tree中包含的類B+Tree最多有n×「Spage/（ST+Sadd）?個(gè)，故一棵RB-Tree中總的視頻文件最多有N=n′×「Spage/（Skey+Sadd）?×n×「Spage/（ST+Sadd）?個(gè)。

在最壞情況下，每個(gè)RB-Tree葉子節(jié)點(diǎn)均包含指向同一時(shí)間區(qū)間的類B+Tree。若僅用類B+Tree對(duì)數(shù)據(jù)進(jìn)行索引，葉子節(jié)點(diǎn)對(duì)應(yīng)的視頻文件數(shù)為n×n′×「Spage/（Skey+Sadd）?，共有N′=「N/（n×n′×「Spage/（Skey+Sadd）?）?個(gè)葉子節(jié)點(diǎn)，則需要I/O的次數(shù)為

根據(jù)RB-Tree中葉子節(jié)點(diǎn)包含的類B+Tree的數(shù)量「Spage/（ST+Sadd）?、每個(gè)類B+Tree中包含的視頻文件數(shù)量「Spage/（Skey+Sadd）?以及葉子節(jié)點(diǎn)的數(shù)量n′，

若僅用R-Tree對(duì)數(shù)據(jù)進(jìn)行索引，共有N′=「N/（「Spage/（ST+Sadd）?×「Spage/（Skey+Sadd）?×n′）?個(gè)葉子節(jié)點(diǎn)。若訪問某個(gè)葉子節(jié)點(diǎn)中的視頻文件，則需要I/O的次數(shù)為可知RB-Tree中每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)包含的視頻文件數(shù)量為

在進(jìn)行查詢時(shí)，由于需要同時(shí)考慮地理區(qū)域和時(shí)間區(qū)間兩個(gè)條件，在利用類B+Tree進(jìn)行檢索時(shí)，若位于同一時(shí)間區(qū)間內(nèi)的視頻文件數(shù)過多，會(huì)使得獲取一個(gè)葉子節(jié)點(diǎn)中所有數(shù)據(jù)需要多次I/O操作，使得查詢效率下降。在利用R-Tree進(jìn)行檢索時(shí)，若位于同一地理區(qū)域內(nèi)的視頻文件數(shù)過多，也會(huì)使得獲取一個(gè)葉子節(jié)點(diǎn)中所有數(shù)據(jù)需要多次I/O操作，使得查詢效率下降。通過本章節(jié)提出的I/O代價(jià)計(jì)算公式，可以算出當(dāng)視頻數(shù)據(jù)數(shù)量多大規(guī)模時(shí)，利用RB-Tree可以顯著提高查詢效率。

5 結(jié)語

本文討論了海量海洋監(jiān)控視頻的建模存儲(chǔ)，并提出一種索引結(jié)構(gòu)RB-Tree來提高視頻檢索的效率。文中對(duì)RB-Tree的查詢復(fù)雜度進(jìn)行深入分析，在此基礎(chǔ)上，對(duì)在何種情況下利用該索引可以有效提高查詢效率進(jìn)行了探討。

本文主要從理論層面分析了利用RB-Tree進(jìn)行索引查詢的復(fù)雜度，下一步，將結(jié)合具體的硬件對(duì)其查詢效率進(jìn)行深入的分析。

［1］李尉尉，王慧祺，夏登文，等.中國海洋調(diào)查船現(xiàn)狀及發(fā)展思考［J］.海洋開發(fā)與管理，2012，29（5）：41-43.LI Weiwei，WANG Huiqi，XIA Dengwen，et al.Reflections on the Status Quo and Development of Chinese Marine Survey Vessels［J］.Ocean Development and Management，2012，29（5）：41-43.

［2］劉健中，管義鋒.大洋綜合資源調(diào)查船全船結(jié)構(gòu)強(qiáng)度有限元分析［C］//船舶與海洋結(jié)構(gòu)學(xué)術(shù)會(huì)議暨中國鋼結(jié)構(gòu)協(xié)會(huì)海洋鋼結(jié)構(gòu)分會(huì)成立三十周年紀(jì)念學(xué)術(shù)會(huì)議.長沙：中國造船工程學(xué)會(huì)，中國鋼結(jié)構(gòu)協(xié)會(huì)，2015：178-185.LIU Jianzhong，GUAN Yifeng.Whole Structure Strength Analysis of Oceanographic Research Vessel［C］//Conference on Ship and Ocean Structure and the 30th Anniversary Conference of China Steel Structure Association.Changsha：China Shipbuilding Engineering Society，China Steel Construction Society，2015：178-185.

［3］孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)［J］.計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146-169.MENG Xiaofeng，CI Xiang.Big Data Management Concepts，Techniques and Challenges［J］.Journal of Computer Research&Development，2013，50（1）：146-169.

［4］Ghemawat S，Gobioff H，Leung S T.The Google file system［C］//ACM Symposium on Operating Systems Principles.New York：ACM，2003：29-43.

［5］Li Y，Manoharan S.A performance comparison of SQL and NoSQL databases［C］//Pacific Rim Conference on Communications，Computers and Signal Processing.Washington D C：IEEE Computer Society，2013：15-19.

［6］Chen M，Mao S，Liu Y.Big data：a survey［J］.Mobile Networks and Applications，2014，19（2）：171-209.

［7］Han J，Haihong E，Le G，et al.Survey on NoSQL database［C］//International Conference on Pervasive computing and applications.Washington D C：IEEE Computer Society，2011：363-366.

［8］He C.Survey on NoSQL Database Technology［J］.Journal of Applied Science and Engineering Innovation，2015，2（2）：50-54.

［9］Sharma V，Dave M.SQL and NoSQLDatabases［J］.International Journal of Advanced Research in Computer Science and Software Engineering，2012，2（8）：20-27.

［10］Hadjieleftheriou M，Manolopoulos Y，Theodoridis Y，et al.Encyclopedia of GIS［M］.US：Springer，2008：993-1002.

［11］Chen S，Gibbons P B，Mowry T C，et al.Fractal prefetching B+-Trees：optimizing both cache and disk performance［C］//ACM SIGMOD International Conference on Management of Data.New York：ACM，2002：157-168.

An Index for Ocean Surveillance Video

TIAN Chiying
（China Ocean Mineral Resources Research and Development，Beijing 100860）

The value of data which is considered as a kind of asset has become more and more important.Storing collected data for subsequent analysis and mining has great significance.In this paper，a storage scheme to meet the query requirement for massive ocean surveillance video is proposed.Propose the index RB-Tree to realize fast query over massive data is also proposed.Besides，the paper theoretically analyzes the time cost of query.The query cost of the RB-Tree with the traditional B+Tree and R-Tree to indicate our advantage on massive ocean video data is furtherly compared.

massive ocean video data，surveillance video，B+Tree index，R-Tree index，RB-Tree index

X85

10.3969/j.issn.1672-9722.2017.11.032

Class Number X85

2017年5月21日，

2017年6月27日

田赤英，女，研究員，研究方向：船載信息系統(tǒng)。