SBBF: A Space-Efficient Buffer Management Scheme for B+-Trees on NAND Flash Memory
2
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
NAND flash memory is becoming widely used as storage media for various mobile devices such as smart phones, portable media players (PMPs), digital cameras, and laptops. As the capacity of flash memory increases, the use of index structures on flash memory becomes more important. The B+-tree is one of the most popular index structures used in disk-based storage systems. However, due to the unique characteristics of flash memory, such as erase-before-write, and asymmetric read/write speed, the direct application of B+-tree index structures to flash-based storage systems incurs excessive write overhead. In this paper, we propose a space-efficient buffer management scheme for B+-trees on NAND flash memory, called SBBF. The proposed scheme stores changes made to a B+-tree in the buffer to reduce the number of write requests to flash memory. Compared to previous work, the proposed scheme can store more changes in the same size buffer by optimizing the use of the buffer space. Consequently, the number of write requests to flash memory is significantly reduced. The experimental results with real workloads show that the proposed scheme outperforms previous work by over 15% in terms of the number of write requests to flash memory.
Abstract
NAND flash memory is becoming widely used as storage media for various mobile devices such as smart phones, portable media players (PMPs), digital cameras, and laptops. As the capacity of flash memory increases, the use of index structures on flash memory becomes more important. The B+-tree is one of the most popular index structures used in disk-based storage systems. However, due to the unique characteristics of flash memory, such as erase-before-write, and asymmetric read/write speed, the direct application of B+-tree index structures to flash-based storage systems incurs excessive write overhead. In this paper, we propose a space-efficient buffer management scheme for B+-trees on NAND flash memory, called SBBF. The proposed scheme stores changes made to a B+-tree in the buffer to reduce the number of write requests to flash memory. Compared to previous work, the proposed scheme can store more changes in the same size buffer by optimizing the use of the buffer space. Consequently, the number of write requests to flash memory is significantly reduced. The experimental results with real workloads show that the proposed scheme outperforms previous work by over 15% in terms of the number of write requests to flash memory.
참고문헌 (12)
- A. Leventhal, "Flash storage memory", Communications of ACM, 51(7), pp.47~51 (2008)
- E. Gal, "Algorithms and data structures for flash memories", ACM Computing Surveys, 37(2) (2005)
- S. Lee, "Design of flash-based DBMS: an in-page logging approach", Proceedings of the ACM SIGMOD Conference, pp.55~66 (2007)
- J. Kim, "A space-efficient flash translation layer for compact flash systems", IEEE Transactions on Consumer Electronics, 48(2) (2002)
- S. Lee, "A log buffer-based flash translation layer using ful-ly-associative sector translation", ACM Transactions on Embedded Computing Systems, 6(3) (2007)
- C. Wu, "An efficient B-tree layer implementation for flash-memory storage", ACM Transactions on Embedded Computing Systems, 6(3) (2007)
- Hyun-Seob Lee, "An efficient index buffer management scheme for implementing a B-tree on NAND flash memory", Data & Knowledge Engineering, 901~916 (2010)
- Douglas Comer, "The ubiquitous B-tree", ACM Computing Surveys, 11(2), pp.121~137 (1979)
- K. Lee, "Design and implementation of MLC NAND flash-based DBMS for mobile devices", JOURNAL OF SYSTEMS AND SOFTWARE, 82(9), pp.1447~1458, ELSEVIER SCIENCE INC
- Y. Kim, "Page- Differential Logging: An Efficient DBMS-Independent Approach for Storing Data into Flash Memory", Proceedings of the ACM SIGMOD Conferecne, pp.363~374 (2010)
- D. Kang, "μ-tree: an ordered index structure for NAND flash memory", In Proceedings of the ACM & IEEE International Conference on Embedded Software, pp.144~153 (2007)
- "Reiser File System"[URL]