email 인덱스
B+Tree는 필요한 가지로만 내려가서
ROWID 238
을 찾는다
예시 트리에서는 몇 단계만 거치면 되고, 데이터가
1,000만 행
으로 커져도 비교 횟수는 전체 행 수가 아니라
트리 높이
를 따라 늘어납니다.
입력
찾는 값
test@example.com
조건은
WHERE email = 'test@example.com'
. 이제 전체 테이블이 아니라 정렬된 인덱스에서 갈림길을 고릅니다.
1단계
루트
[m]
→
오른쪽 가지
찾는 값이
m
보다 뒤에 있으므로 왼쪽 전체를 건너뛰고 오른쪽 서브트리로 내려갑니다.
2단계
내부 노드
[d]
[t]
여러 구간 중에서
t
범위만 선택합니다. 관련 없는 구간은 여기서 이미 제외됩니다.
3단계
리프
[n,p]
[t,u,z]
→
test@example.com
리프에서 실제 엔트리를 찾고, 그 엔트리가 가리키는
ROWID
를 읽습니다.
Full Table Scan
최악 1,000만 번
행을 앞에서부터 끝까지 확인해야 하므로 데이터가 커질수록 비교와 디스크 I/O가 함께 늘어납니다.
Index Scan
약 log₂N, 1,000만 건도 약 23번
B+Tree의 높이만큼만 내려가면 되므로, 필요한 범위만 좁혀서 실제 행 위치를 빠르게 찾습니다.