Fan-out

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

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

깊은 트리
높은 fan-out
페이지 단위
BST키 1개, 자식 2개
깊이 증가행이 많아질수록 단계 증가
페이지 접근랜덤 접근이 늘기 쉬움
B-Tree한 페이지에 여러 키
fan-out 증가한 번에 많은 범위 분기
높이 감소루트에서 리프까지 단계 감소