'B+ TREE'에 해당되는 글 1건

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 에 중복성 존재
- 대용량 데이터 처리 어려움

 

블로그 이미지

운명을바꾸는자

IT와 함께 살아가는 삶

,