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

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.