基于八叉樹的地震數據多級緩存方法

曹晉 彭成

關鍵詞：分布式；八叉樹；地震數據；多級緩存；雙向鏈表

0 引言

隨著石油勘探工作的不斷深入及勘探范圍的不斷擴大，油氣分布由早期的構造性油氣藏分布向隱蔽性油氣藏分布逐步過渡[1]。面對越來越復雜的地質構造，單位數據采集量不斷增加，采集的地震數據日益龐大[2]。然而，相關地震數據處理技術、可視化手段仍停留在早期的簡單數據處理階段，遠遠滯后于地震數據采集技術的發展，已無法滿足當前勘探處理對象的精度和深度要求[3-4]。如何提高和改進地震資料處理技術已成為當前物探工作中亟待解決的首要問題[5]。

隨著計算機技術的飛速發展，在地理勘探領域中，深部探測會產生超大規模地震數據SEGY文件，其文件規模能達到TB量級[6]。傳統的地學應用在數據處理過程中采用一次加載、反復使用的模式。但是，當數據規模遠超內存時，將不能使用傳統加載模式對數據進行處理[7-8]。為此，地震數據需要采用文件格式與內存管理兩種手段支持超大規模數據。這種超大規模地震數據的處理手段目前被國外技術壟斷[9]。

如何利用現代計算機的高速處理能力，提高地震數據處理精度及地震數據顯示速度，是目前迫切需要解決的重要問題[9]。迄今為止，國內外眾多石油地球物理勘探公司、相關高校研究院所投入了大量的資金和技術力量，致力于地震數據處理相關技術的研究[10]。

傳統的地震資料處理系統以地震道為數據輸入輸出單元，難以集成基于道集的復雜處理算法，并且數據I/O效率低。為了更快地響應地震數據查詢請求，需要設計合適的存儲結構及內存緩沖機制。本方法利用三維空間下八叉樹結構與編碼的快速空間定位機制，實現對三維大數據體的結構分塊存儲，同時設計了二級緩存結構，提升了數據訪問效率。

1 八叉樹編碼與分塊存儲

對地震數據按照設定的小立方體大小進行切分，生成若干子塊文件，實現八叉樹結構的地震分塊存儲。八叉樹編碼使用的是線性莫頓（Morton） 編碼。莫頓碼本質上是一種八進制碼，如圖1所示，每一位八進制數位可以看成3位二進制數，由所在節點的空間位置編碼而來（其中，n 表示子體數據塊所處的空間結構位置）：Morton = [（x0，y0，z0），（x1，y1，z1），...，（xn-1，yn-1，zn-1）]。切分時的每個子塊都會有其對應的莫頓碼，從莫頓碼也可以反推出子塊對應的空間范圍。莫頓碼的位數等于切分的層級數，層級越小，莫頓碼越短，切分的粒度越粗，層級越大，莫頓碼越長，切分的粒度越細，本方法中只切分生成最終一級的子塊，其他層級的子塊并不進行切分生成。

八叉樹節點體現了空間坐標信息，同時易于實現自然數的映射，即某一體數據塊的具體文件存儲位置。莫頓碼按照大小排序得到子塊的自然數編碼（Tile ID） ，進而映射到不同體數據塊文件存儲位置。

在利用八叉樹子塊來讀取地震數據時，通過輸入的主測線號、聯絡線號和深度范圍得到其在源地震數據立方體中相應的空間范圍，進而轉換成一組對應的線性莫頓（Morton） 編碼，然后以子塊自然數編碼（TileID） 為索引定位數據在文件中的存儲位置；同樣，給出數據存儲位置，也可以計算子塊自然數編碼（Tile ID） ，得到它在體數據或八叉樹中的空間位置。自然數編碼（Tile ID） 從零開始，對應最終層級中莫頓碼最小的子塊，依次類推。數據在子塊中的具體位置由空間范圍與子塊三個方向的長度除余得到起始偏移量，然后從起始位置讀取地震數據。

2 基于地震道的一級緩存結構

構成地震數據文件的基本單元是地震道，相當于地震數據立方體高方向上的一整條。地震道包括道頭和具體的地震數據，道頭中含有地震道的主測線號、聯絡線號、起止時間、地震數據點個數等信息。對于地震數據的查詢請求通常是給定主測線號、聯絡線號、起止時間、返回對應位置范圍的地震數據。

一級緩存就是在內存中存放一組地震道，每次查詢請求傳過來時，如果存在滿足要求的緩存地震道，則直接返回結果。地震道緩存結構如圖2所示，測網中偏移指地震道在主測線和聯絡線構成的測網平面上的位置；地震數據中存放了此道在起始時間和終止時間范圍內的地震數據；采樣間隔是相鄰兩個地震數據樣本點的采樣時間間隔，通過間隔和時間，建立起采樣點與采樣時間的對應關系；道集大小對于疊后數據為1，對于疊前數據，同樣的主測線和聯絡線下，對應的是一組地震道而不是一條地震道，此時道集大小為這組地震道的個數，地震數據中順序存放各個地震道；最大最小振幅表示此道地震數據的絕對值的最大最小值；命中次數表示此緩存被使用了多少次，后面在內存不夠需要刪除部分緩存道時，會根據此值大小，優先刪除使 用次數少的地震道緩存。

3 基于八叉樹子塊的二級緩存結構

二級緩存是對子塊的緩存，當一級緩存中不存在對應結果時，就會繼續從二級緩存去尋找。每個二級緩存相當于將一個子塊文件加載到內存中，其數據結構如圖3所示，莫頓碼表示此子塊的線性莫頓（Mor?ton） 編碼；塊編碼是塊的自然數編碼（Tile ID） ；中心坐標是此子塊的空間位置范圍的中心點；地震數據存放了子塊中所有的地震數據；地震數據大小表示這些地震數據的個數；命中次數表示此緩存被用到的次數；塊大小表示這個子塊在三個方向上長度的乘積，即子塊立方體體積；前一個塊和后一個塊表示前面和后面的子塊緩存，二級緩存采用的是雙向鏈表緩沖技術，如圖4所示，這種結構可以避免數據塊在內存中的頻繁遷移。同時，根據訪問頻度等信息組織子體數據塊索引，確保在鏈表末端的數據是最少被訪問的數據，可以優先剔除出內存，而那些最近被使用的數據將放在最前端。

4 一級緩存的生成及利用

分級緩沖讀取地震道整體流程如圖5所示。首先從地震道緩存中獲取數據，如果有則返回，并將緩存命中數加1；如果沒有，則繼續從子塊緩存中獲取數據。如果子塊緩存中有數據，則將獲取到的數據填到地震道相應的位置上，并將子塊緩存命中數加1，同時將獲取的地震道作為緩存存放下來。如果子塊緩存中沒有數據，則從子塊文件中提取數據，填到地震道相應的位置上，并生成地震道緩存和子塊緩存。當緩存數量達到設定的限制時，刪除使用數量最少的地震道緩存和使用較早的子塊緩存。

用戶對于地震數據的查詢請求有多種形式，最終都轉換成主測線號、聯絡線號、時間范圍三個參數來獲取地震數據的，一級緩存采用的是普通LRU（LeastRecently Uesd，最少使用次數）策略，以地震道為單元的一級內存緩沖，緩存的是不同時窗范圍、多次讀取子塊地震道數據合并后的地震道數據。一次具體的生成和利用如圖6中左半部分所示。

1） 對于輸入的主測線號、聯絡線號、時間范圍，在地震道緩存中尋找相同主測線號、聯絡線號的緩存。如果沒有找到，則尋找二級緩存；如果找到，則判斷緩存的時間范圍是否能覆蓋輸入的時間范圍。

2） 當緩存時間范圍不能覆蓋用戶查詢請求時，缺少的范圍從二級緩存中繼續查找，最后將得到的數據與當前緩存中的地震道拼接；如果緩存時間范圍可以覆蓋用戶查詢請求，則直接使用此緩存地震道并增加緩存命中次數。

3） 將得到的地震道緩存按照用戶查詢請求的時間范圍進行截斷，生成地震數據并返回。

4） 當緩存道數量達到用戶設定的數量限制時，根據各個緩存道命中次數的多少，刪除命中較少的緩存道。剩余所有緩存道的命中次數統一減去一個數值，數值大小為所刪除的所有緩存道中命中次數最多的值。

5 二級緩存的生成及利用

一級內存緩沖未能覆蓋被請求的地震道數據時，根據主測線、聯絡線及時窗范圍，轉換為八叉樹的莫頓碼及對應的子塊文件存儲位置，詢問以八叉樹子塊為存儲單元的二級緩存。具體的流程如圖6右半部分所示。

1） 如果在二級緩存中找到相同子塊編號的子塊，則增加子塊緩存命中次數，并將此子塊緩存移動到鏈表中具有同樣命中次數的所有子塊緩存的最前端；如果沒有找到，則從文件中讀取子塊數據，并建立對應的子塊緩存。子塊緩存的建立方法為：莫頓碼和塊編碼填入對應的碼；中心坐標通過八叉樹計算出空間范圍，然后求取中心點；地震數據為子塊中的數據順序存儲；地震數據大小為子塊數據大小；命中次數為1；塊大小為子塊空間范圍大小；前一個塊為空，后一個塊為當前鏈表中第一個塊；將建立完成的子塊緩存放到命中次數為1的所有子塊緩存的最前端。

2） 如果之前找到一級地震道緩存，則將子塊數據拼接到地震道緩存中；如果沒有找到則新建一個地震道緩存，時間范圍為用戶查詢請求的范圍，將子塊數據填充到地震道緩存中。子塊數據拼接和填充的具體方法為：根據子塊數據所代表的時間范圍，與地震道緩存的時間范圍比較，得到子塊數據相對地震道緩存數據的具體位置，并替換已有位置上的數據或者填充到已有位置。對于疊前地震數據體，地震道緩存和子塊緩存都是深度上一整條地震數據存儲完再存儲下一條，在拼接或填充時需要一條一條拼接或填充。如圖7所示，在地震道緩存深度范圍內的數據，采用填充或替換方法；在地震道緩存深度范圍外的數據，采用拼接的方法。

3） 當子塊緩存達到用戶設定的數量限制時，刪去鏈表末尾的一批子塊緩存，即較早且使用次數較少的子塊緩存，刪除的數量為末尾一批具有相同命中次數的緩存。同時，其他所有子塊緩存的命中次數統一減去此批刪去子塊緩存的命中次數。

4） 將得到的地震道緩存按照用戶查詢請求的時間范圍進行截斷，生成地震數據并返回。

6 結論

本文設計了一種基于八叉樹的地震數據多級緩存方法。利用三維空間下八叉樹結構與編碼的快速空間定位機制，實現對三維大數據體的結構分塊存儲。同時設計了二級緩存結構，提升了數據訪問效率。實現了基于地震道的緩存和基于子塊的緩存，分別提升了查詢請求響應速度和子塊讀取響應速度。還實現了緩存訪問頻次記錄及雙向鏈表結構，避免數據塊在內存中的頻繁遷移，并且可以優先剔除利用次數少的緩存對象。