[Tree] B-트리, B-Tree

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- B-트리 (B-Tree)

• 다수의 키(수백 ~ 수천 개)를 가지는 노드로 구성되어 다방향 탐색이 가능한 균형 트리
• 노드에 대량의 데이터를 저장하기 때문에 트리의 깊이가 작다는 장점이 있어 대량의 데이터 탐색에 유리
• 주로 데이터베이스의 기본 자료구조로 활용
• 차수가 m인 B-트리는 다방향 탐색 트리로서
  • 모든 이파리 노드들은 동일한 깊이를 가짐
  • 각 내부 노드의 자식 수는 [m / 2] 이상 m 이하
  • 루트의 자식 수는 2 이상

 

- 연산

• Search : 탐색하고자 하는 키와 노드의 키들을 비교하여 적절한 서브트리를 탐색 후, 각 노드에는 일반적으로 수백 개가 넘는 키가 있으므로 이진 탐색을 수행
• Insertion
  • 탐색과 동일한 과정을 거쳐 새로운 키가 저장되어야 할 단말 노드를 찾음
  • 단말 노드에 새 키를 수용할 공간이 있다면 노드의 키들이 정렬 상태를 유지하도록 새 키를 삽입
  • Overflow 발생 시 루트 노드로 올라가며 Split 연산을 반복적으로 진행
• Deletion
  • B-트리에서 삭제는 항상 단말 노드에서 이뤄짐
  • 만약 삭제할 키가 속한 노드가 단말 노드가 아닌 경우 이진 탐색 트리의 삭제와 유사하게 중위 선행자나 중위 후속자를 삭제할 키와 교환한 후에 단말 노드에서 삭제를 수행
  • Underflow 발생 시 Transfer와 Fusion 연산을 진행