田赤英

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

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

田赤英

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

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

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

1 引言

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

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

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

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

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

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

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

其中，設備ID號是把各種不同設備的標識號映射為長度固定的標識號；地理區(qū)域為矩形區(qū)域?qū)屈c的坐標，即（(x1，y1)，(x2，y2)）；時間區(qū)間為［起始時間，結(jié)束時間］，時間以“年月日時分秒”來表示。

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

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

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

在查詢某個時間段內(nèi)某個區(qū)域的視頻文件時，要從key中抽取出表示地理區(qū)域和時間區(qū)間的子串，判斷是否與查詢條件中的區(qū)域和時間段有重疊。假定一個查詢，查找時間段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ù)判斷時間區(qū)間［2016-08-08 15：45：00，2016-08-08 16：05：00］與key中第19到35位所代表的時間區(qū)間是否有重疊。若時間區(qū)間也重疊，則返回該視頻文件作為結(jié)果。

3 RB-Tree索引

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

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

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

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

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

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

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

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

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

1）把視頻文件分組，位于相同單位地理區(qū)域的視頻文件分為一組，當某視頻文件的地理區(qū)域跨越多個單位地理區(qū)域時，將其放入多個對應分組中；

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

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

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

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

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

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

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

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

10）以存在公共交點的相鄰m′個單位地理區(qū)域為單元，創(chuàng)建上層節(jié)點，直至完成R-Tree的構(gòu)建。其中，非葉節(jié)點包含指向孩子節(jié)點的指針及其對應的地理區(qū)域。

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

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

3.2 RB-Tree索引的查詢

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

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

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

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

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

3.3 RB-Tree索引的更新

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

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

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

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

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

（1）更新其父節(jié)點中對應該節(jié)點的時間區(qū)間，若父節(jié)點為根節(jié)點，轉(zhuǎn)2），否則，以其父節(jié)點作為當前節(jié)點，轉(zhuǎn)1）；

（2）更新RB-Tree中指向該類B+Tree根節(jié)點的葉子節(jié)點中對應的時間區(qū)間，停止；

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

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

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

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

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

4 RB-Tree索引查詢代價分析

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

表1

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

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

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

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

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

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

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

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

5 結(jié)語

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

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

［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)強度有限元分析［C］//船舶與海洋結(jié)構(gòu)學術會議暨中國鋼結(jié)構(gòu)協(xié)會海洋鋼結(jié)構(gòu)分會成立三十周年紀念學術會議.長沙：中國造船工程學會，中國鋼結(jié)構(gòu)協(xié)會，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ù)管理：概念、技術與挑戰(zhàn)［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)。