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 language | English |
---|---|
Title of host publication | Proceedings - 2009 10th International Conference on Mobile Data Management |
Subtitle of host publication | Systems, Services and Middleware, MDM 2009 |
Pages | 323-328 |
Number of pages | 6 |
DOIs | |
Publication status | Published - 5 Oct 2009 |
Externally published | Yes |
Event | 2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009 - Taipei, Taiwan Duration: 18 May 2009 → 20 May 2009 |
Conference
Conference | 2009 10th International Conference on Mobile Data Management: Systems, Services and Middleware, MDM 2009 |
---|---|
Country/Territory | Taiwan |
City | Taipei |
Period | 18/05/09 → 20/05/09 |
ASJC Scopus subject areas
- General Engineering