검색 비용 비교
행 수가 커질수록 차이는 선형 증가와 로그 증가로 벌어집니다
Full Table Scan은 행을 하나씩 확인하고, Index Scan (B+Tree)은 트리 높이만 따라 내려갑니다. 그래서 데이터가 커질수록 “얼마나 많이 보느냐”보다 “얼마나 빨리 늘어나느냐”가 성능 차이를 만듭니다.
비교 질문
Full Table Scan
Index Scan (B+Tree)
찾는 방식
앞에서부터 한 행씩 확인

조건이 맞는지 끝까지 읽어 보며 찾습니다.

루트 → 리프까지 후보를 좁힘

트리 높이만큼 내려가며 필요한 위치에 빠르게 도달합니다.

행 수가 10배 늘면
거의 10배 더 비교

비교 횟수가 데이터 건수와 거의 1:1로 같이 증가합니다.

몇 번만 더 비교

log₂(N) 수준으로 늘어나 증가 속도가 훨씬 완만합니다.

1,000만 행 예시
10,000,000회

원하는 행이 뒤에 있으면 거의 전부 확인할 수 있습니다.

약 23회

log₂(10,000,000) ≈ 23

1억 행 예시
100,000,000회

데이터가 10배가 되면 비용도 그대로 10배 커집니다.

약 27회

1,000만 행에서 10배 늘어도 비교는 약 4회만 더 필요합니다.

B+Tree 인덱스 비교 횟수의 증가 속도
1천 건 ~10
10만 건 ~17
100만 건 ~20
1천만 건 ~23
1억 건 ~27
핵심: 데이터가 많아질수록 인덱스의 장점은 “조금 덜 본다”가 아니라 비교 횟수의 증가 속도 자체가 다르다는 점입니다.