Efficient and lightweight indexing approach for multi-dimensional historical data in blockchain

【Author】 Singh, Bikash Chandra; Ye, Qingqing; Hu, Haibo; Xiao, Bin

【Source】FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE

【影响因子】7.307

【Abstract】In blockchain systems, stateful data are stored globally and sequentially in the form of key-value pairs. Indeed, in addition to being one-dimensional, values can be multi-dimensional. However, in blockchain systems, existing works only consider one-dimensional data to implement indexing approaches, as a result, these approaches perform poorly when extended to multi-dimensional and historical data. To overcome these issues, in this paper we propose two new indexing models for blockchain. The first model is Two-tier Deterministic Appended Only Skip List (TDASL) that improves from LineageChain (Ruan et al., 2019, 2021) by using an additional indexing layer on top of a skip list to quickly retrieve the state versions and by using prefixes to query multi-dimensional state versions. The second model is Predefined Partitioned B-plus Tree (PPBPT), which paves the way of adopting B-plus tree in blockchain by addressing the challenge of its heavy reconstruction cost upon updates. To do so, PPBPT copies a predefined B-plus tree, which is used for generating indexes for blockchain historical data, thereby reducing reconstruction costs. We conduct extensive experiments to verify the effectiveness of the proposed approaches under various parameter settings.(c) 2022 Published by Elsevier B.V.

【Keywords】Blockchain; Distributed ledger; Index; Blockchain state query; B-plus tree; Skip list

【发表时间】2023 FEB

【收录时间】2022-11-15

【文献类型】实证数据

【主题类别】

区块链技术-核心技术-分布式存储