Abstract:

Aiming at the problems of low query efficiency and limited query types in on-chain data querying of blockchain systems， an inter-block index model was proposed. Firstly， for discrete attributes within blocks， Inverted Bloom Filters （IBFS） index was introduced. When querying data using IBFS， it allows for locating target block in O（1） time complexity without all block traversal. Secondly， for continuous attributes， the clustering algorithm was employed to calculate fine-grained data distribution intervals in block， and Dual-Layer Clustering Chain （DLCC） index was constructed by combining with maximum/minimum values of the data in block， thereby enabling the filtering of more non-target blocks during querying data. Finally， based on the proposed index model， various query algorithms were designed and implemented. Experimental results show that compared with tree Bloom filter index， IBFS index reduces the storage space by 51.0%， and shorten the time to locate target blocks by 75.9%； compared with start-end interval index， DLCC index reduces the number of located blocks during range query by 55.5%.

Key words: blockchain, query optimization, index model, Bloom filter, clustering algorithm

摘要：

针对区块链系统链上数据查询中查询效率低和查询类型少的问题，提出一种区块间索引模型。首先，对于区块中的离散型属性，提出倒排布隆过滤器（IBFS）索引；使用该索引查询数据时无需遍历全部区块，可以在O（1）时间复杂度内定位到目标区块；其次，对于连续型属性，使用聚类算法计算区块内数据的细粒度分布区间，并结合区块内数据的最大最小值构建双层聚类链表（DLCC）索引，从而在查询数据时可过滤更多不含目标数据的区块；最后，在所提索引模型的基础上，设计并实现多种查询算法。实验结果表明，与树型布隆过滤器索引相比， IBFS索引占用的存储空间降低了51.0%，定位到目标区块的时间减少了75.9%；与起止区间索引相比， DLCC索引在范围查询时定位到的区块数减少了55.5%。

关键词: 区块链, 查询优化, 索引模型, 布隆过滤器, 聚类算法