B 트리는 바이너리 서치 트리와 달리 다수의 자식 노드를 가지는 다진 트리입니다. 이로 인해 B 트리는 대량의 데이터를 효율적으로 관리할 수 있습니다.
B-Tree의 특징
•
노드들은 정렬된 순서로 저장됩니다.
•
노드마다 허용된 최대 자식 수가 있습니다.
•
루트 노드부터 리프 노드까지 모든 경로의 길이가 동일하게 유지됩니다.
•
데이터가 노드에 삽입되거나 삭제될 때, 트리의 균형을 유지하기 위한 재조정이 일어납니다.
B 트리는 대량의 데이터를 효율적으로 저장하고 검색하기 위해 사용됩니다. 트리의 균형을 유지하는 능력으로 인해 검색, 삽입, 삭제 연산의 평균 시간 복잡도가 O(log n)입니다.
B-Tree의 예시
예시 B 트리:
8, 15
/ \
3, 5, 6 18, 20
/ | \ / | \
1, 2 4 7, 10, 12 16, 17 19, 21, 23
Plain Text
복사
1.
루트 노드: 8, 15
•
이 노드는 두 개의 키를 가지고 있으며, 두 개의 자식 노드를 가집니다.
•
왼쪽 자식은 3, 5, 6 (이 키들보다 작은 값들을 저장), 오른쪽 자식은 18, 20 (이 키들보다 큰 값들을 저장)입니다.
2.
첫 번째 자식 노드: 3, 5, 6
•
이 노드는 1, 2, 4, 7, 10, 12라는 세 개의 자식 노드를 가집니다.
•
이 키들은 다음과 같은 규칙을 따릅니다:
◦
1, 2는 이 노드의 모든 키보다 작음.
◦
4는 3, 5, 6 사이에 위치.
◦
7, 10, 12는 이 노드의 모든 키보다 큽니다.
3.
두 번째 자식 노드: 18, 20
•
이 노드는 16, 17과 19, 21, 23라는 두 개의 자식 노드를 가집니다.
•
이 노드에서의 규칙은:
◦
16, 17은 18, 20보다 작음.
◦
19, 21, 23은 18, 20보다 큽니다.
B-트리의 작동 방식
1. 삽입 과정
•
예시: 11을 삽입하려고 할 때
1.
루트 노드 8, 15를 탐색합니다. 11은 8보다 크고 15보다 작으므로, 오른쪽 자식 노드 18, 20로 이동합니다.
2.
18, 20 노드에 11을 삽입하려고 합니다. 이 노드는 가득 차지 않으므로 11을 추가할 수 있습니다.
3.
결과적으로 11이 삽입된 후 노드는 11, 18, 20이 됩니다.
2. 검색 과정
•
예시: 10을 검색하려고 할 때
1.
루트 노드 8, 15에서 시작합니다. 10은 8보다 크고 15보다 작으므로 오른쪽 자식 노드로 이동합니다.
2.
오른쪽 자식 노드 18, 20에서 10을 찾으려고 하였으나 이 노드에는 존재하지 않으므로 10이 없다라는 결과를 반환합니다.
3. 삭제 과정
•
예시: 20을 삭제하려고 할 때
1.
루트 노드에서 20이 있는 오른쪽 자식 노드로 이동합니다.
2.
20을 삭제한 후, 노드는 18만 남습니다.
3.
이 경우, B-트리의 특성에 따라 18이 리프 노드이므로 간단히 삭제가 이루어집니다.
4.
삭제 후, 노드가 가득 차지 않을 경우, 필요에 따라 형제 노드에서 키를 빌리거나 병합하는 과정을 거칩니다.
요약
•
B-트리는 여러 개의 키를 포함하고, 검색, 삽입, 삭제 성능을 최적화하여 디스크 기반 시스템에 매우 효율적입니다.
•
주어진 B-트리 구조는 여러 키와 자식 노드를 사용하여 균형을 유지하며, 각 노드는 해당 키들에 따라 정렬된 값들을 포함합니다.
•
B-트리는 데이터베이스와 파일 시스템에서 대량의 데이터를 효율적으로 처리할 수 있는 강력한 구조입니다.