Linked Block-based Multiversion B-Tree index for PCM-based embedded databases

Chun Jiang Zhu, Kam Yiu Lam*, Yuan Hao Chang, Joseph K Y NG

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

3 Citations (Scopus)


In this paper, by exploring the application characteristics of cyber-physical systems (CPS) and the performance characteristics of PCM, we propose a new B-tree index structure, called Linked Block-based Multi-Version B-Tree (LBMVBT), for indexing multi-version data in an embedded multi-version database for CPS. In LBMVBT, to reduce the number of writes to PCM in maintaining the index and improve the efficiency in serving version-range queries, we introduce the block-based scheme for indexing in which multiple versions of a data item are grouped into a version block to be indexed by a single entry in the multi-version index. To reduce the index re-organization cost (i.e., number of writes to PCM) due to node overflow and underflow, we add external entries in each index leaf node so that a node re-organization can be done by only updating pointers without copying the index entries of the re-organized leaf nodes to the new node. Analytic studies have been performed on LBMVBT and a series of experiments has been conducted to evaluate the efficacy of LBMVBT. The experimental results show that LBMVBT can effectively reduce the number of writes to the index and achieve a good overall performance on serving update transactions while version-range queries can be served with smaller number of reads to the index compared with MVBT.

Original languageEnglish
Pages (from-to)383-397
Number of pages15
JournalJournal of Systems Architecture
Issue number9
Publication statusPublished - 9 Oct 2015

Scopus Subject Areas

  • Software
  • Hardware and Architecture

User-Defined Keywords

  • Cyber-physical systems
  • Embedded systems
  • Multi-version index
  • Phase change memory


Dive into the research topics of 'Linked Block-based Multiversion B-Tree index for PCM-based embedded databases'. Together they form a unique fingerprint.

Cite this