基于八叉树的地震数据多级缓存方法

曹晋 彭成

关键词：分布式；八叉树；地震数据；多级缓存；双向链表

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 结论

本文设计了一种基于八叉树的地震数据多级缓存方法。利用三维空间下八叉树结构与编码的快速空间定位机制，实现对三维大数据体的结构分块存储。同时设计了二级缓存结构，提升了数据访问效率。实现了基于地震道的缓存和基于子块的缓存，分别提升了查询请求响应速度和子块读取响应速度。还实现了缓存访问频次记录及双向链表结构，避免数据块在内存中的频繁迁移，并且可以优先剔除利用次数少的缓存对象。