B+ 트리 검색(Query)이란?
B+ 트리에서 원하는 데이터를 찾는 과정을 B+ 트리 검색(Searching) 또는 B+ 트리 쿼리(Querying)라고 합니다. 이 알고리즘은 B-트리의 검색 방식과 매우 유사하지만, B+ 트리는 여기에 더해 범위 검색(Range Query) 기능까지 지원한다는 점에서 차별화됩니다.
설명을 위해 다음과 같은 B+ 트리가 있다고 가정해 보겠습니다.
B+ 트리 예시
단일 키 검색 과정
B+ 트리의 검색 방식은 이진 탐색 트리(Binary Search Tree)와 상당히 비슷합니다. 예를 들어 위 트리에서 값 63을 찾는다고 해보겠습니다.
먼저 루트 노드에서 시작합니다. 63은 루트의 요소인 60보다 크고 75보다 작으므로, 60의 오른쪽 자식으로 이동합니다. 그 오른쪽 자식이 바로 63입니다.
여기서 중요한 점이 있습니다. 만약 일반적인 B-트리였다면 이 시점에서 검색이 종료되었을 것입니다. 하지만 현재 노드는 실제 데이터를 저장하지 않는 내부 노드(Internal Node)이므로, 아직 진짜 결과가 아닙니다. B+ 트리에서는 모든 실제 레코드가 리프 노드(Leaf Node)에만 저장되기 때문에, 반드시 리프 레벨까지 내려가야 합니다. 리프 노드에 도달하면 비로소 63이라는 레코드를 실제 결과로 얻게 됩니다.
범위 검색(Range Query)의 장점
B+ 트리의 가장 큰 강점은 범위 검색입니다. 예를 들어 63부터 78까지의 모든 요소를 찾고 싶다고 가정해 보겠습니다.
일반적인 방식이라면 각 요소마다 처음부터 다시 검색해야 하지만, B+ 트리에서는 그럴 필요가 없습니다. 먼저 시작 값인 63이 위치한 리프 노드를 찾은 뒤, 리프 노드들이 서로 연결되어 있는 연결 리스트(Linked List) 구조를 따라가며 78 이전의 모든 노드를 순차적으로 읽으면 됩니다. 역추적(backtracking) 없이 효율적으로 범위 내의 데이터를 조회할 수 있기 때문에, B+ 트리는 데이터베이스 인덱스 등 범위 질의가 많은 시스템에서 널리 사용됩니다.
검색 알고리즘
이제 B+ 트리에서 특정 요소를 검색하는 알고리즘을 살펴보겠습니다.
BPlusTreeSearch(root, key)
- 입력(Input): 트리의 루트 노드, 찾고자 하는 키(key)
- 출력(Output): 해당 키를 가진 노드의 값. 키가 존재하지 않으면 null 반환
레코드에 대해 이진 탐색(binary search) 수행
if 'key'에 해당하는 레코드를 찾았다면,
해당 레코드 반환
else if 현재 노드가 리프 노드이고 키를 찾지 못했다면,
null 반환
이 알고리즘은 각 노드 내부에서 이진 탐색으로 다음 자식 포인터를 빠르게 결정하고, 리프 노드에 도달할 때까지 트리를 따라 내려가는 방식으로 동작합니다. 키를 찾으면 해당 레코드를 반환하고, 리프 노드까지 내려갔는데도 키가 없다면 검색 실패로 null을 반환합니다.