1. B트리(B-Tree)의 개요
1-1. B트리(B-Tree)의 정의
- 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조
- B는 Balanced의 의미이며, Leaf node가 한쪽 방향으로 쏠리는 현상이 적음
1-2. B트리(B-Tree)의 특징
- Root와 leaf를 제외한 모든 노드는 최소 M/2, 최대 M개의 서브트리를 가짐
- Leaf노드는 (m/2)-1개, 최대 m-1의 키 값을 가짐
2. B트리(B-Tree)의 구조도 장/단점
2-1. B트리(B-Tree)의 구조도
2-2. B트리(B-Tree)의 장/단점
1) B트리(B-Tree)의 장점
- 삽입, 삭제 후에도 균형 트리 유지
- 효율적인 알고리즘 제공
- 저장 장치의 효율성
- 균등한 탐색 속도 보장 가능
2) B트리(B-Tree)의 단점
- 노드의 삽입과 삭제 시 트리균형 유지 위하여 복잡한 연산(재분배, 합병) 필요
- 순차탐색시 inorder(중위)순회로 비효율적
3. B트리(B-Tree)간 비교
| 구분 | B-Tree | B+Tree | B*-Tree |
| 특징 | - 노드에 1/2 이상 채워져야 분열 | - 레코드 위치는 leaf 노드에만 등록됨 | - 노드에 2/3 이상 채워져야 분열 |
| 장점 | - 안정성, 신뢰성, Recovery 우수 | - 순차 접근이 용이함 - 데이터 저장, 검색속도 빠름 |
- B-tree 에 비해 분열이 적으며 연산용이 |
| 단점 | - 순차접근이 어려움 - 데이터 저장 효율 미흡 |
- Index Set 과 Sequence Set 에 중복성 존재 |
- 대용량 데이터 처리 어려움 |
'1. IT Story > Basic Studies' 카테고리의 다른 글
| 리드의 법칙(Reed’s Law) (0) | 2019.05.09 |
|---|---|
| 길더의 법칙(Guilder’s Law) (0) | 2019.05.08 |
| 파레토 법칙(Pareto Principle) (0) | 2019.05.07 |
| 요르돈 법칙(Yourdon’s Law) (0) | 2019.05.06 |
| 데이터베이스-해싱(Hashing) (0) | 2019.05.04 |
| 데이터베이스-회복기법(Recovery) (0) | 2019.05.03 |
| 데이터베이스-트랜잭션(Transaction) (0) | 2019.05.02 |
| 데이터베이스-데이터무결성(integrity) (0) | 2019.05.01 |
운명을바꾸는자
IT와 함께 살아가는 삶
