B-트리 (Balanced Tree의 약자)는 모든 잎 노드가 동일한 깊이를 가지는 자가 균형 이진 검색 트리입니다.
이는 삽입, 삭제 및 검색 시에 일정한 성능을 보장합니다. B-트리의 "B"는 이 트리가 항상 균형(balance)을 유지하도록 설계되었다는 것을 의미합니다.
B-트리의 주요 특성은 다음과 같습니다:
1. 모든 잎 노드는 동일한 깊이를 가집니다.
2. 각 내부 노드(루트 노드 포함)는 최대 M개, 최소 M/2개의 자식 노드를 가질 수 있습니다. 예외적으로 루트 노드는 자식이 2개 미만일 수도 있습니다.
3. 노드 내의 키는 오름차순으로 정렬됩니다.
4. 각 내부 노드의 키는 자식 노드들 사이의 키 값들을 구분합니다.
B-트리는 균형 트리이기 때문에, 데이터의 삽입과 삭제 시에 트리의 높이를 재조정해야 할 수 있습니다.
이를 통해 검색, 삽입, 삭제 등의 연산을 항상 효율적으로 수행할 수 있습니다.
예를 들어, 3차 B-트리에 키를 순서대로 삽입해보겠습니다.
여기서 3차 B-트리란 각 노드의 자식이 최대 3개인 트리를 의미합니다.
1. 처음 키 '1'을 삽입합니다. 트리는 아래와 같습니다:
1
2. 다음으로 키 '2'를 삽입합니다. 루트 노드에 키 '2'가 추가됩니다:
1 - 2
3. 키 '3'을 삽입합니다. 루트 노드가 꽉 찼기 때문에 루트가 분할되며, 키 '2'가 새로운 루트가 됩니다:
2
/ \
1 3
4. 키 '4'를 삽입합니다. 키 '4'가 가장 오른쪽 노드에 추가됩니다:
2
/ \
1 3 - 4
5. 마지막으로 키 '5'를 삽입합니다. 가장 오른쪽 노드가 꽉 찼기 때문에 이 노드가 분할되며, 키 '4'가 루트의 오른쪽 자식이 됩니다:
2 - 4
/ \ \
1 3 5
이처럼 B-트리는 각 노드의 키 간격을 최적화하여 검색 연산을 빠르게 수행할 수 있습니다.
또한, 삽입이나 삭제 시에 트리의 높이를 재조정하여 균형을 유지하므로, 모든 연산의 시간 복잡도는 O(log n)을 유지합니다.
이 때문에 B-트리는 대용량의 데이터를 저장하고 검색하는 데이터베이스 시스템에서 널리 사용됩니다.
