범위 비교로 한 경로만 내려감

검색 키 45는 각 노드의 키 범위를 따라가지만,
선택된 노드 어디에도 일치하지 않아 실패합니다.

B-Tree 검색은 모든 자식을 훑지 않고, 현재 노드의 키와 비교해 다음에 읽을 노드 하나를 결정합니다.

검색 키
45
1단계 · 루트 확인

루트 노드의 범위 결정

[ 30 , 60 ]
30 < 45 < 60

45는 두 키 사이에 있으므로 왼쪽·오른쪽이 아니라 가운데 자식 하나만 읽습니다.

2단계 · 선택된 자식 확인

가운데 자식에서 다시 비교

[ 40 , 50 ]
40 < 45 < 50

선택한 노드에도 45와 정확히 같은 키가 없습니다. 비교는 맞았지만 일치 값은 찾지 못했습니다.

3단계 · 결과

검색 실패

45는 현재 B-Tree 안에 없습니다.

루트 → 가운데 자식
방문
노드 2개만 확인하고 종료
I/O
2회 = 루트 1번 + 내부 노드 1번

읽는 법

B-Tree는 “현재 노드에서 범위를 비교하고, 그 결과에 맞는 자식 하나로 이동”하는 과정을 반복합니다. 그래서 검색 비용은 방문한 노드 수, 즉 트리 높이에 비례합니다.

이번 예시

45는 루트의 범위에는 들어오지만, 내려간 노드에 같은 키가 없어 최종적으로 존재하지 않는 값으로 판정됩니다.