B-Tree
태그 :
- 개념
- 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조로. 트리의 루트로부터 하나의 노드에 이르는 모든 경로가 일정한 깊이를 유지하며 데이터의 접근시간이 동일함
1. Balanced Tree를 통한 균등한 응답속도 보장을 위한 탐색 트리, B-Tree 개요
가. B-Tree의 정의
- 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조
* B 는 Balanced의 의미이며, leaf node가 한쪽 방향으로 쏠리는(skewed) 현상이 적음
나. B-Tree의 특징
- 각 노드는 1/2 이상 채워져야하며, 모든 leaf node는 같은 level에 있음
- 탐색, 추가, 삭제는 root node로부터 시작함
- 노드 내 값은 오름차순 유지
- 공백이거나 높이가 1이상인 m-원 탐색 트리(m-way search tree)
- 루트와 리프(leaf)를 제외한 내부 노드는 최소 [m/2], 최대 m개의 서브트리를 가지며, 적어도 [m/2]-1개의 키 값을 가짐 -> 적어도 반 이상이 키 값으로 채워져 있어야 한다
- 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가짐
- 모든 리프는 같은 레벨에 있음 (균형 트리)
2. B-Tree의 구조와 장점 및 단점
가. B-Tree의 구조
- In Order Tree Traversal 순서: 5, 10, 20, 25, 30, 40, 50, 100
나. B-Tree의 장점과 단점
장점 |
1) 삽입, 삭제 후에도 균형 트리 유지 2) 효율적인 알고리즘 제공 3) 저장 장치의 효율성 4) 균등한 탐색 속도 보장 가능 |
단점 |
1)노드의 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산(재분배, 합병)이 필요 2) 순차탐색 시에 inorder(중위) 순회로 비효율적 à B+ Tree 구조에서 leaf node간의 linked list로 순차 탐색 효율 향상됨 |
3. B-Tree와 B+tree의 비교 및 활용
가. B-Tree와 B+tree의 비교
구분 |
B-tree |
B+tree |
접근성 |
- 순차 접근이 어려움 - 탐색 중 원하는 키 값의 레코드 위치를 파악해야 함 |
- 순차 접근이 용이함 - 레코드의 위치는 leaf node에서만 파악됨 |
중복성 |
- 탐색 키의 중복성을 제거함 |
- Index Set와 Sequence Set에 중복성 존재 |
복잡성 |
- non-leaf node 크기가 더 크며 tree에 대한 저장공간 관리가 복잡함 |
- 모든 node 크기가 같으며 삭제될 node가 항상 lead node에 존재함 |
나. B-tree의 활용
- DBMS의 인덱스 자료구조로 활용 됨(B+tree 및 B*tree로 발전 적용)
- 검색엔진, 패턴 매칭 등 빠르면서도 성능이 일정하게 유지되는 탐색이 요구되는 분야에 활용됨
4. B-Tree 연산
가. 삽입
- 리프노드에 빈 공간이 있는 경우 : 단순히 빈 공간에 삽입하면 됨
- 오버플로 발생 시
1) 두 노드로 분열(split)
2) ⎡m/2 ⎤ 째의 키 값 -> 부모노드
3) 나머지는 반씩 나눔 (왼쪽, 오른쪽 서브트리)
- 새로운 값 "59"가 추가된 경로를 간략히 설명
나. 삭제
- 리프노드에서 삭제
- 삭제키가 리프가 아닌 노드에 존재
. 후행키 값과 자리교환(후행키-항상 리프에)
. 리프노드에서 삭제
- 언더플로 : 키수 < ⎡m/2⎤ -1
. 재분배 (redistribution) : 최소키 수 이상을 포함한 형제노드에서 이동
(형제노드의 키 → 부모노드 → 언더플로 노드)
. 합병 (merge) : 재분배 불가능시 이용 (형제노드 + 부모노드의 키 + 언더플로 노드)