B-Tree 보고서 및 소스코드 입니다.

소개글

파일구조 B-Tree 소스코드 및 보고서 입니다(실행결과 도 있음)

41page로 구성되어 있습니다

목차

없음

본문내용

1. 서론

1.1. B-Tree의 이론적 배경
■ B(Balanced)-Tree는 인덱스를 조직하는 트리 구조로 가장 많이 사용하는 것으로 알려져 있으며 Bayer와 McCreight에 의해 제안되었다. B-트리는 m-원 균형 탐색 트리로써 효율적인 균형 알고리즘을 제공한다.

[그림 ] 3차 B-트리의 구조


■ B- 트리에서의 삽입은 새로운 키 값은 항상 리프 노드에 삽입된다. 노드에 공간이 있는 경우 순서에 맞게 단순 삽입되며 노드에 공간이 없는 경우에는 Overflow로 spilt가 발생된다. 이 때 중간 키 값은 분할된 두 노드의 왼쪽 서브트리, 오른쪽 서브트리가 되도록 부모 노드에 삽입한다.
■ B- 트리에서의 삭제는 삭제할 키 값이 리프 노드에 있는 경우에는 그대로 삭제 되며 삭제될 키 값이 내부 노드에 있는 경우 이 키 값과 후행 키 값과 교환 후 리프 노드에서 삭제한다. 삭제 결과로 노드의 키 값 수가 B-트리의 최소 키 값 수보다 작게 되면 underflow가 일어나 재분배나 합병을 수행한다.
■ B- 트리에서의 검색은 M-원 탐색 트리의 직접 검색과 같은 과정이며 B-트리 전체의 순차 검색은 트리의 중위 순회(inorder travsersal)로 수행한다.

1.2. B+-Tree의 이론적 배경
■ B(Balcanced)-Tree는 Knuth가 제안한 B-트리의 또 다른 변형으로 인덱스 세트와 순차 세트로 구성된 것이 특징이다. 이 트리는 B-트리의 순차 탐색을 보완하여 성능을 향상한다.

참고 자료

없음