Space-efficient index scheme for PCM-based multiversion databases in cyber-physical systems

Yuan Hung Kuan, Yuan Hao Chang, Tseng Yi Chen, Po Chun Huang, Kam Yiu Lam

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


In this article, we study the indexing problem of using PCM as the storage medium for embedded multiversion databases in cyber-physical systems (CPSs). Although the multiversion B+-tree (MVBT) index has been shown to be efficient in managing multiple versions of data items in a database, MVBT is designed for databases residing in traditional block-oriented storage devices. It can have serious performance problems when the databases are on phase-change memory (PCM). Since the embedded multiversion database in CPSs may have limited storage space and are update intensive, to resolve the problems of MVBT of lack of space efficiency and heavy update cost, we propose a new index scheme, called space-efficient multiversion index (SEMI), to enhance the space utilization and access performance in serving various types of queries. In SEMI, since the number of keys in the database may be small, instead of using a B-tree index, we propose to use a binary-search tree to organize the index keys. Furthermore, multiple versions of the same data item may be stored consecutively and indexed by a single entry to maximize the space utilization and at the same time to enhance the performance in serving version-range queries. Analytical studies have been conducted on SEMI, and a series of experiments have been performed to evaluate its performance as compared with MVBT under different workloads. The experimental results have demonstrated that SEMI can achieve very high space utilization and has better performance in serving update transactions and range queries as compared with MVBT.

Original languageEnglish
Article number21
JournalACM Transactions on Embedded Computing Systems
Issue number1
StatePublished - Oct 2016


  • Cyber-physical systems
  • Embedded database
  • Multiversion index
  • Phase-change memory (PCM)


Dive into the research topics of 'Space-efficient index scheme for PCM-based multiversion databases in cyber-physical systems'. Together they form a unique fingerprint.

Cite this