As NAND flash memory becomes increasingly popular as data storage for embedded systems, many file systems and database management systems are being built on it. They require an efficient index structure to locate a particular item quickly from a huge amount of directory entries or database records. This paper proposes μ-Tree, a new ordered index structure tailored to the characteristics of NAND flash memory. μ-Tree is a balanced tree similar to $B^+-Tree$. In μ-Tree, however, all the nodes along the path from the root to the leaf are put together into a single flash memory page in order to minimize the number of flash write operations when a leaf node is updated. Our experimental evaluation shows that μ-Tree outperforms $B^+-Tree$ by up to 78% for traces extracted from real workloads.
낸드 플래시 메모리는 최근 수년간 휴대형 기기들의 저장장치로 각광받아 왔다. 기술이 발전함에 따라 낸드 플래시 메모리의 용량이 커졌고, 점차 저장 할 수 있는 데이터가 늘어갔다. 그에 따라, 기기내의 파일 시스템이나 데이터베이스 같은 시스템에서는 많은 양의 디렉터리 엔트리나 레코드로부터 빨리 원하는 데이터를 접근할 수 있는 색인구조를 필요로 하게 되었다. 낸드 플래시 메모리 위에 B-트리를 사용할 경우, 같은 곳에 재기입이 안 되는 낸드 플래시의 특성 때문에, 리프노드에 수정이 가해지게 되면 노드의 물리적 위치가 바뀌게 된다. 그에 더해, 이전의 리프 노드를 가리키고 있던 인덱스 노드 역시 다시 써주게 되어, 리프노드 한 개를 수정하기 위해 리프부터 루트까지의 모든 노드를 다시 써주어야 한다. 기존방식은 노드가 하나의 플래시 페이지에 들어가도록 설계되어, 필연적으로 여러 번의 플래시의 쓰기동작을 수행하게 된다. 본 논문에서는 낸드 플래시 메모리의 특성을 잘 고려하여 디자인된 색인구조인 μ-트리를 제안한다. μ-트리는 B-트리에 기반 한 색인구조로서, 리프노드부터 루트노드까지의 모든 노드를 한 개의 플래시 페이지에 저장함으로써, 리프 노드 갱신 시에 소요되는 플래시 쓰기동작을 최소화시켰다. 또한, 다양한 환경에서의 실험을 통해 μ-트리가 기존방식에 비해 최대 78%까지 성능을 높일 수 있음을 보였다.
