최근 NAND 플래시 메모리는 빠른 접근 속도, 가벼운 무게, 적은 전력소모, 충격에 강한 내 구성 때문에 하드디스크를 대체할 저장 매체로 주목 받고 있다. 그러나, NAND 플래시 메모리는 디스크 기반의 저장장치와 다르게 읽기 쓰기 소거 연산 처리 속도와 제자리 갱신이 불가능한 물리적인 특성을 가지고 있다. 이러한 특징들로 인해 디스크 기반의 대표적인 인덱스 구조 중에 하나인 해시 인덱스를 NAND 플래시 메모리 상에 그대로 구현하였을 때, 여러 문제가 발생할 수 있다. 특히, 레코드가 빈번하게 삽입, 삭제, 갱신되면 대량의 제자리 갱신이 발생하여 플래시 메모리에서 느린 쓰기 연산과 소거 연산이 수행되어 성능이 저하된다. 본 논문에서는 이러한 성능 저하를 피하기 위하여 버켓 오버 플로우 발생 시 분할 연산을 수행하지 않고, 각 버켓에 오버플로우 버켓을 사용하여 분할 연산을 최대한 지연시켜 쓰기 및 소거 연산을 줄이는 인덱스 구조를 제안한다. 또한, 각 버켓에 대한 오버플로우 버켓의 수를 적용적으로 유지함으로써 갱신 및 삭제 비율에 따라 오버플로우 버켓을 유지하여 추가적인 읽기 쓰기 연산을 줄인다. 본 논문은 기존의 확장형 해시 인덱스 구조와 수학적 분석 및 다양한 실험을 통하여 비교함으로써 제안하는 인덱스 구조의 우수성을 보인다.
Recently, NAND Flash memory has become an alternative storage system for a storage device because of its rapid access speed, shock-resistant, small size and lower power consumption. However, compared to the disk-based storage device, NAND flash memory has several hardware limitations such as asymmetric speed of read, write and erase operation and no in-place update, so that hash index structure, one of the popular disk-based index structure, may result in severe performance degradation if it is directly deployed on NAND flash memory. Especially, frequent insertion, deletion, and update operations lead to an enormous amount of in-place update operations that invoke a number of slow write operations and erase operations, hence result in performance degradation. In this paper, we propose a new index structure that delays a split operation which causes additional write and erase operations by using overflow buckets when bucket overflow occurs rather than immediate invocation of split operations. Also, we present a new overflow bucket maintenance policy that can reduce the number of additional read/write operations by adaptively handling the number of overflow buckets according to the update/erase ratio for each bucket. Finally, we show the superiority of the proposed index structure by comparing it to traditional extendible hash index through mathematical analysis and various experiments.
