TIL:B-tree

B-tree

• Bayer와 McCreight에 의해 제안
• m-원 균형 탐색 트리로서 효율적 균형 알고리즘을 제공

특성

1. b-트리는 공백/높이가 1이상인 m-원 탐색 트리
2. 루트와 리프를 제외한 내부 노드는 최소 m/2, 최대 m 개의 서브트리를 가짐 (키 값은 최소 m - 1의 값을 가짐)
3. 루트는 그 자체가 리프가 아닌 이상 적어도 2개 이상의 서브 트리를 갖음
4. 모든 리프는 같은 레벨에 있음

※ B-트리는 항상 균형 상태를 유지하며 키 값 삽입/삭제 뒤에도 B-트리 정의/성질 유지

B-tree 검색

• 특정 키 값을 검색하기 위해 m-원 탐색 트리의 직접 검색 과정을 거침
• 노드 n에 대해 순차 검색
• 순차 검색 시 키 값에 따라 트리의 각 노드를 중위 순회

B-tree 삽입

• 키 k가 들어갈 노드가 빈 공간이라면 해당 위치에 삽입
• 노드에 빈 공간이 없으면 노드를 2개의 노드로 분할
  • 중간 키 값은 분할 노드의 부모 노드, 중간 키 값보다 작은 것은 왼쪽 노드, 중간 키 값보다 크면 오른쪽 노드에 배치

**※ 노드의 키 값은 항상 오름차순 순서를 유지 **

B-tree 삭제

• 삭제 키 값 = 내부노드, 후행 키 값과 교환 뒤 리프 노드에서 삭제

삭제 기법

1. 재분배
   오른쪽/왼쪽 형제 노드에 최소 키 값 수보다 많은 키 값들이 있는 노드 선택
   해당 노드로부터 한 개의 키 값을 차출해 이동

2. 합병
   재분배 방식이 불가능할 때 사용.
   형제 노드의 키 값들과 이 두 노드의 부모 노드의 키 값을 모두 모으는 작업