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

Bikash Chandra Singh, Qingqing Ye, Haibo Hu, Bin Xiao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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.

Original languageEnglish
Pages (from-to)210-223
Number of pages14
JournalFuture Generation Computer Systems
Volume139
DOIs
Publication statusPublished - Feb 2023

Keywords

  • B-plus tree
  • Blockchain
  • Blockchain state query
  • Distributed ledger
  • Index
  • Skip list

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Efficient and lightweight indexing approach for multi-dimensional historical data in blockchain'. Together they form a unique fingerprint.

Cite this