전제
차수 200
내부 노드 최대 199개 키
리프당 100개 레코드
높이가 1만 늘어도 다음 레벨이 약 200갈래로 퍼집니다. 그래서 트리는 낮게 유지되지만, 저장 가능한 레코드 수는 기하급수적으로 커집니다.
높이 1
루트만
루트
199개 키
단일 노드의 시작점
높이 2
루트 + 리프
루트
리프
20,000건
200 × 100
높이 3
내부 1층 추가
루트
내부
리프
4,000,000건
200 × 200 × 100
높이 4
내부 2층
루트
내부
내부
리프
800,000,000건
200³ × 100
검색 경로 = 트리 높이
루트
→
상위 내부
→
리프
→
레코드 위치
루트와 상위 내부 노드는 보통 버퍼 캐시에 머무르므로, 높이 3~4 트리라도 매번 모든 단계를 디스크에서 다시 읽지 않습니다.
실무 해석
수백만~수억 건도
낮은 높이로 탐색
검색 경로는 3~4단계면 충분하고, 실제 디스크 I/O는 보통 리프 중심의 1~2회까지 줄어듭니다.