TIL:B*-트리

B*-tree

• B-트리에서 삭제 시 합병, 재분배로 인한 오버헤드를 줄이고 삽입과 삭제 연산의 성능을 개선하기 위해 고한된 B-트리의 변형

특성

1. B*-트리는 공백/높이가 1이상의 m-원 탐색 트리
2. 루트는 리프가 아닌 최소 2개, 최대 2(2m-2)/3 + 1 개의 서브 트리를 갖음
3. 루트와 리프를 제외한 모든 노드는 적어도 2(2m-2)/3 + 1개의 서브트리를 갖음
4. ** 모든 리프는 같은 레벨에 있음 **

삽입

• 삽입의 시작은 리프노드에서 시작
• 삽입 시 오버플로우
  • 노드를 즉시 분할
  • 오버플로우된 키 값과 포인터를 인접한 형제 노드의 여유공간을 이용해 재분배
  • 형제 노드 = 만원, 인접한 형제 노드의 키 값을 3개의 노드로 분할
  • ** 분할된 노드가 2/3가 항상 채워지는 것이 보장 **

삭제

• b-트리의 삭제와 비슷
• 삭제 -> 최소 키 값의 수 부족 -> 형제 노드로부터 재분배
• 삭제 -> 형제 노드 여유 키 값 없음 -> 합병
  • B*-트리는 3개의 노드를 2개의 노드로 합병
  • 2개의 노드가 1개의 노드로 합병되 트리 높이가 낮아질 경우가 있음