자료구조 B-트리

소개글

자료구조 B-트리 발표자료

목차

B-트리 정의
구조
특성
추가
삽입
탐색

본문내용

다방향 탐색 트리
Bayer와 McCreighton 에 의해 제작된 m-원 탐색 트리의 한 종류
트리의 균형을 유지하는 특성이 있음
B-트리 (B-tree)

B-트리의 특성
1.루트 노드는 단말노드이거나, 2에서 m개의 서브트리를 가짐.
2. 루트 노드를 제외한 모든 내부 노드는 아래 개수만큼 서브트리를 가짐.
┌ m/2┐3 ≤ (서브트리의 개수) ≤ m


3. 단말 노드는 아래 개수만큼 자료를 가짐.
┌ m/2┐-1 ≤ (자료의 개수) ≤ m-1
4. 모든 단말 노드는 같은 레벨에 있음.
즉, 트리는 완전한 균형 상태에 있도록 함


m=5 인 B-트리
서브트리 : 3 ≤ ≤5, 자료의 개수 : 2 ≤ ≤4

참고 자료

없음