B+Tree는 B-Tree와 비교해 왜 범위 검색에 더 유리한가?

리프 노드가 연결 리스트로 이어져 있어 중간에 위아래 노드로 되돌아가지 않고 수평 탐색을 하기 때문이다.

B-Tree에서 특정 범위의 데이터를 찾으려면 트리를 오르내리는 재귀적 탐색을 반복해야 한다. 부모 노드와 다른 자식 노드로 경로를 바꾸는 과정에서 많은 메모리 연산과 디스크 탐색이 일어난다.

B+Tree는 리프 노드끼리 서로 주소를 가리킨다. 맨 앞의 값을 찾은 뒤에는 연결 리스트를 타고 옆으로 이동하며 데이터를 순차적으로 읽는다.

다만 B+Tree는 특정 단일 키를 검색할 때도 무조건 리프 노드까지 가야 한다. 루트 노드에 데이터가 있어도 탐색을 중간에 멈추지 않는다.