[알고리즘]External Search

소개

External Search 중 B-tree에 대해 다룬 자료입니다. 핵심적인 내용만 추렸기 때문에 분량은 많지 않지만 그림이 상당수 포함되어 이해하기에는 무리 없을 수준입니다. B-tree와 B+-tree, B*-tree 이 세 가지에 대해 중점적으로 다루고 있습니다.

목차

1. Sequential Search
2. Indexed Sequential Search
3. M-Way Search 트리
4. B-트리
5. B*-트리
6. B+-트리
7. Conclusion
8. Reference

본문내용

1. Sequential Search
1.1 정의 및 특성
- 특정 레코드를 찾기 위해 파일상의 각 레코드에 대한 키를 처음부터 순차적으로 비교해 가면서 조사하는 방법
- 주로 일괄처리 작업에 사용되며 어떠한 저장매체(주로 자기테이프)에서도 탐색이 가능

2. Indexed Sequential Search
2.1 정의 및 특성
- 레코드들이 저장되는 단위별로 인덱스를 생성하고 이를 이용해 자료의 대략적인 위치를 먼저 검색하는 방법

3. m-way Search 트리
3.1 정의 및 특성
- 모든 노드가 m보다 작거나 같은 진출 차수를 갖는 트리
- 트리의 각 노드의 구조.
① 노드의 key 값은 오름차순
② i=0, i=1,…, n-1인 i에 대해 Pi가 가리키는 서브트리는 모두 m-way Search 트리고 서브트리의 모든 노드들의 키 값은 ki보다 작음
③ Pn이 가리키는 서브트리의 모든 노드들의 키 값은 kn-1 의 키 값보다 큼

3.2 성능
- 노드당 최대 키의 개수 : m-1개
- m-원 트리의 최소 높이 : [logm (n+1)]
- 최적 m-원 트리 최대탐색 길이 : O(logmn)

4. B-트리
4.1 정의 및 특성
① 루트노드는 최소한 2개의 서브트리 보유
② 내부노드는 최소한 ┏m/2┓의 서브트리(child) 보유
③ 모든 단말노드는 동일 레벨에 존재
④ 각 노드의 키들은 정렬된 상태

4.2 자료 삽입
① 현재 노드가 외부노드가 아닌 동안
- 현재 노드가 꽉 차 있으면 분할.
- 삽입 키와 노드의 키들을 비교하여 다음 노드로 이동.
② 현재의 외부노드가 꽉 차 있으면 분할한다.
③ 현재의 외부노드에 삽입키를 넣는다. (정렬된 순서 유지)

참고자료

· 없음