[자료구조]B 트리, B+ 트리, B* 트리

1. 각 트리에 대한 요약 내용

• B 트리 (B-Tree):
  • B 트리는 균형 트리의 일종으로, 데이터를 정렬된 상태로 저장합니다. 각 노드에는 여러 키와 해당 키에 대응하는 값을 가질 수 있습니다.
  • 각 노드는 키에 대한 오름차순으로 정렬된 배열을 가지며, 노드의 크기가 일정한 범위 내에 유지됩니다.
  • B 트리는 데이터베이스 인덱스와 파일 시스템에서 널리 사용됩니다. 검색, 삽입 및 삭제 작업에 대해 대부분의 경우 O(log n)의 시간 복잡도를 제공합니다.
• B+ 트리 (B+ Tree)
  • B+ 트리는 B 트리의 변형으로, 리프 노드만이 데이터를 저장하고 내부 노드는 키만을 저장합니다. 리프 노드는 연결 리스트로 연결되어 있습니다.
  • 리프 노드는 외부 블록이므로 색인과는 달리 키를 찾는 데 사용됩니다. 이는 키에 대한 검색이 더 효율적으로 이루어질 수 있도록 합니다.
  • B+ 트리는 범위 검색에 특히 유용하며, 데이터베이스 시스템에서 주로 사용됩니다. B 트리와 비슷한 시간 복잡도를 가집니다.
• B* 트리
  • B* 트리는 B 트리의 변형으로, 삽입 시에 트리의 균형을 유지하기 위해 조정이 더 자주 발생합니다.
  • B* 트리는 B 트리보다 더 균형적인 구조를 가지며, 삽입과 삭제 작업이 더 빈번한 경우에 성능을 향상시킬 수 있습니다.
  • B* 트리는 데이터베이스 시스템에서의 활용이 주로 보고되며, B 트리보다 조금 더 높은 삽입 및 삭제 성능을 제공합니다.

2. B 트리

• 규칙
  • 루트를 제외한 모든 노드는 [m/2] 만큼의 자식 포인터를 가져야한다. 차수가 10이면 한 개의 노드가 자식 포인터를 최소 5개를 가져야한다.
  • 루트 노드는 최소 2개의 자식 포인터를 가져야한다.
  • 모든 리프 노드는 똑같은 레벨이어야 한다.
  • Bottom-up 방식으로 Creation process가 이루어 진다.

3. B+ 트리

• 규칙
  • 오직 리프 노드에서만 레코드 포인터를 가진다. 그래서 리프 노드에 모든 키들이 존재한다.
  • 모든 리프 노드는 왼쪽에서 오른쪽으로 연결되어 있다.

4. B* 트리

• 규칙
  • 루트 노드가 아닌 노드는 노드의 2/3 이상이 채워져야 하는 특징이 있다.
  • 삽입 시 노드가 꽉 차더라도 바로 분리하지 않고, 키 값과 포인터를 재분배하여 형제 노드로 이동시키는 구조를 갔고 있다.
  • 삭제 시엔 삭제될 자리로 옮길 잎 노드가 정해진 개수의 키 값을 갖지 않을 때 형제 노드로부터 키 값을 재분배한다. 재분배 할 수 없는 경우 노드를 합친다.

 

5. 참고

• B트리의 종류와 특징 : https://velog.io/@seanlion/btree

B트리,B+트리, B*트리 개념 정리