MLB+-tree: A Multi-level B+-tree Index for Multidimensional Range Query on Seismic Data

摘要

Seismic processing is an important technology in petroleum industry. Processing results are usually observed and analyzed by petroleum scientists via interactive applications. In these applications, multidimensional range queries are frequently executed to fetch the data that users are interested in. The traditional B+-tree index does not work well for these queries because considerable index data has to be scanned from storage devices during the query execution. In this paper, we present MLB +-tree, a multi-level B+-tree index to accelerate multidimensional range queries on seismic data. Thinner index slices will be accessed by using MLB +-tree and query latency is reduced accordingly. An adaptive index selection method is also introduced to find the best index for various queries. Our experiments show that MLB +-tree outperforms B+-tree in most multidimensional range queries on different datasets. Since most queries are ad-hoc, fast index construction is desirable in seismic processing. To cope with this problem, we present a distributed index construction algorithm based on the map-reduce programming model. Our implementation of this index construction algorithm gains approximately linear speedup on a 64-nodes high-performance cluster in our experiment.