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

2021.05.11 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #13 (탐색트리2)

---

B- 트리

• 균형 m원 탐색 트리
  • 가장 많이 사용되는 인덱스 방법
  • 효율적인 균형 알고리즘을 제공함
• 차수(order)가 m 인 B-tree 특성
  • B트리는 공백이거나 높이가 1 이상인 m원 탐색 트리
  • 루트와 리프를 제외한 내부 노드
    • 최소 m/2, 최대 m개의 서브트리
    • 적어도 m/2 - 1 개 의 키값 (노드의 반이상이 채워짐)
  • 루트 : 리프가 아니면 적어도 두개의 서브트리를 가짐
  • 모든 리프는 같은 레벨

장점

• 삽입, 삭제 뒤에도 트리의 균형 상태를 유지
• 저장 장치의 효율성
  • 각 노드의 반이상은 항상 키값으로 채워짐

m차 B-트리 노드 구조

3차 B-트리 구조

 

m차 b-트리 노드 구조

B-트리에서의 연산

• m원 탐색트리의 검색과 같은 과정
  • 직접 탐색 : 키 값에 따라 왼쪽, 오른쪽으로 분기
  • 노드에서의 검색튼 순차 겁색
  • B-트리 전체의 순차 검색은 트리의 중위 순회로 수행

2021.05.19 - [전체글] - 자료구조 공부 #18 (트리연산)

트리연산 관련 다른 수업 내용이다 참고하자

 

B-트리에서 삽입

 

• 삽입
  • 공간이 있는경우 : 순서에 맞게 삽입
  • 공간이 없는 경우 : overflow로 split 발생
    • overflow 처리방법
      • 노드를 두개로 분할
        • 해당 노드에 새로운 키 값 삽입했다 가정
        • 중간(m/2)번째 키 값을 기준으로 왼쪽 키값을 그대로 두고 오른쪽 큰 기 값들은 새로운 노드에 저장
        • 중간 키값은 분할된 두 노드가 왼쪽, 오른쪽 서브트리가 되도록 부모 노드에 삽입
        • 이때 다시 overflow 발생시 split 작업 반복

 

삽입 결과

트리 순회 방법

트리 순회

2021.05.16 - [이론공부/자료구조] - 자료구조 공부 #17 (트리순회)

 

자료구조에 배운 트리순회 내용이다 참고하자

 

 

 

B-트리에서 삭제

1. 삭제할 키 값이 리프 노드에 있는 경우에는 그대로 삭제
2. 삭제될 키 값이 내부 노드에 있는 경우
     - 이 키 값의 후행 키 값과 교환 후 리프 노드에서 삭제
        B-트리 특성상 이 후행 키 값은 항상 리프 노드에 있음
        리프 노드에서의 삭제 연산이 더 간단
     - 후행 키 값 대신 선행 키 값을 사용할 수 있음
3. 삭제 결과로 노드의 키값 수가 B 트리의 최소 키 값 수(m/2 -1) 보다 작게 되면 underflow가 일어나 재분배 시행

 

재분배

• 해당 노드의 오른쪽이나 왼쪽 형제 노드 중에서 최소 키 값보다 많은 수의 키값을 가진 노드에서 키 값 하나를 차출
• 부모 노드에 있는 키 값을 언더 플로가 일어난 노드로 이동, 빈자리로 차출된 키값을 이동
  • 트리구조가 변경안됨

 

합병

• 재분배가 불가능한 경우 (두형제 노드가 최소의 키값만 가진 경우)에 적용
• 언더플로가 된 노드의 오른쪽(왼쪽) 형제 노드에 있는 키 값들과 이 두 노드를 분리시키는 부모 노드의 키값을 합치고 트리구조를 조정, 합병으로 생긴 빈 노드는 제거
  • 트리구조 변경됨
• 이 합병 작업은 루트노드까지 연쇄적으로 파급될 수 있다. 이 경우에는 트리의 레벨이 하나 감소될 수도 있다.

 

---

 

b 트리의 특성, 구조 균형이 유지되는 이유, 및 삽입삭제 과정을 이해하자