효율적 범위 검색을 위한 플래시 메모리 기반 B+-트리

국문 초록 (Abstract)

지난 수십 년간 B+-트리는 디스크 기반 데이터베이스를 위한 색인 구조로 가장 널리 사용되고 있다. 디스크 기반 B+-트리에서의 노드 갱신은 해당 노드가 저장된 디스크 페이지를 제자리 갱신함으로써 간단히 수행되며, 이런 제자리 갱신 비용은 크지 않다. 반면에 B+-트리를 플래시 메모리에 저장하여 사용할 때는 플래시 메모리의 과도한 제자리 갱신 비용 문제로 인해 기존 디스크 기반 B+-트리 알고리즘을 그대로 사용하기 어렵다. 이런 이유로 기존 플래시 메모리 기반 B+-트리 연구에서는 실시간으로 발생하는 갱신 연산 정보를 추가적인 임시 공간에 저장하는 방식을 사용하였다. 이런 방식은 B+-트리의 제자리 갱신 횟수를 쉽게 줄일 수 있다는 장점이 있지만 저장 공간의 추가 사용과 키 검색 시간을 지연시킬 수 있다는 문제가 있다. 특히 단말노드 계층의 링크 연결을 사용한 범위 검색을 효과적으로 수행할 수 없다는 문제를 가지고 있다. 이런 문제점을 해결하기 위해 본 논문에서는 단말노드들과 이들의 부모노드를 p-node 블록이라는 하나의 플래시 메모리 블록에 저장할 수 있는 알고리즘을 제안한다.

다국어 초록 (Multilingual Abstract)

During the past decades, the B+-tree has been most widely used as an index file structure for disk-resident databases. For the disk based B+-tree, a node update can be cheaply performed just by modifying its associated disk page in place. However, in case that the B+-tree is stored on flash memory, the traditional algorithms of the B+-tree come to be useless due to the prohibitive cost of in-place updates on flash memory. For this reason, the earlier schemes for flash memory B+-trees usually take an approach that saves B+-tree changes from real-time updates into extra temporary storage. Although that approach can easily prevent frequent in-place updates in the B+-tree, it can suffer from a waste of storage space and prolonged search times. Particularly, it is not allowable to process range searches on the leaf node level. To resolve such problems, we devise a new scheme in which the leaf nodes and their parent node are stored together in a single flash block, called the p-node block.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 연구 배경
• Ⅲ. 제안하는 플래시 메모리 B+-트리
• Ⅳ. 성능 평가
• Ⅴ. 결론
• 참고문헌

참고문헌 (Reference)

1 Chang Xu, "Update Migration: An Efficient B+ Tree for Flash Storage" 276 (276): 276-290, 2010

2 D. Yinan Li, "Tree Indexing on Solid State Drives" 2010

3 Patrick E. O'Neil, "The Log-Structured Merge-Tree (LSM-Tree)" 33 (33): 351-385, 1996

4 S. C. Lim, "Restructuring the concurrent B+-tree with non-blocked search operations" 147 (147): 2002

5 Devesh Agrawal, "Lazy-Adaptive Tree: an Optimized Index Structure for Flash Devices" 361-372, 2009

6 Stepahan Baumann, "Flashing Databases: Expectations and Limitations" 2010

7 Sai Tung On, "Flash-Optimized B+-Tree" 25 (25): 2010

8 Y. K. Wang, "Evaluating Non-In-Place Update Techniques for Flash-Based Transaction Processing Systems" 777 (777): 777-791, 2009

9 G. J. Na, "Dynamic In-Page Logging for B+-tree Index" 24 (24): 1231-1243, 2012

10 S. G. Moon, "Crash Recovery in FAST FTL" 6399 : 13-22, 2011

11 Marcel Kornacker, "Concurrency and Recovery in Generalized Search Trees" In Proc. of SIGMOD 1997

12 S. W. Park, "An Efficient Buffer Management Scheme for Implementing a B-Tree on NAND Flash Memory" 2007

13 C. H. Wu, "An Efficient B-tree Layer Implementation for Flash-memory Storage Systems" 6 (6): 2007

14 C. Mohan, "ARIES/IM: An Efficient and High Concurrency Index Management Method using Write-ahead Logging" 1992

15 Xiaoyan Xiang, "A Reliable B-Tree Implementation over Flash Memory" 2008