B tree

• BST와 같은 형태에서 자식 노드가 3개 이상인 트리

• 부모 노드에는 2개 이상의 키를 저장(이 키들은 오름차순 정렬되어 있음)

• 자식 노드는 부모 노드의 키를 기준으로 자식 노드를 나눔

• 자식 노드의 개수가 M인 B tree를 M차 B tree라고 함

B tree 파라미터

• M : 각 노드의 최대 자식 수
• M - 1 : 각 노드의 최대 키 수
• Math.ceil(M / 2) : 각 노드의 최소 자식 수(단, root, leaf 노드 제외)
• Math.ceil(M / 2) - 1 : 각 노드의 최소 키 수(단, root 노드 제외)

B tree 특징

• 모든 leaf 노드는 같은 레벨을 가진다 => balanced tree
• 검색에서 avf, worst case에서 모두 O(log2 N)의 시간 복잡도를 가진다 => 항상 일정한 성능을 보장

B tree 삽입

• 항상 leaf 노드에 삽입(삽입 후 정렬)
• 삽입 후 최대 키 수보다 많으면(M - 1)
  • 가운데 키를 기준으로 좌우 노드로 키를 분리
  • 가운데 키를 부모 노드로 이동

B tree 삭제

• internal 노드를 삭제하려면 해당 노드를 특정 leaf 노드와 위치를 바꿈, 특정 leaf 노드는 아래 2가지 중 하나
  • 선임자(predecessor) : 나보다 작은 데이터들 중 가장 큰 데이터
  • 후임자(successor) : 나보다 큰 데이터들 중 가장 작은 데이터
• 항상 leaf 노드에서 삭제(삭제 후 정렬)
• 삭제 후 최소 키 수보다 적으면(Math.ceil(M / 2) - 1) 재조정

B tree가 DB의 index로 사용되는 이유

• avg, worst case에서 조회, 삽입, 삭제 모두 O(log2 N)의 시간 복잡도를 가짐
• 하지만, balanced BST 또한 마찬가지로 조회, 삽입, 삭제의 avg, worst case에서 모두 O(log2 N)의 시간 복잡도를 가짐

B tree가 DB의 index로 사용되는 이유

DB가 실제 저장되는 HDD의 2가지 특징으로 인하여 B tree가 사용됨

1. HDD는 속도가 느리다 => 최대한 적게 접근하는 것이 성능에 좋다
2. HDD는 데이터를 block 단위로 관리하므로 RAM으로 데이터를 가져올 때도 정해진 block 단위로 가져옴 => 이 block에 필요한 데이터도 필요 없는 데이터도 있다, 최대한 많은 필요한 데이터가 block에 들어가야 성능에 좋다

• B tree는 BST에 비하여 레벨이 적다 => 더 적은 접근 횟수로 데이터를 찾을 확률이 높다.
• B tee는 BST에 비하여 한 노드에 더 많은 데이터가 있다 => 한 block에 더 많은 데이터를 가져올 확률이 높다.

위 그림의 상황은 각 노드들이 다른 block에 저장되어 있는 상황

101차 B tree의 예시