计算机科学 ›› 2025, Vol. 52 ›› Issue (8): 146-153.doi: 10.11896/jsjkx.240700127
陈根深1,2,3,4,5, 刘刚1,2,3,4,5, 董洋3,4, 范文遥1,2,4,5, 易强1,2, 姜子鑫3,4
CHEN Genshen1,2,3,4,5, LIU Gang1,2,3,4,5, DONG Yang3,4, FAN Wenyao1,2,4,5, YI Qiang1,2, JIANG Zixin3,4
摘要： 三维地质块体模型中大量的零值或空值使得基于B+树的属性索引结构频繁分裂和调整,导致索引维护成本高;同时,B+树的单向链表结构加剧了大规模块体模型中数据顺序遍历和范围查询效率低下的问题。为此,提出了一种基于Inverted-B+树(IBT)的索引方法。该方法通过构建IBT索引结构,在将重复键插入叶子节点时,为每个重复键创建倒排节点,从而有效减少了数据处理中的结构调整。通过在内部节点存储中间索引值来加速查询过程,并在叶子节点和倒排节点之间建立双向链表,实现了从任意叶子节点按顺序访问整个数据集从而进行高效的范围查询。利用三维地质结构模型经过体元剖分、插值和降维处理所得到的6个块体模型进行测试,结果表明:与传统B+树相比,IBT方法在索引构建时间、空间占用和查询性能方面均有显著提升,特别是在处理大规模数据集中,其索引构建效率提升了71%,空间占用减少了83%,查询效率得到了显著提升。
中图分类号:
| [1]WU C L,LIU G,ZHOU Q,et al.Fundamental problems of integrated application of big data in geoscience[J].Bulletin of Geological Science and Technology,2020,39(4):1-11. [2]LIU G,WU C L,HE Z W,et al.Data model for geological spatio-temporal big data expression and storage management[J].Bulletin of Geological Science and Technology,2020,39(1),164-174. [3]ZHOU Q,WU C L,HU X Y,et al.A new metallogenic model for the giant manganese deposits in northeastern Guizhou,China[J].Ore Geology Reviews,2022,149:105070. [4]CHEN G S,GUO X L,LIU G,et al.3D geological modeling in the typical area of karst basin on the south bank of the Yangtze river in Yichang city [J].Safety and Environmental Enginee-ring,2019,26(2):1-8. [5]LIU G,CHEN G S,CHEN Q Y,et al.Key technologies for efficient visualization of large scale 3D spatial models based on web[J].Geospatial Information,2023,21(12):8-13. [6]LIU L,SUN Y,JI M,et al.Efficient Construction of VoxelModels for Ore Bodies Using an Improved Winding Number Algorithm and CUDA Parallel Computing[J].ISPRS Internatio-nal Journal of Geo-Information,2023,12(12):473. [7]LI J,LIU P R,LIANG Z X,et al.Three-dimensional geological modeling method of regular voxel splitting based on multi-source data fusion[J].Rock and Soil Mechanics,2021,42(4):1170-1177. [8]SMIRNOVA A D,CHEN S J,MIKHAYLOVA T V.Geological Mathematical Block Modelling in Kuzbass Mining Industry[C]//2022 IEEE International Multi-Conference on Enginee-ring,Computer and Information Sciences(SIBIRCON).IEEE,2022:1970-1973. [9]CUI Z S,CHEN Q Y,LIU G.A two-stage downscaling hydrological modeling approach via convolutional conditional neural process and geostatistical bias correction[J].Journal of Hydro-logy,2023,620:129498. [10]WANG Z Y,ZUO R G,YANG F F.Geological mapping using direct sampling and a convolutional neural network based on geochemical survey data[J].Mathematical Geosciences,2023,55(7):1035-1058. [11]JIN X,WANG G W,TANG P,et al.3D geological modeling and uncertainty analysis for 3D targeting in Shanggong gold deposit(China)[J].Journal of Geochemical Exploration,2020,210:106442. [12]WELLMANN F,CAUMON G.3-D Structural geological mo-dels:Concepts,methods,and uncertainties[M]//Advances in geophysics.Elsevier,2018:1-121. [13]LIU Y Y,ZHANG X W,GUO W,et al.Research Status of and Trends in 3D Geological Property Modeling Methods:A Review[J].Applied Sciences,2022,12(11):5648. [14]HOULDING S.3D geoscience modeling:computer techniquesfor geological characterization[M].Springer Science & Business Media,2012. [15]LI M X,WANG H C,DAI H P,et al.A Survey of Multi-Dimensional Indexes:Past and Future Trends[J].IEEE Transactions on Knowledge and Data Engineering,2024,36(8):3635-3655. [16]MAMOULIS N.Spatial data management[M].Beijing:Springer Nature,2022. [17]PAN J J,WANG J,LI G.Survey of vector database management systems[J].The VLDB Journal,2024,33(5):1591-1615. [18]CHEN G S,LIU G,CHEN Q,et al.Key technologies and application of 3D spatial data management system for mining based on multi-source data integration and WebGIS[J].Software Guide,2023,22(11):18-28. [19]CAO K Y,LIU Y F,DONG Y K,et al.Hilbert R-tree Space Indexing Based on RHCA Clustering[C]//International Confe-rence on Smart Technologies and Systems for Internet of Things.Singapore:Springer Nature Singapore,2021:205-211. [20]CHENG H,XIE K,WEN C,et al.Fast visualization of 3D massive data based on improved Hilbert R-tree and stacked LSTM models[J].IEEE Access,2021,9:16266-16278. [21]ZHANG Y N,ZHANG A M,GAO M,et al.Research on Three-Dimensional Electronic Navigation Chart Hybrid Spatial Index Structure Based on Quadtree and R-Tree[J].ISPRS Internatio-nal Journal of Geo-Information,2022,11(5):319. [22]LIU Z B,CHEN L,YANG A R,et al.Hiindex:An efficient spatial index for rapid visualization of large-scale geographic vector data[J].ISPRS International Journal of Geo-Information,2021,10(10):647. [23]WANG Y Z,LYU H,MA Y Q.Geological tetrahedral model-oriented hybrid spatial indexing structure based on Octree and 3D R*-tree[J].Arabian Journal of Geosciences,2020,13(15):728. [24]CHAUDHRY N,YOUSAF M M.A hash-based index for processing frequent updates and continuous location-based range queries[J].Knowledge and Information Systems,2023,65(10):4233-4271. [25]SAFACE S,MIRABI M,RAHMANI A M,et al.A distributed B＋Tree indexing method for processing range queries over streaming data[J].Cluster Computing,2023,27:1251-1274. [26]DE MOL R,BARRANCO C D,DE TRÉ G.Indexing possibilistic numerical data using interval B+-trees[J].Fuzzy Sets and Systems,2021,413:138-154. [27]JIANG H,KANG J F,DU Z H,et al.Vector spatial big data storage and optimized query based on the multi-level Hilbert grid index in HBase[J].Information,2018,9(5):116. [28]LIU H,YAN J N,WANG J L,et al.HGST:A Hilbert-GeoSOT Spatio-Temporal Meshing and Coding Method for Efficient Spatio-Temporal Range Query on Massive Trajectory Data[J].ISPRS International Journal of Geo-Information,2023,12(3):113. [29]LEI Y,TONG X C,WANG D L,et al.W-Hilbert:A W-shaped Hilbert curve and coding method for multiscale geospatial data index[J].International Journal of Applied Earth Observation and Geoinformation,2023,118:103298. |
|
||
首页