화일 처리 및 응용 공부 #15 (B*트리)

2021.05.26 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #14 (B-트리)

이전 내용에 이어지는 내용이 몇 있으니 참고하자

---

 

기존 B-트리의 문제점

• B트리 구조 유지를 위해 추가적인 유지 연산이 필요함
  • 삽입시 노드의 분할, 재분배, 삭제시 노드의 합병, 재분배
• B*- 트리는 B-트리의 성능 개선을 위해 개반된 B트리의 변형

 

B*-트리

1. 공백이거나 높이가 1이상인 m원 탐색트리
2. 루트는 리프가 아닌 이상 최소 2개, 최대 2[(2m-2)/3] +1(소수점 내림) 개의 서브트리를 가짐
3. 루트와 리프를 제외함 노드는 적어도 (2m-2)/3+1 (소수점 내림)개의 서브트리, (2m-2)/3 개의 키값을 가짐
4. 모든 리프는 같은 레벨에 있다.

 

 

B 트리와의 차이점

• 삽입으로 인한 노드 분할의 빈도를 축소
  - 노드 오버플로시 즉시 분할 하는 대신 아래 과정을 진행

1. 오버플로된 키 값과 포인터를 인접한 형제 노드의 여유공간을 이용해 재분배
2. 인접 형제 노드가 만원이면 두인접 형제 노드 키값을 3개 노드로 분할
   - 한노드가 만원이 되더라도 다른 인접 형제 노드가 만원이 될때 까지 분할은 지연
   - 각 내부 노드는 항상 키 값수가 (2m-2)/ 3 이상 키 값을 채운다
   
   

 

같은 노드에서 가질수 있는 최소 키값이 B트리보다 많다.

결과적으로, 같은 키 값 수에 대해 B트리 보다 적은 수의 노드가 필요하게 됨

 

 

B*트리 생성

7차 b*트리 생성

 

 B*트리 삽입

5차 b*트리 키 24 삽입 과정

노드 분할 이용한 5차 b*트리 삽입 과정

노드 분할에 경우 q 노드 r노드 s 노드 전부를 합쳐서 오름차순으로 나눈후 2/3 부근에 있는 값을 루트로 놓고 다시 분할

 

 

B*트리에서 삭제

• B트리에서 삭제와 비슷함, 키 값 삭제로 최소 키 값 수가 유지되지 않으면,
  
  • 형제 노드로 부터 재분배 받도록 시도,
  • 형제 노드에 여유 키 값이 없으면 3개 노드를 2개 노드롤 합병
     - 합병으로 인해 트리 높이가 한레벨 낮아 질 수 있음

 

---

이전 내용과 함께 다시 봐보자