Block-based multi-version B+-tree for flash-based embedded database systems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

11 Scopus Citations
View graph of relations

Author(s)

  • Jiantao Wang
  • Kam-Yiu Lam
  • Yuan-Hao Chang
  • Jen-Wei Hsieh
  • Po-Chun Huang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6747989
Pages (from-to)925-940
Journal / PublicationIEEE Transactions on Computers
Volume64
Issue number4
Online published24 Feb 2014
Publication statusPublished - Apr 2015

Abstract

In this paper, we propose a novel multi-version B+-tree index structure, called block-based multi-version B+-tree ( BbMVBT), for indexing multi-versions of data items in an embedded multi-version database (EMVDB ) on flash memory. An EMVDB needs to support streams of update transactions and version-range queries to access different versions of data items maintained in the database. In BbMVBT, the index is divided into two levels. At the higher level, a multi-version index is maintained for keeping successive versions of each data item. These versions are allocated consecutively in a version block. At the lower level, a version array is used to search for a specific data version within a version block. With the reduced index structure of BbMVBT, the overhead for managing the index in processing update operations can be greatly reduced. At the same time, BbMVBT can also greatly reduce the number of accesses to the index in processing version-range queries. To ensure sufficient free blocks for creating version blocks for efficient execution of BbMVBT, in this paper, we also discuss how to perform garbage collection using the purging-range queries for reclaiming 'old' versions of data items and their associated entries in the index nodes. Analysis of the performance of BbMVBT is presented and verified with performance studies using both synthetic and real workloads. The performance results illustrate that BbMVBT can significantly improve the read and write performance to the multi-version index as compared with MVBT even though the sizes of the version blocks are not large.

Research Area(s)

  • Embedded databases, flash memory, index structure, multi-version data, real-time data

Citation Format(s)

Block-based multi-version B+-tree for flash-based embedded database systems. / Wang, Jiantao; Lam, Kam-Yiu; Chang, Yuan-Hao; Hsieh, Jen-Wei; Huang, Po-Chun.

In: IEEE Transactions on Computers, Vol. 64, No. 4, 6747989, 04.2015, p. 925-940.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review