Lazy-update B+-tree for flash devices

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

19 Citations (Scopus)

Abstract

With the rapid increasing capacity of flash chips, 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 a new indexing method, called lazy-update B+-tree, to overcome the limitations of flash memory. The basic idea is to defer the time of committing update requests to the B+-tree by buffering them in a segment of main memory. They are later committed in groups so that 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 the problem. Simulation results show that the proposed lazyupdate 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
Title of host publicationProceedings - 2009 10th International Conference on Mobile Data Management
Subtitle of host publicationSystems, Services and Middleware, MDM 2009
Pages323-328
Number of pages6
DOIs
Publication statusPublished - 5 Oct 2009
Externally publishedYes
Event2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009 - Taipei, Taiwan
Duration: 18 May 200920 May 2009

Conference

Conference2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009
Country/TerritoryTaiwan
CityTaipei
Period18/05/0920/05/09

ASJC Scopus subject areas

  • Engineering(all)

Cite this