earticle

영어

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.

한국어

NAND 플래시 메모리는 스마트 폰, 휴대용 미디어 플레이어, 디지털 카메라, 노트북 등과 같은 다양한 모바일 장치의 저장 매체로서 사용이 점차 증대되고 있다. 플래시 메모리의 용량이 증가하면서, 플래시 메모리에서의 색인 구조의 사용도 점차 중요해지고 있다. B+-트리는 디스크 기반의 저장 시스템에서 가장 널리 쓰이는 인덱스 구조 중의 하나이다. 그러나 ‘쓰기 전 삭제’와 ‘비대칭적인 읽기/쓰기 속도’와 같은 플래시 메모리의 독특한 특성으로 인해, B+-트리 색인을 플래시 기반의 저장 시스템에 바로 적용하는 것은 심각한 쓰기 비용을 초래한다. 본 논문에서는 SBBF라 불리는, NAND 플래시 메모리에서의 B+-트리를 위한 공간 효율적인 버퍼 관리 기법을 제안한다. 제안 기법은 플래시 메모리로 보내지는 쓰기 요청의 수를 줄이기 위해, B+-트리의 변경 사항들을 버퍼에 저장한다. 기존 연구와 비교하여, 제안하는 방법은 버퍼 공간의 사용을 최적화하여 동일한 크기의 버퍼에 더 많은 변경 사항들을 저장할 수 있다. 이로 인해 플래시 메모리로 보내지는 쓰기 요청의 수를 크게 감소시킬 수 있다. 실제 데이터를 사용한 실험 결과를 통해, 제안 방법은 플래시 메모리로 보내지는 쓰기 요청의 수 측면에서 기존 방법에 비해 15% 이상의 성능 향상을 가져옴을 보인다.