분할상태목록을 이용한 NAND 플래시 메모리를 위한 선형해시 인덱스

Abstract

최근 NAND 플래시 메모리는 빠른 접근 속도, 높은 내구성, 작은 크기 및 저 전력 소모 등의 특성으로 인하여 차세대 대용량 저장 장치로 각광 받고 있다. 그러나 NAND 플래시 메모리는 비대칭적인 읽기∙ 쓰기∙ 소거 연산 처리 속도와 제자리 갱신이 불가능한 물리적인 특성으로 인하여 대표적인 디스크 기반 인덱스 구조 중의 하나인 해시 인덱스 구조를 NAND 플래시 메모리상에서 직접 구현하였을 경우 오버플로 체인에 의한 추가적인 쓰기∙ 소거 연산으로 인해 성능 저하가 일어날 수 있다. 이러한 성능 저하를 피하기 위해 New Dynamic Hash가 제안되었으나, 키 값 검색 시 하나 이상의 버켓들을 검색해야 하며, 여전히 오버플로 체인에 의해 추가적인 쓰기∙ 소거 연산이 여전히 발생하는 문제점을 해결하지 못 하였다. 본 논문에서는 버켓 오버플로 발생 시 오버플로 체인 대신 분할상태목록을 이용하는 NAND 플래시 메모리에 최적화된 선형 해시 구조(LHF)를 제안한다. LHF는 분할상태목록을 사용함으로써 분할 연산 시 오버플로 체인에 의한 추가적인 소거 연산을 발생 시키지 않으며, 검색 연산 시 오직 하나의 버켓만을 검색하여 빠른 검색속도를 보장한다. 기존의 해시 인덱스 구조와 비교 측정을 통하여 성능의 우수성을 보인다.