Flash-optimized B+-tree

Sai Tung On, Haibo Hu, Yu Li, Jianliang Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

With the rapid increasing capacity of flash memory, flash-aware indexing techniques are highly desirable for flash devices. The unique features of flash memory, such as the erase-before-write constraint and the asymmetric read/write cost, severely deteriorate the performance of the traditional B+-tree algorithm. In this paper, we propose an optimized indexing method, called lazy-update B+-tree, to overcome the limitations of flash memory. The basic idea is to defer the committing of update requests to the B+-tree by buffering them in a segment of main memory. They are later committed in groups so that the cost of each write operation can be amortized by a bunch of update requests. We identify a victim selection problem for the lazy-update B+-tree and develop two heuristic-based commit policies to address this problem. Simulation results show that the proposed lazy-update method, along with a well-designed commit policy, greatly improves the update performance of the traditional B+-tree while preserving the query efficiency.
Original languageEnglish
Pages (from-to)509-522
Number of pages14
JournalJournal of Computer Science and Technology
Volume25
Issue number3
DOIs
Publication statusPublished - 1 May 2010
Externally publishedYes

Keywords

  • B+-tree
  • Flash memory
  • Indexing
  • Lazy update

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this