B-트리 탐색(B-Tree Querying)이란?
B-트리(B-Tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 균형 다진 트리(multiway balanced tree) 자료구조입니다. 이 글에서는 B-트리에서 특정 키를 찾는 과정, 즉 B-트리 탐색(B-Tree Querying)이 어떻게 동작하는지 단계별로 살펴보겠습니다.
B-트리의 탐색 방식은 이진 탐색 트리(Binary Search Tree)와 매우 유사하지만, 한 노드가 여러 개의 키를 가질 수 있다는 점이 다릅니다. 각 노드의 키들은 항상 정렬된 상태로 유지되므로, 키의 대소 관계를 비교하며 어떤 자식 서브트리로 내려갈지 결정할 수 있습니다.
탐색 예시
아래와 같은 B-트리가 있다고 가정해 보겠습니다.
이 트리에서 66을 찾는 과정은 다음과 같습니다.
1. 루트 노드에서 시작합니다. 루트의 키는 46이고, 찾으려는 값 66은 46보다 큽니다. 따라서 루트의 오른쪽 자식으로 이동합니다.
2. 오른쪽 자식 노드에는 여러 개의 키가 있으며, 정렬된 상태로 [56, 81]을 담고 있습니다. 목표 키 66은 56보다 크고 81보다 작습니다.
3. 따라서 56과 81 사이에 위치한 서브트리로 진입합니다.
4. 이 지점에서 리프(leaf) 레벨에 도달했고, 그곳에서 원하는 요소 66을 발견하게 됩니다.
이처럼 B-트리 탐색은 루트에서 시작해 각 노드에서 키를 비교하고, 적절한 키 범위에 해당하는 자식 포인터를 따라 내려가는 과정의 반복으로 이루어집니다.
탐색 알고리즘
B-트리에서 요소를 검색하는 알고리즘은 다음과 같습니다.
BTreeSearch(root, key)
입력(Input): 트리의 루트 노드와 찾고자 하는 키(key)
출력(Output): 해당 키를 가진 노드의 값(value). 키가 존재하지 않으면 null을 반환
x := 루트 노드 읽기
if x가 인덱스(index) 노드이면
x 안에 o->key = 'key'인 객체 o가 존재하면 o->val 반환
'key'의 범위를 포함하는 x의 자식 x->child[i]를 찾음
return BTreeSearch(x->child[i], key)
else
if x 안에 o->key = 'key'인 객체 o가 존재하면 o->val 반환
else null 반환
end if
end if시간 복잡도
B-트리의 탐색 시간 복잡도는 O(log n)입니다. B-트리는 높이가 낮게 유지되는 균형 트리이므로, 트리에 저장된 데이터가 많아져도 탐색에 필요한 디스크 접근 횟수나 비교 횟수가 로그 스케일로 증가합니다. 이러한 특성 덕분에 B-트리는 대용량 데이터를 다루는 데이터베이스 인덱스 구조로 널리 채택되고 있습니다.