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 asymme...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.展开更多
基金supported by the Research Grants Council of Hong Kong under Grant No. HKBU210808the National Natural Science Foundation of China under Grant No. 60833005
文摘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.
