플래시 메모리를 위한 효율적인 B+ 트리 저장 알고리즘
An Efficient B+ Tree Storing Algorithm for Flash Memory
- 주제(키워드) 플래시메모리 , 임베디드 DBMS
- 주제(KDC) 플래시 메모리 기반 B+트리 저장 기법
- 발행기관 아주대학교
- 지도교수 정태선
- 발행년도 2009
- 학위수여년월 2009. 8
- 학위명 석사
- 학과 및 전공 정보통신전문대학원 정보통신공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000010203
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
플래시 메모리는 임베디드 시스템에서 필요한 특성을 고루 가진 저장장치로써, 최근 가장 주목을 받고 있다. 따라서 기존의 장치에서 개발된 저장 기법들을 플래시 메모리 상에서 적용하려는 시도가 많이 이루어지고 있다. 특히 현재 B+트리는 하드디스크 기반의 DBMS (Database Management System)에서 가장 많이 쓰이는 인덱싱 기법 중의 하나이며, 플래시 메모리로 적용될 수 있다. 하지만, B+트리는 빈번한 입력과 삭제가 발생하는데, 덮어쓰기(overwrite)가 가능한 하드디스크와 달리 그렇지 않은 플래시 메모리에서는 성능저하가 발생하게 된다. 이러한 성능저하를 최소화 할 수 있는 FTL (Flash Translation Layer) 계층에서 관리가 필요하다. 본 논문에서는 FTL 계층 상위 단계에서 B+트리의 노드 삽입과 삭제에서 발생하는 플래시 메모리 쓰기 지우기 연산을 최소하고, 노드와 페이지의 관계를 1 : 2로 하는 생성원리를 이용한 저장시점을 기술하도록 한다. 따라서 쓰기 지우기 연산을 효율적으로 관리함으로써, 하드디스크와 동일한 성능을 나타내는 플래시 기반의 B+트리 저장 방법을 제안한다.
more목차
1. 서 론 1
2. 플래시 메모리와 B+ 트리의 특징 및 용어정리 2
2.1. 플래시 메모리의 특징 2
2.2. B+ 트리의 특징 및 용어정리 3
3. 문제 인식과 관련 연구 4
3.1. 문제 인식 4
3.2. 관련 연구 4
3.2.1 유보버퍼 4
3.2.2 쓰기 패턴 변화 5
3.2.3 로그 기반 관리 기법 6
3.2.4 고정 페이지 레이아웃 7
4. BLUF (B+ Tree Layer Using Formation) 8
4.1. PR-버퍼(Pre-Record Buffer) 8
4.2. 생성원리에 따른 저장 9
4.3. 중간 노드 테이블 10
4.4. 버킷 노드 10
5. BLUF 알고리즘 12
5.1. 삽입 연산 12
5.2. 읽기 연산 13
5.3. 지우기 연산 14
6. 성능 평가 방법 및 평가 결과 14
6.1. 성능 평가 방법 14
6.2. 성능 평가 결과 15
7. 결론 16
8. 참고문헌 17
그림 & 표 차례
그림 1 B+트리 구조 3
그림 2 노드(Node) 구성요소 3
그림 3 BFTL 5
그림 4 LBS 트리 예제 6
그림 5 μ-트리 예제 8
그림 6 3,8,15,6,5가 입력되는 상황 9
그림 7 3,8,15,6,5가 입력되는 경우 10
그림 8 2,10,12,1,20,11이 계속해서 입력되는 경우 11
그림 9 Bucket Node 사용 12
그림 10 알고리즘별 전체 수행 시간 15
그림 11 알고리즘별 쓰기 횟수 15
그림 12 PR-버퍼 크기에 따른 16
표 1 하드 디스크와 NAND 플래시 메모리 속도 비교[1] 2
표 2 삽입 연산 알고리즘 12
표 3 읽기 연산 알고리즘 13
표 4 실험 환경 14
