B-트리

B-트리란?

1. 균형 다진(이진x) 탐색 트리
2. 모든 노드가 키와 자식 포인터를 가짐 -> 내부 노드도 키와 자식 포인터 가짐
3. 루트에서 리프노드까지의 모든 경로의 길이 동일 -> 모든 리프 노드가 같은 레벨에 위치
4. 차수가 m일때
   -> 각 노드가 가질 수 있는 자식 수: ⌈m/2⌉ ~ m
   -> 각 노즈다 가질 수 있는 키 수: ⌈m/2⌉-1 ~ m-1

B-트리 삽입 과정

B-트리 노드 삽입 방법

1. 삽입 위치 탐색
   -> 삽입할 키가 들어갈 리프 노드를 탐색
2. 삽입
   -> 해당 리프 노드에 키를 삽입
   -> 키들을 정렬 상태로 유지
3. 노드 초과 확인
   -> 삽입 후 키의 개수가 m 개수 초과
4. 분할
   -> 중간값을 부모 노드로 올리고
   -> 왼쪽 키들과 오른쪽 키들이 각각 새로운 노드가 됨
5. 부모에서 Overflow 발생시
   -> 부모도 최대 m-1 키를 넘어가면 같은 방식으로 분할
   -> 최상위 루트까지 올라가 분할되면 새로운 루트가 생김

B-트리 삭제 과정

• 1️⃣ 삭제하려는 키가 리프 노드에 있는 경우
  • 해당 키를 삭제
  • 단, 삭제 후 키의 개수가 최소 허용치보다 적어지면 보정 작업
    • 왼쪽 또는 오른쪽 형제 노드에서 키를 빌려옴
    • 양쪽 형제도 최소치라면 병합
• 2️⃣ 삭제하려는 키가 내부 노드에 있는 경우
  • 해당 키를 왼쪽 서브트리의 최대 키 또는 오른쪽 서브트리의 최소 키와 교체
  • 교체된 키를 실제로 리프에서 삭제
  • 1️⃣과 동일
• 3️⃣ 보정 과정 (삭제 후 최소 조건 위반 시)
  • 삭제 후 노드의 키 개수가 ⌈m/2⌉ - 1 미만이 되면 보정
  • 재분배
    • 형제 노드가 키를 최소 개수보다 많이 가지고 있다면 → 부모 키를 형제 키와 교환
  • 병합
    • 형제 노드도 최소 키 개수라면 병합
    • 부모의 키 하나를 형제와 합쳐 새로운 노드로 병합
    • 부모 노드의 키 개수가 줄어들게 되고, 부모도 최소 조건 위반 가능 → 재귀적으로 보정

B-트리 연산 시간복잡도

1. 탐색: O(log n)
2. 삽입: O(log n)
3. 삭제: O(log n)