본문 바로가기

LSM HB-Tree: An LSM Tree Augmented With Hierarchical B-Tree for Efficient Range Query Processing on Blockchain Data

문서 유형
연구출판물 · 학술지 논문
등재
SCIEScopus
저널 순위
JCR Q2Scopus Q1
저널
IEEE ACCESS13 · pp.194596 · 2025
피인용
Web of Science 0Scopus 0
FWCI (Scopus)
0
JCR IF
JCR 2024 3.6
ISSN
2169-3536

저자

  1. 이병영제1저자Pusan Natl Univ, Dept Informat Convergence Engn, Busan 46241, South Korea
  2. 변경수Pusan Natl Univ, Dept Informat Convergence Engn, Busan 46241, South Korea
  3. 권준호교신저자Pusan Natl Univ, Grad Sch Data Sci, Dept Data Sci, Busan 46241, South Korea

초록

With the rapid proliferation of blockchain technology, the volume of stored data has increased dramatically. Existing blockchain systems typically employ a key-value storage model, which is efficient for single-key lookups but inadequate for complex queries such as value-based conditional searches and range queries. Although several studies have attempted to support complex queries by integrating external databases, such approaches inherently suffer from integrity and synchronization issues. To address these limitations, we propose and implement an LSM-Tree augmented with hierarchical, level-specific B-tree indexes (referred to as LSM HB-tree). The proposed architecture augments the conventional LSM-Tree hierarchy with level-specific B-tree indexes, thereby supporting composite key indexing and improving the efficiency of data retrieval within on-chain storage. Index construction builds a B-tree index for SSTables at each level, thereby reducing disk access costs and significantly improving the performance of equality and range queries. We evaluate the system by varying the SSTable threshold from 2 MiB to 32 MiB and observe that an 8 MiB threshold provides the best trade-off between write latency and query efficiency. Under this configuration, experiments with equality and range queries under selectivity levels ranging from 0.01% to 100% demonstrate that LSM HB-tree substantially reduces query latency compared to the conventional LSM-Tree. Furthermore, multi-threaded experiments with up to 16 threads reveal that the best performance for both equality and range queries is achieved with four threads. Collectively, these results confirm that LSM HB-tree is a practical and effective index structure for supporting efficient complex queries entirely within the internal blockchain architecture.

키워드

BlockchainsTrees (botanical)IndexingQuery processingSynchronizationDatabasesCompactionResearch and developmentMetadataThroughputBlockchainLSM-treeB-treerange query processinghierarchical indexingparallel query execution

식별자

Scopus EID
2-s2.0-105022415737
WoS UID
001619067900002