Volume 6 Number 7 (Jul. 2011)
Home > Archive > 2011 > Volume 6 Number 7 (Jul. 2011) >
JCP 2011 Vol.6(7): 1307-1318 ISSN: 1796-203X
doi: 10.4304/jcp.6.7.1307-1318

An Efficient Buffer Scheme for Flash-based Databases

Liang Huai Yang1, Jing Wang1, Zhifeng Huang1, Weihua Gong1, Lijun Chen2
1College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, China
2School of Information Science and Technology, Peking University, Beijing, China

Abstract—Most embedded database systems are built on a two-level memory hierarchy, a RAM buffer on top of flash memory. Both kinds of memories have limited capacity, thus, how to efficiently utilize them is critical for embedded systems with resource restrictions. Different from magnetic hard disk, flash memory has speed asymmetry in reads and writes, i.e., random reads are over an order of magnitude faster than random writes. -tree [9] is the state-of-theart index supporting efficient random updates on the flash memory. However, we found that the traditional page based buffer scheme(LRU-P for short) under-utilized the RAM space. To improve the utilization on the memory resources and the query performance, we propose a novel buffer scheme called LRU-N – a node-based LRU policy for the RAM buffer. In addition, to increase the utilization of the flash memory, we also present a k-partitioning strategy for - tree. LRU-N uses a page address swizzling scheme to exploit the co-related locality of accessing multiple tree nodes in the -tree. The k-partitioning strategy determines an optimal k value for space efficiency by allocating more flash memory to the leaf nodes and guarantees sufficient space for tree growth. Our experiments conducted on both simulated data sets of various distributions and real-world data sets show that LRU-N can significantly improve buffer hit rate up to 65% for the best cases over the page-based scheme LRU-P; even with small buffer size, LRU-N can also achieve rather good performance. And our proposed k-partitioning strategy can effectively reduce the index size up to 33% over -tree.

Index Terms—Buffer scheme, LRU, -Tree, flash DB


Cite: Liang Huai Yang, Jing Wang, Zhifeng Huang, Weihua Gong, Lijun Chen , "An Efficient Buffer Scheme for Flash-based Databases," Journal of Computers vol. 6, no. 7, pp. 1307-1318, 2011.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>