'B트리'에 해당되는 글 1건

데이터베이스-B트리(B-Tree)

1. IT Story/Basic Studies 2019. 5. 5. 11:05

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-1. B트리(B-Tree)의 구조도

2-2. B트리(B-Tree)의 장/단점

1) B트리(B-Tree)의 장점

- 삽입, 삭제 후에도 균형 트리 유지
- 효율적인 알고리즘 제공
- 저장 장치의 효율성
- 균등한 탐색 속도 보장 가능

2) B트리(B-Tree)의 단점

- 노드의 삽입과 삭제 시 트리균형 유지 위하여 복잡한 연산(재분배, 합병) 필요
- 순차탐색시 inorder(중위)순회로 비효율적

구분	B-Tree	B+Tree	B*-Tree
특징	- 노드에 1/2 이상 채워져야 분열	- 레코드 위치는 leaf 노드에만 등록됨	- 노드에 2/3 이상 채워져야 분열
장점	- 안정성, 신뢰성, Recovery 우수	- 순차 접근이 용이함 - 데이터 저장, 검색속도 빠름	- B-tree 에 비해 분열이 적으며 연산용이
단점	- 순차접근이 어려움 - 데이터 저장 효율 미흡	- Index Set 과 Sequence Set 에 중복성 존재	- 대용량 데이터 처리 어려움