Fan-out

BST보다 B-Tree 계열이 DB 인덱스에 맞는 이유

페이지 한 번을 읽을 때 더 많은 분기 후보를 담으면 트리 높이와 랜덤 페이지 접근이 줄어든다.

BST: 좁은 fan-out

40
↓
60
↓
70
↓
80

단계가 깊어질수록 페이지 접근이 늘기 쉽다.

B-Tree: 넓은 fan-out

20406080
↓
51015
455055
859095

한 페이지 안에서 많은 후보를 비교하므로 높이가 낮다.

DB 인덱스의 핵심은 CPU 비교 횟수보다 “루트에서 리프까지 몇 페이지를 읽는가”이다.