[CS기초] B-tree

B-tree 자료구조

B-tree는 균형 잡힌 다진 트리(Balanced Multi-way Search Tree)로, 디스크 접근 최소화를 위해 설계되었으며, 데이터베이스와 파일 시스템에 최적화된 자료구조입니다.

• 다진 트리(m-ary tree): 각 노드가 최대 m개의 자식 노드를 가질 수 있는 트리
  • 이진 트리(2-ary tree)는 자식이 최대 2개인 특별한 경우이다.
• 균형 트리(balanced tree): 모든 리프 노드(자식이 없는 노드)가 루트로부터 거의 같은 거리에 위치한 트리
  • 깊이 차이가 너무 크지 않게 유지되어, 탐색/삽입/삭제의 성능을 일정하게 보장한다.

한 노드에 여러 개의 키와 자식을 가질 수 있어 트리의 높이를 낮게 유지하고, 디스크 접근 횟수를 최소화합니다.

 

B-tree의 특징

• 모든 리프 노드는 같은 깊이를 가지며, 항상 균형 잡힌 상태를 유지한다.
• 각 노드는 최대 m-1개의 키와 최대 m개의 자식을 가진다. (m: 트리의 차수)
• 키는 오름차순 정렬되어 있으며, 자식은 키의 범위에 따라 분기된다.
• 노드의 데이터 갯수가 초과됐을 때에는 노드를 분할(split)한다.

 

B-tree의 장점과 단점

장점

• 디스크 접근을 최소화할 수 있다.
  • 큰 데이터셋을 처리하는 DB나 파일 시스템에 적합하다.
• 노드에 여러 키가 있어 트리 높이가 낮다.
• 삽입/삭제 후에도 항상 균형을 유지한다.

단점

• 구현이 복잡하다. (삽입/삭제 시 노드 분할, 병합 처리가 필요)
• 메모리 환경에서는 AVL 트리나 레드-블랙 트리처럼 자가 균형 이진 탐색 트리가 더 빠를 수 있다.

 

B-tree의 시간 복잡도

탐색/삽입/삭제 연산을 모두 O(logN)에 수행할 수 있다.

 

 

B-tree의 삽입 (Insertion)

B-tree의 새로운 키는 항상 리프 노드에 삽입됩니다. 하지만 삽입 위치를 찾아가는 도중이나 삽입 후에 노드가 가득 찬 경우, 이를 처리(split)해줘야 합니다.

삽입 과정 요약

1. 루트에서 시작하여 삽입할 리프 노드를 탐색
2. 내려가는 도중, 자식 노드가 가득 찼다면 미리 분할(split)
3. 리프 노드에 도달하면 정렬된 상태로 키를 삽입

노드 분할(Split)

• 노드에 키가 최대 개수(m - 1개)에 도달했을 경우 분할
• 중간 키를 부모로 올리고, 나머지는 좌우로 나눠 새로운 두 노드로 생성

 

B-tree의 삭제 (Deletion)

B-tree에서의 삭제는 삭제하는 키가 리프 노드에 있는 경우와 내부 노드에 있는 경우로 나뉘며, 삭제 과정 중 키 수가 부족한 노드를 보완해야 할 수 있습니다.

삭제 과정 요약

1. 리프 노드에 있는 키 → 바로 삭제
2. 내부 노드에 있는 키 → 선행자 또는 후계자로 교체한 후, 하위에서 삭제
3. 삭제 도중 자식 노드의 키가 부족하면:
   • 형제에게서 키를 빌리기(borrow)
   • 형제와 병합(merge)