낸드 플래시 메모리 상에서 효율적인 MR-트리 동작을 위한 지연 연산 기법 = Delay Operation Techniques for Efficient MR-Tree on Nand Flash Memory

국문 초록 (Abstract)

플래시 메모리 중 저장장치로 사용되는 낸드 플래시 메모리는 유비쿼터스 및 모바일 환경에 적합한 특성으로 다양한 분야의 저장장치로 이용되고 있으며 효율적인 활용을 위한 많은 연구가 진행되고 있다. 모바일 환경에서 이용할 수 있는 멀티미디어 데이타베이스 시스템을 위한 인덱스로써 공간 데이타 액세스가 가능한 R-트리의 검색성능을 향상 시킨 MR-트리는 메인 메모리 데이타베이스 시스템에서 캐쉬 미스를 줄이고 중간 노드의 이용률을 높임으로써 연산 성능을 높일 수 있는 특성을 가진다. 본 논문에서는 검색 성능이 좋은 MR-트리를 활용하여 낸드 플래시 메모리 기반에서 효율적인 동작을 위한 지연 연산 기법을 제안하였다. MR-트리의 노드 크기를 낸드 플래시 메모리의 쓰기 연산 단위에 맞추고 인덱스 수정 연산 시 노드 크기만큼 지연 연산하여 쓰기 연산으로 인한 플래시 메모리에서의 추가적인 비용을 줄이고 연산 횟수를 줄여 인덱스 성능을 향상 시켰다.

다국어 초록 (Multilingual Abstract)

Embedded systems usually utilize Flash Memories with very nice characteristics of non-volatility, low access time, low power and so on. For the multimedia database systems, R-tree is an indexing tree with nice characteristics for multimedia access. MR-tree, which is an upgraded version of R-tree, has shown better performance in searching, inserting and deleting operations than R-tree. Flash memory has sectors and blocks as a unit of read, write and delete operations. Especially, the delete is done on a unit of 512 byte blocks with very large operation time and it is also known that read and write operations on a unit of block matches caching nature of MT-tree. Our research optimizes MR-tree operations in a unit of Flash memory blocks. Such an adjusting leads in better indexing performance in database accesses. With MR-tree on a 512B block units we achieved fast search time of database indexing with low height of MR-tree as well as faster update time of database indexing with the best fit of flash memory blocks. Thus MR-tree with optimized operations shows good characteristics to be a database index schemes on any systems with flash memory.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. MR-트리
• 4. MR-트리와 플래시 메모리
• 5. 실험 결과
• 6. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

1 남정현, "제2호" 34 (34): 109-118, 2007

2 "SAMSUNG NAND flash SLC-small block"

3 Chanik Park, "Energy aware demand paging on Nand Flash-based embedded storages" 2004

4 Chin-Hsien Wu, "An efficient R-tree implementation over flash- memory storage systems" 2003

5 Chin-Hsien Wu, "An efficient B-tree layer for flash memory storage systems" 2003

6 Eran Gal, "Algorithms and data structures for flash memories" ACM Computing Surveys(CSUR) 138-163, 2005

7 Kyung-Chang Kim, "A cache-conscious main memory spatial index structure for mobile GIS, Web and wireless geographic information systems" 167-180, 2004