깊어짐키 1개
포인터 2개와 함께 저장되어 한 번 읽어도 비교 범위가 작습니다.
디스크에서는 트리 높이가 곧 읽어야 할 블록 수입니다.
노드 하나를 따라갈 때마다 디스크 블록을 한 번 더 읽습니다. 그래서 같은 100만 건 검색이라도, 얼마나 많은 키를 한 노드에 담느냐가 성능을 가릅니다.
디스크 I/O 1회 ≈ 10ms
SSD는 더 빠르지만, 메모리 접근보다 훨씬 느립니다. 결국 I/O 횟수 감소가 핵심입니다.
한 블록에 담는 키
노드 구조가 깊이에 직접 영향
깊어짐키 1개
포인터 2개와 함께 저장되어 한 번 읽어도 비교 범위가 작습니다.
낮아짐키 수백 개
한 블록에서 많은 키를 비교해 다음 범위를 크게 좁힙니다.
100만 건일 때 트리 높이
깊이가 작을수록 루트부터 빨리 도달
log2(1,000,000)에 가까워 단계가 많습니다.
차수 100이면 log100(1,000,000) 수준까지 낮아집니다.
검색 시 디스크 I/O
최악 기준으로 필요한 블록 읽기
노드당 키가 적어 거의 매 단계마다 새 블록을 읽습니다.
팬아웃이 커서 루트-중간-리프 정도로 끝납니다.
예상 지연 시간
I/O 1회 10ms로 단순 계산
20 × 10ms
3 × 10ms
핵심 차이는 알고리즘 이름이 아니라 블록 활용 방식입니다. B-Tree는 한 번 읽을 때 더 많은 키를 처리해 트리 높이와 디스크 접근 횟수를 함께 줄입니다.