一種面向地震數據的兩級索引

谷文彥，李 俊，潘昌森（中國科學技術大學 自動化系，安徽 合肥 230026）

一種面向地震數據的兩級索引

谷文彥，李 俊，潘昌森
（中國科學技術大學 自動化系，安徽 合肥 230026）

地震數據處理中的數據讀取具有塊小量大的特點，常規磁盤所用的數據讀取方式，其處理速度緩慢。設計了一種基于FastDFS的分布式地震數據存取系統。該系統將數據分塊存儲在硬盤上，在FastDFS中建立基于炮號和道號的兩級索引結構，并選取Trie樹作為一級索引，AVL樹或紅黑樹作為二級索引，提高了系統讀取速度。實驗結果表明，該地震數據存取系統減少了相應的查詢響應時間，提高了系統存取性能。

地震數據；兩級索引；Trie樹；紅黑樹；AVL樹

0 引言

隨著地震勘探技術快速發展，地震數據規模不斷增加。數據顯示，地震道集數按每三年翻一番的速度增長，2014年單文件已經突破16 000道［1-2］，這些數據量一般在TB甚至PB級別。當今PC集群的計算性能有了很大提高，但相應的集群存儲相對滯后，地震數據存取效率越來越成為地震資料處理的瓶頸。采用共享網絡文件系統NFS存取地震數據，制約了海量地震數據存取的效率［3］。并行文件系統Lustre［4］在存取地震數據I/O性能上優于NFS［3］，它采用RAID存儲數據，擁有高性能的順序讀取效率，但每次需要讀取整個條帶的數據，隨機讀取效率低。

地震數據處理程序請求的數據不一定連續存儲在文件中。處理程序在隨機請求數據時只需要文件中的若干道數據，卻要讀取整個文件，讀取效率就會很低。為此，本文提出一種快速存取地震數據的方法，該方法將地震文件的數據分塊存儲，并建立以炮號和道號為關鍵字的兩級索引結構。通過實驗表明，加入索引后，在滿足存取需求的同時，減少了查詢時間和數據傳輸開銷，提高了系統的存取效率。

1 地震數據

1.1 地震數據格式

勘探地球物理協會（Society of Exploration Geophysicists，SEG）制定的 SEGY地震數據格式是最常用的數據格式，SEGY文件結構如圖1所示。

圖1 SEGY格式

標準的SEGY格式包括3個部分：（1）3 200B的E-BCDIC文件頭，保存一些地震數據整體性的描述信息；（2）400B的二進制頭文件，用來保存描述SEGY文件的信息，如文件數據格式、采樣點數目、采樣時間、測量單位等；（3）實際地震勘探數據，每道數據前面會有240B的道頭信息，保存該道數據對應的位置坐標、采樣點數、炮號、道號等信息。

1.2 數據格式的改進

地震數據道頭主要是記錄道的信息，對用戶分析數據沒有作用，每次讀取地震數據還要把道頭數據也讀出來，效率很低。本文將道頭和數據體分開存儲，并在兩者之間加入關鍵字索引信息。用戶每次讀取數據，只要指定數據關鍵字，就可以通過索引查找到該數據存放的具體位置。這種方式下用戶每次讀的有效數據增多，效率有所改善。

2 兩級索引結構

2.1 FastDFS介紹及兩級索引結構

FastDFS充分考慮了冗余備份、負載均衡、線性擴容等機制，解決了大容量存儲、高并發訪問等問題。與現有的類Google FS相比，FastDFS的架構和設計的獨到之處體現在輕量級、分組方式和對等結構［5］。跟蹤器（Tracker）作為中心節點，提供負載均衡和任務調度；存儲節點（Storage）則直接利用文件系統存儲文件。FastDFS不對文件進行分塊存儲，上傳文件時，文件ID由存儲節點生成并返回給客戶端，文件ID中包含文件所在組名、相對路徑和文件名。存儲節點可以直接根據文件名ID來定位數據。因此FastDFS中不需要存儲索引信息。

本系統為支持順序讀取和隨機讀取地震道數據，對SEGY文件格式進行改進，將道頭和數據塊分開存儲，在兩者之間建立二級索引。考慮到跟蹤器負責管理數據，因此將數據塊的位置信息存儲在跟蹤器上，客戶端讀數據時，可以根據跟蹤器上存儲的信息直接找到存儲數據的存儲節點，而跟蹤器上的信息就是本文提出的一級索引。綜上所述，兩級索引中一級索引記錄數據塊所在存儲節點號，二級索引記錄數據塊具體位置。系統框架如圖2所示。

圖2 兩級索引框架

2.2 I/O操作流程

（1）寫數據

Client寫數據的數據頭中包含炮號、起始和終止道號及數據塊大小等信息，以便跟蹤器和存儲節點構建索引。寫數據塊過程中同一炮號不同塊的數據分布在不同的卷組內，以實現負載均衡。寫數據前 Client向跟蹤器詢問可存儲新數據塊的存儲節點，數據寫入存儲節點后，該存儲節點會根據數據塊信息（數據塊所屬的炮號、起始道號、終止道號）和位置信息構建二級索引。跟蹤器會根據存儲節點報告的信息構建一級索引，流程如圖3所示。

圖3 寫流程

（2）讀數據

Client從存儲節點讀數據時，命令需要包含炮號、起始和終止道號。Client首先查詢跟蹤器上的一級索引，找到數據塊所在的存儲節點，然后Client向該存儲節點讀數據，存儲節點則根據二級索引查詢數據具體位置，并讀出數據返回給Client。讀數據流程如圖4所示。

圖4 讀流程

3 兩級索引實現

3.1 一級索引

存儲采用共炮存儲，即同一炮的多道數據合并后作為一個數據塊存儲在存儲節點上，數據塊名格式為：炮號_起始道號_終止道號，且以此數據塊名形成的字符串作為一級索引的key值，value值是該數據塊所在存儲節點的信息。用戶要查詢第100炮的第0～99道的數據，就會首先生成100_0_99這個字符串，然后去一級索引中查找，返回存儲數據的存儲節點。

一級索引采用 Trie樹，Trie樹利用字符串的公共前綴來降低查詢時間以達到提高效率的目的。Trie樹的插入、刪除和查找都很簡單，用一個循環就可以解決，第i次循環找到前i個字符。以靜態開辟個數組來實現這棵字符樹，本文每個節點的子節點有11種情況（0～9和_），需要對每個節點開辟一個大小為 11的數組。

3.2 二級索引

紅黑樹［6］在每個節點上增加一個顏色位，可以是Red或Black，通過限制從根到葉子路徑中各節點著色方式來維持平衡，有4種平衡方法［7］。紅黑樹正是用這種非嚴格的平衡來換取增刪節點時旋轉次數的降低，性能比普通二叉樹高。

［8］中說明當操作僅限于插入和檢索時AVL樹是平衡二叉搜索樹中最有效的方法，在查找和排序上有很重要的應用。AVL樹左右子樹高度差超過1，會被認為是不平衡的，由于AVL樹的這種平衡條件，使樹的深度不會過深。參考文獻［9］、［10］中闡述了可能導致AVL樹失去平衡的4種可能，及相應的4種旋轉方法。

Client查到存儲節點后通過炮號、起始道號向該存儲節點查尋二級索引，找數據具體位置。

本文分別采用紅黑樹和AVL樹作為二級索引，力求尋找一個性能更佳的二級索引結構。通過炮號及道號來唯一標識數據塊，于是本文把炮號和起始道號組成的聯合體組合成一個唯一長整形數，代碼如下。以此作為該二級索引key值，對應的value值為該數據塊的位置信息。

二級索引關鍵字結構代碼：

4 實驗與結果

4.1 實驗環境

本實驗集群由5臺服務器組成，1臺client、1臺跟蹤器和3臺存儲節點。每臺服務器CPU均為2.33GHz，內存為4GB，操作系統是CentOS6.4。

4.2 實驗和結果

本文提出的地震數據存取系統是基于FastDFS修改而來的。一級索引采用Trie樹，二級索引加入AVL樹的版本命名為AVLFS，加入紅黑樹的版本命名為RBFS。每道數據32KB，將100道數據作為一個數據塊。采用以下兩種方法進行測試：（1）寫入相同數據塊，測試讀取速度隨著讀的有效數據大小變化的關系；（2）讀取有效數據一定，測試速度隨著寫入數據量變化的關系。

實驗1寫入200炮的數據，每炮100個數據塊，一共20 000個數據塊。讀取分布在不同數據塊中的道，測試結果如圖5所示。

圖5 速度隨讀請求的變化關系

實驗2 讀取8 000道地震數據，這8 000道數據分布在不同數據塊，結果如圖6所示。

圖6 速度隨寫數據塊數量的變化關系

圖5顯示，與FastDFS相比，加入兩級索引的地震數據存取系統在隨機讀的速度上有了8～10倍的提升，隨著數據塊請求數的增加，速度也有所提升，這是由于多磁盤并發讀取使得速度有所增加。圖6中隨著寫數據塊個數的增多讀取速度幾乎沒有影響，這說明索引性能沒有隨著寫數據塊個數增加而降低。通過圖5、圖6，還可得出二級索引采用AVL樹在讀取速度上優于紅黑樹，主要是AVL樹比紅黑樹更加平衡，查詢效率更快。

5 結論

本文提出一種能夠快速存取地震數據的方法，該方法將數據分塊存儲，并建立兩級索引結構。實驗表明，加入兩級索引后滿足了對地震數據隨機讀取的要求，同時減少了查詢時間和數據傳輸開銷，系統讀取速度有很大提高。針對查詢操作，AVL樹優于紅黑樹索引，而地震數據存取就是一次存儲，多次讀取，故本系統最終選擇AVL樹作為二級索引。本文后續工作將會對兩級索引進行進一步優化。

參考文獻

［1］張捷.石油勘探地震數據的處理和成像問題［R］.合肥：中國科學技術大學地球物理研究所，2013.

［2］趙改善.我們需要多大和多快的計算機［J］.勘探地球物理進展，2004，27（1）：23-28.

［3］杜吉國，孫孝萍，陳繼紅，等.Lustre并行文件系統在地震數據處理中的應用［J］.物探裝備，2013，23（5）：294-299.

［4］Lustre［EB/OL］（2015-03-31）.http：//wiki.lustre.org/index.php/Main_page.

［5］余慶.分布式文件系統 FastDFS架構剖析 ［J］.程序員，2010（11）：63-65.

［6］Rudolf Bayer.Symmetric binary B-Trees：data structure and maintenance algorithms［J］.Acta Informatica，1972，1（4）：290-306.

［7］THOMAS H C，CHARLES E L，RONALD LR，et al.算法導論［M］.潘金貴，顧鐵成，李成法，等，譯.北京：機械工業出版社，2006.

［8］BAER J L，SCHWAB B.A comparison of tree-balancing algorithms［J］.Communication of the ACM，1977，20（5）：322-330.

［9］ELLIS C S.Concurrent search and insertion in AVL Trees［J］. IEEE Transactions on Computers，1980，29（9）：811-817.

［10］CHAUHAN S，THAKUR S，RANA S，et al.A brief Study of balancing of AVL Tree［J］.International Journal of Research，2014，1（11）：406-408.

A two level index for seismic data

Gu Wenyan，Li Jun，Pan Changsen
（Department of Automation，University of Science and Technology of China，Hefei 230026，China）

Read data in seismic data processing has a characteristics of small piece and large number，and for the conventional disk read mode，its processing speed is slow.This paper designed a distributed seismic data access system based on FastDFS.This system stored the data in hard disk based on block，and established two level index structure based on the shot number and gather number in FastDFS.It selected Trie tree as the primary index，AVL tree or red-black tree as the secondary indexes，to improve the reading speed of the system.The experimental results show that the seismic data access system created in this paper has reduced the query response time，and can improve the performance of system access.

seismic data；two level index；Trie tree；red-black tree；AVL tree

TP316.4

A

1674-7720（2015）18-0026-03

谷文彥，李俊，潘昌森.一種面向地震數據的兩級索引［J］.微型機與應用，2015，34（18）：26-28，35.

2015-04-20）

谷文彥（1988-），男，碩士研究生，主要研究方向：網絡軟件開發、嵌入式軟件開發。

李俊（1973-），男，博士，副教授，碩士研究生導師，主要研究方向：網絡傳播與控制。

潘昌森（1990-），男，碩士研究生，主要研究方向：網絡軟件開發、大數據。